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 );
} }
层序
必须有中序 加上先序或者后序，才可以唯一确定一个二叉树。先序加后续不可以。
