1、先序
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}
2、中序
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d\n", BT->Data);
InOrderTraversal(BT->Right);
}
}
3、后序
void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d\n", BT->Data);
}
}
注意事项
1、前序遍历
从整棵二叉树的根结点开始,对于任意结点VV,访问结点VV并将结点VV入栈,并判断结点VV的左子结点LL是否为空。若LL不为空,则将LL置为当前结点VV;若LL为空,则取出栈顶结点,并将栈顶结点的右子结点置为当前结点VV。
2、中序遍历
从整棵二叉树的根结点开始,对于任一结点VV,判断其左子结点LL是否为空。若LL不为空,则将VV入栈并将L置为当前结点VV;若LL为空,则取出栈顶结点并访问该栈顶结点,然后将其右子结点置为当前结点VV。重复上述操作,直到当前结点V为空结点且栈为空,遍历结束。
3、后序遍历
将整棵二叉树的根结点入栈,取栈顶结点VV,若VV不存在左子结点和右子结点,或VV存在左子结点或右子结点,但其左子结点和右子结点都被访问过了,则访问结点VV,并将VV从栈中弹出。若非上述两种情况,则将VV的右子结点和左子结点依次入栈。重复上述操作,直到栈为空,遍历结束。