3.3 二叉树遍历

1 便利 （递归的过程）
1.1 先序便利
1 访问根结点;
2 先序遍历其左子树;
3 先序遍历其右子树

void PreOrderTraversal(Bintree BT) {
if (BT) {
printf ("%d",BT->data);
PreOrderTraversal(BT->Left);
PreOrderTraversal(BT->Right);
}
}

先序

1.2 中序
1 中序遍历其左子树;
2 访问根结点;
3 中序遍历其右子树。

void InOrderTraversal( BinTree BT ) {
if( BT ) {
InOrderTraversal( BT->Left ); 
printf(“%d”, BT->Data); 
InOrderTraversal( BT->Right );
} }

中序

1.3 后续
1 后序遍历其左子树;
2 后序遍历其右子树;
3 访问根结点。

void PostOrderTraversal( BinTree BT ) {
if( BT ) {
PostOrderTraversal( BT->Left ); PostOrderTraversal( BT->Right); printf(“%d”, BT->Data);
} }

后序

先序、中序和后序遍历过程:遍历过程中经过结点的路线一 样，只是访问各结点的时机不同。

2.非递归遍历
使用堆栈

2.1中序遍历非递归遍历算法
遇到一个结点，就把它压栈，并去遍历它的左子树;
当左子树遍历结束后，从栈顶弹出这个结点并访问它;
然后按其右指针再去中序遍历该结点的右子树

void InOrderTraversal( BinTree BT )
{  BinTree T=BT;
Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ 
while( T || !IsEmpty(S) ){
while(T){ /*一直向左并将沿途结点压入堆栈*/
Push(S,T);
T = T->Left; 
}
if(!IsEmpty(S)){
T = Pop(S); /*结点弹出堆栈*/
printf(“%5d”, T->Data); /*(访问)打印结点*/ 
T = T->Right; /*转向右子树*/
} 
}
}

2.2先序遍历的非递归算法，只需要把print的时机移动到push的时候即可。

3.层序遍历
二叉树遍历的核心问题： 二维结构的线性化。

队列实现:遍历从根结点开始，首先将根结点入队，然后开始执行循环:结点出队、访问该结点、其左右儿子入队

先根结点入队
从队列中取出一个元素;
访问该元素所指结点;
若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队。

void LevelOrderTraversal ( BinTree BT )
{
Queue Q; BinTree T;
if ( !BT ) return; /* 若是空树则直接返回 */
Q = CreatQueue( MaxSize ); /*创建并初始化队列Q*/ AddQ( Q, BT );
while ( !IsEmptyQ( Q ) ) {
T = DeleteQ( Q );
printf(“%d\n”, T->Data); /*访问取出队列的结点*/ 
if ( T->Left ) AddQ( Q, T->Left );
if ( T->Right ) AddQ( Q, T->Right );
} }

层序

必须有中序 加上先序或者后序，才可以唯一确定一个二叉树。先序加后续不可以。