数据结构——树（下）

1、二叉树的递归遍历

1、先序遍历

图示为

代码实现为

void PreOrderTraversal(BinTree BT){
    if (BT){
        cout << BT->Data;
        PreOrderTraversal(BT->left);
        PreOrderTraversal(BT->right);
    }           

2、中序遍历

void InOrderTraversal(BinTree BT){
    if (BT){
        InOrderTraversal(BT);
        cout << BT->Data;
        InOrderTraversal(BT);
    }
}           

3、后序遍历

void PostOrderTraversal(BinTree BT){
    if (BT){
        PostOrderTraversal(BT);
        PostOrderTraversal(BT);
        cout << BT->Data;
    }
}           

重点说明：先序、前序和后序只是遍历过程中的访问各结点的顺序不同，但是经过的路线是一样的

2、二叉树的非递归遍历

​ 非递归算法的实现基本思路：使用堆栈

1、中序遍历非递归遍历方法

具体方法：

• 遇到一个结点，就压栈，再去遍历它的左子树
• 当左子树遍历完成时，从栈顶弹出这个结点并访问它
• 然后按其右指针再去中序遍历该结点的右子树

void InOrderTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = CreatStack(MAXSIZE);
    while (T || IsEmpty(S)) {
        while(T) {
            Push(S, T);
            T = T->left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S);
            cout << T->Data;
            T = T->right;
        }
    }
}           

2、先序遍历非递归遍历方法

• 当遇到一个结点，第一次遇到时直接输出，再去遍历它的左子树
• 当左子树遍历完成，弹出左子树，再遍历右子树
• 当右子树遍历完成，返回结点

void PreOrderTraversalTest(BinTree BT) {
    BinTree T = BT;
    Stack S = CreatStack(MAXSIZE);
    while (T || IsEmpty(S)) {
        while(T) {
            Push(S, T);
                        cout << T->Data;
            T = T->left;
        }
        if (!IsEmpty(S)){
            T = Pop(S);
            T = T->right;
        }
    }
}           

3、后序遍历非递归遍历方法

• 从结点开始，一直压栈，直到最左子树
• 弹出最左子树，返回结点，遍历右子树
• 右子树遍历完毕，返回结点

代码实现为：

void PostOrdeTraversal(BinTree BT) {
    BinTree T = BT;
    BinTree pre = nullptr;        //储存当前结点的前一个结点 
    BinTree Ttop;        //储存栈顶元素
    Stack S = CreatStack(MAXSIZE);
    while(T || IsEmpty(s)) {
        while(T) {
            Push(T, S);
            T = T->left;
        }
        Ttop = Top(S);        //查看当前栈顶元素 
        if(Ttop->right == nullptr || Ttop->left == pre){
            //当前结点没有右子树或已被访问 
            cout << Ttop->Data;
            pre = Ttop;        //更新前一个结点的位置 
            Pop(S);
        }else{
            T = Ttop->right;        //开始访问右子树 
        }
    } 
}