1 递归遍历

A B C D F G I E H

1.1 先序遍历

过程：访问根节点->先序遍历左子树->先序遍历后子树 遍历顺序：A (B D F E) (C G H I) 遍历代码：

void PreorderTraversal( BinTree BT ) { if( BT ) { printf("%d ", BT->Data ); PreorderTraversal( BT->Left ); PreorderTraversal( BT->Right ); } }

1.2 中序遍历

过程：先序遍历左子树->访问根节点->先序遍历后子树 遍历顺序：(B D F E) A (C G H I) 遍历代码：

void InorderTraversal( BinTree BT ) { if( BT ) { InorderTraversal( BT->Left ); /* 此处假设对BT结点的访问就是打印数据 */ printf("%d ", BT->Data); /* 假设数据为整型 */ InorderTraversal( BT->Right ); } }

1.3 中序遍历

过程：先序遍历左子树->先序遍历后子树->访问根节点 遍历顺序：(B D F E) (C G H I) A 遍历代码：

void PostorderTraversal( BinTree BT ) { if( BT ) { PostorderTraversal( BT->Left ); PostorderTraversal( BT->Right ); printf("%d ", BT->Data); } }

1.4 总结

由遍历顺序可以观察到，前中后序遍历只会影响访问路径的先后，而路线是一样的。

2 非递归实现

因为非递归的话，可能要先存入这个节点数值但不使用，所以考虑堆栈

2.1 先序遍历

流程：见一个节点，直接输出，然后顺着他左边同理遍历，直到左空，然后pop出最新压进栈的，看他有没有右儿子，有的话就在右子树同理进行上述操作。

void PreorderTraversal( BinTree BT ) { BinTree T,BT; Stack S=CreatStack(MaxSize); while(T||!IsEmpty(S){ while(T){ Push(T,S); printf("%d",T->Data); T=T->Left; } if(!IsEmpty(S){ T=Pop(S); T=T->Right; } } }

2.2 中序遍历

流程：遇到一个节点就压进栈，然后遍历他的左子树，左子树遍历到底之后从栈顶pop出元素并访问，然后遍历他的右子树

void InorderTraversal( BinTree BT ) { BinTree T,BT; Stack S=CreatStack(MaxSize); while(T||!IsEmpty(S){ while(T){ Push(T,S); T=T->Left; } if(!IsEmpty(S){ T=Pop(S); printf("%d",T->Data); T=T->Right; } } }