数据结构——树——二叉树遍历

r囧r小猫 2022-04-16 04:15 305阅读 0赞

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。  
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。  
**二叉树的遍历**  
![在这里插入图片描述][2018111616123139.png]

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

![在这里插入图片描述][20181116161359105.png]

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

![在这里插入图片描述][20181116161443171.png]

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

![在这里插入图片描述][20181116161711839.png]

void LevelorderTraversal ( BinTree BT )
    {
         
        Queue Q; 
        BinTree T;
        if ( !BT ) return; /* 若是空树则直接返回 */
        Q = CreatQueue(); /* 创建空队列Q */
        AddQ( Q, BT );
        while ( !IsEmpty(Q) ) {
        
            T = DeleteQ( Q );
            printf("%d ", T->Data); /* 访问取出队列的结点 */
            if ( T->Left )   AddQ( Q, T->Left );
            if ( T->Right )  AddQ( Q, T->Right );
        }
    }

层序基本过程：先根结点入队，然后：

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

**先序遍历的非递归遍历算法**

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

**后序遍历非递归遍历算法**

void PostOrderTraversal( BinTree BT )
    {
        
        BinTree T BT,t;
        Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
        while( T || !IsEmpty(S) )
        {
        
            while(T)    /*一直向左并将沿途结点压入堆栈*/
            {
        
                Push(S,T);
                T = T->Left;
            }
            if(!IsEmpty(S))
            {
        
                T=S.top();
                if(T->Right&&T->Right!=t){
        //右子树存在且未被访问
                    T=T->Right;
                }
                else {
        
                T = Pop(S); /*结点弹出堆栈*/
                printf(“%5d”, T->Data); /*（访问）打印结点*/
                t=T;
                T = NULL; /*重置*/
                }
            }
        }
    }

![在这里插入图片描述][20181116165436885.png] [先序输出叶结点][Link 1]

![在这里插入图片描述][2018111616553279.png][求二叉树高度 ][Link 2]  
类似的：  
[计算给定二叉树T的宽度][T]  
![在这里插入图片描述][20181116165642820.png][前缀表达式][Link 3]

**注意：由两种遍历序列确定二叉树 必须要有中序序列才行**

![在这里插入图片描述][2018111616581746.png][实现代码][Link 4]

[根据后序和中序遍历输出先序遍历][Link 5]

以下为习题：

[ 例题：二叉树的遍历][Link 6]

[练习：树的同构][Link 7]

[练习：判断一颗二叉树是否是另一颗树的子树][Link 8]

[2018111616123139.png]: /images/20220416/d14f23f2ac4640f3957ce54c6ade4c76.png
[20181116161359105.png]: /images/20220416/7ef1c36a8c1a4e7385873702a016fd6e.png
[20181116161443171.png]: /images/20220416/4c6de86b8cd54c31a8daf6da9702e047.png
[20181116161711839.png]: /images/20220416/3215a32012c941f1910eb682b9bff7b9.png
[20181116165436885.png]: https://img-blog.csdnimg.cn/20181116165436885.png
[Link 1]: /images/20220416/b4d7e1eef50643b0a6908c6eb64458dd.png
[2018111616553279.png]: https://img-blog.csdnimg.cn/2018111616553279.png
[Link 2]: /images/20220416/7bcb1be1e10e4499979a31dfca980797.png
[T]: https://blog.csdn.net/qq_42623428/article/details/83757002
[20181116165642820.png]: https://img-blog.csdnimg.cn/20181116165642820.png
[Link 3]: /images/20220416/59c88f8048e14c57af5a53e91057f83e.png
[2018111616581746.png]: https://img-blog.csdnimg.cn/2018111616581746.png
[Link 4]: /images/20220416/11997125c8c642679efe69154ce03d10.png
[Link 5]: https://blog.csdn.net/qq_42623428/article/details/83628120
[Link 6]: https://blog.csdn.net/qq_42623428/article/details/83628335
[Link 7]: https://blog.csdn.net/qq_42623428/article/details/83685033
[Link 8]: https://blog.csdn.net/qq_42623428/article/details/83794413