【数据结构】遍历二叉树

1. 遍历二叉树的算法描述（递归定义）

先序遍历

若二叉树为空，则空操作；

否则

（1）访问根节点

（2）先序遍历左子树

（3）先序遍历右子树

中序遍历

若二叉树为空，则空操作；

否则

（1）中序遍历左子树

（2）访问根节点

（3）中序遍历右子树

后序遍历

若二叉树为空，则空操作；

否则

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根节点

2. 根据遍历序列确定二叉树

• 若二叉树中各结点的值均不同，则二叉树的先序、中序、后序序列都是唯一的
• 由二叉树的先序序列和中序序列，或由后序序列和中序序列可以唯一确定一棵二叉树

由先序序列和中序序列确定二叉树：

先序序列先访问的是根节点，由此确定二叉树的根节点和左右子树，然后重复此过程可递归的找到所有的左右子树和根节点

由后序序列和中序序列确定二叉树：

后续遍历最后访问的是根节点，其余同理

3. 遍历算法实现

递归实现

先序遍历

Status PreOrderTraverse(BiTree T){if(t==NULL)return OK;else{printf("%d", T->data);//访问根节点PreOrderTraverse(T->lchild);//递归遍历左子树PreOrderTraverse(T->rchild);//递归遍历右子树}
}

中序遍历

Status InOrderTraverse(BiTree T){if(t==NULL)return OK;else{InOrderTraverse(T->lchild);//递归遍历左子树printf("%d", T->data);//访问根节点InOrderTraverse(T->rchild);//递归遍历右子树}
}

后序遍历

Status PostOrderTraverse(BiTree T){if(t==NULL)return OK;else{PostOrderTraverse(T->lchild);//递归遍历左子树PostOrderTraverse(T->rchild);//递归遍历右子树printf("%d", T->data);//访问根节点}
}

非递归实现

Status InOderTravese(BiTree T){BiTree p,q;InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,q);printf("%c", q->data);p=q->rchild;}}return OK;
}

4. 二叉树的层次遍历

对于一棵二叉树，从根节点开始，按从上到下，从左到右的顺序访问每个结点

设计思路：使用一个队列

1.将根节点进队

2.队不为空时，出队结点p，访问它

​ 1.若它右左孩子，将左孩子进队

​ 2.若它有右孩子，将右孩子进队

使用循环队列

typedef struct{BTNode data[MaxSize];int front,rear;  //队头和队尾指针
}SqQueue;//循环队列

void LevelOrder(BTNode *b){BTNode *p;SqQueue *qu;InitQueue(qu);	//初始化队列enQueue(qu, b);	//根节点进队while(!QueueEmpty(qu)){deQueue(qu, p);				//出队结点pprintf("%c", p->data);		//访问结点pif(p->lchild!=NULL)			//左孩子不为空则进队enQueue(qu, p->lchild);if(p->rchild!=NULL)			//右孩子不为空则进队enQueue(qu, p->rchild);}
}

5. 二叉树的建立

按先序遍历序列建立二叉树的二叉链表

// 构造二叉树（前序遍历，'#'表示空节点）
Status CreateBiTree(BiTree &T){cin>>ch;if(ch=="#")T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;				//生成根节点CreateBiTree(T->lchild);	//构造左子树CreateBiTree(T->rchild);	//构造右子树}return OK;
}

6. 复制二叉树

算法描述

如果是空树，递归结束；

否则，申请新结点空间，复制根节点

​ 递归复制左子树

​ 递归复制右子树

int Copy(BiTree T, BiTree &NewT){if(T==NULL){		//如果是空树，返回0NewT = NULL;return 0;}else{NewT=new BiTree;NewT->data=T->data;Copy(T->lchild, NewT->lchild);Copy(T->rchild, NewT->rchild);}
}

7. 计算二叉树的深度

算法思路

如果是空树，则深度为0

否则，递归计算左子树的深度m，递归计算右子树的深度n，二叉树深度为max(m,n)+1

int Depth(BiTree T){if(T==NULL)return 0;else{m=Depth(T->lchild);n=Depth(T->rchild);return m>n?m+1:n+1;}
}

8. 计算二叉树结点总数

算法描述

如果是空树，则结点个数为0

否则，结点个数为左子树的结点个数+右子树的结点个数再＋1

int NodeCount(BiTree T){if(T==NULL)return 0;elsereturn NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

9. 计算叶子结点数

算法描述

如果是空树，则叶子结点个数为0

否则，叶子结点个数为左子树的叶子结点个数+右子树的叶子结点个数

int LeafCount(BiTree T){if(T==NULL)return 0;if(T->lchild==NULL&&T->rchild==NULL)return 1;elsereturn LeafCount(T->lchild)+LeafCount(T->rchild);
}