【数据结构】二叉树的遍历（递归与非递归）

迈不过友情╰ 2022-06-16 09:13 233阅读 0赞

# 先序遍历（递归） #

遍历过程

1.  访问根结点
2.  先序遍历其左子树
3.  先序遍历其右子树

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

![图示][SouthEast]

# 中序遍历（递归） #

遍历过程为

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

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

![图示][SouthEast 1]

# 后序遍历（递归） #

遍历过程为

1.  后序遍历其左子树
2.  后序遍历其右子树
3.  访问根结点

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

![图示][SouthEast 2]

![图示][SouthEast 3]

# 非递归遍历算法 #

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

中序遍历过程：

1.  遇到一个结点就把它压入栈，并去遍历它的左子树。
2.  当左子树遍历结束后，从栈顶弹出这个结点并访问它。
3.  然后按其右指针再去中序遍历该结点的右子树。

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;/*转向右子树*/
            }
        }
    }

先序遍历的非递归算法，就是第一次碰到结点的时候就print出来，相对于中序遍历（第二次遍历到它的时候再print），就是改下结点的输出时间。

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

后序遍历递归定义：先左子树，后右子树，再根节点。后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。

void PostOrderTraversal( BinTree BT )
    {
        BinTree T = BT;
        BinTreeNode pLastVisit; /*pLastVisit:上次访问节点 */
        Stack S = CreatStack( MaxSize );/*创建并初始化堆栈S*/
        while( T ){
       /*一直向左并将沿途结点压入堆栈*/
            Push(S, T);
            T = T->left;
        }
        while( !IsEmpty(S) ){
            T = Pop(S);/*弹出栈顶元素*/
            /*如果不存在右子树，或者右子树已经被访问过，则输出根结点*/
            if( T->Right == NULL || T->Right == pLastVisit ){
                printf("%5d", T->Data);/*访问并打印结点*/
                pLastVisit = T;/*修改最近被访问的结点*/
            }else{
                //如果存在右子树并且右子树没有访问过，则根结点再次入栈
                Push(S, T);
                //进入右子树，并将右子树的所有左子树压入栈中
                T = T->Right;
                While(T){
                    Push(S,T);
                    T = T->Left;
                }
            }
        }
    }

# 层序遍历 #

二叉树遍历的核心问题：**二维结构的线性化**

从结点访问其左、右儿子结点，访问左儿子后有儿子怎么办？

需要一个存储结构保存暂时不访问的结点：堆栈、队列

队列的实现：

遍历从根结点开始，然后将根结点入队列，然后开始执行循环：结点出队，访问该结点，将其左右儿子入队列。

动图，耐心观看，简单明了

![图示][SouthEast 4]

void LevelOrderTraversal( BinTree BT )
    {
        Queue Q;
        BinTree T;
        if(!BT) Return;/*若是空树则直接返回*/
        Q = CreateQueue( MaxSize )/*创建并初始化队列*/
        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 );
        }
    }

[SouthEast]: /images/20220616/f58313d127d64f25842d4fb7b1b57e68.png
[SouthEast 1]: /images/20220616/cae123da61284b4d8ca0deb034867d5a.png
[SouthEast 2]: /images/20220616/d92ae51f0fb742faace0bf0014c8c044.png
[SouthEast 3]: /images/20220616/ca0c38ff75004d51804d3a6e26351d0c.png
[SouthEast 4]: /images/20220616/ebb40dd830484c5ba20403c298f3afc3.png