二叉树的遍历.队列与栈实现（深度优先，广度优先）

柔情只为你懂 2023-07-02 07:28 24阅读 0赞

树的遍历方法有广度优先（层序遍历），以及深度优先两种方法，分成先序遍历，中序遍历，后序遍历三种。  
一.深度优先：  
1.递归实现：  
先序遍历  
输出顺序：根节点，左子树，右子树。

void PreOrderTraversal( BinTree BT)
    {
        
        if(BT){
            //如果树非空
            printf("%d",BT->Data);    //输出根节点
            PreOrderTraversal(BT->Left);  //继续递归执行其左子树
            PreOrderTraversal(BT->Right); //继续递归其右子树
        }
    }

中序输出：左子树，根节点，右子树。  
只需要将输出语句放到两个递归语句之间即可。

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

后序输出：左子树，右子树，根节点。

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

第一次遇到就输出则为先序遍历，第二次遇到才输出则为中序遍历，第三次遇到输出则为后序遍历。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70][]  
二.非递归实现  
中序遍历，由于中序遍历的特点是在第二次遇到该元素时才会输出，所以我们可以使用栈来进行操作。  
1 遇到节点，就把他压入栈，然后遍历他的左子树。  
2 左子树的遍历结束后，将节点弹出栈并输出他，然后再遍历他的右子树。

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);                        //节点出栈                          
            printf("%5d",T->Data);           //输出节点
            T=T->Right;                      //再转向右子树。
        }
        }
    }

先序遍历的算法是第一次遇到节点就输出，所以非递归的写法只需要根据中序遍历的代码修改输出语句的顺序即可。

void InOrderTraversal( BinTree BT)
    {
        
        BinTree T=BT;
        stack s=CreatStack(maxsize);
        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;
        }
        }
    }

后序遍历的非递归写法，即可在结构中增加一个记录次数的指针，使其在为2时输出节点，可在节点出栈时，将其再次入栈，等到它再次出栈时右子树刚刚遍历完毕，此时可以输出节点。

一.通过给节点增加访问次数的属性实现：

void PostOrderTraversal(Bintree BT) {
          //给节点增加访问次数的属性Visit，初始化为0
        Bintree T BT;
        Stack S = CreateStack(Maxsize);
        while (T || !IsEmpty(S)) {
        
            while (T) {
        
                if (T->Visit == 0) {
        //虽然没必要判断，为便于理解
                    T->Visit++;
                    Push(S, T);  //第一次入栈，不访问
                }
                T = T->left;   //转向左子树
            }
            if (!IsEmpty(S)) {
        
                T = Pop(s);
                if (T->Visit == 2)    {
        
                    printf("%d", T->Data);//第三次碰到它，访问节点，可以彻底从堆栈弹出了
                    T = NULL;//左右子数均已经访问过
                }
                else {
        
                    T->Visit++;
                    Push(S, T);  //第二次入栈，不访问，（相当于T没有出栈）
                    T = T->Right;  //转向右子树
                }
            }
        }

总结：  
(1)借助堆栈实现前序遍历、中序遍历非递归程序的本质是利用堆栈模拟递归函数调用时的入栈和出栈过程。而前序遍历、中序遍历和后序遍历在递归函数执行时，结点（作为函数参数）的入栈和出栈过程是完全一样的。  
(2)前序遍历是在结点入栈时输出结点信息，然后开始分别对该结点左右子树的遍历；而在中序遍历中，结点出栈时表明刚完成对该结点左子树的遍历，此时可输出该结点信息。  
(3)后序遍历必须在左右子树均输出的情况下才能输出该结点。如果直接采用前序遍历、中序遍历的非递归程序，我们没法判别该结点的右子树什么时候遍历结束。为了能知道结点右子树什么时候遍历结束，可以在其左子树遍历结束（即该结点出栈）时，将该结点再次入栈，等到它再次出栈时就说明其右子树刚刚遍历完毕，此时可以输出该结点。  
(4)也就是在后序遍历的非递归过程中，可以让每个结点两次入出栈，第一次出栈说明其左子树已遍历完成，第二次出栈说明右子树也遍历完成，可以输出结点信息。为了区分到底是第几次入出栈，可以给每个入栈结点增加一个标记（也就需要采用结构，其中一个分量作为标记以区分第几次入出栈）。

二.广度优先（层序遍历）  
实现方法，利用队列的线性结构可以实现，首先将根节点入队，在从队列中取出一个元素，并输出它，判断其是否为空，若非空，则按照先左后右的顺序，将其左右子入队，下面是伪代码。

void LevelOrderTraversal( BinTree BT)
    {
        
        Queue Q;
        BinTree T;
        if(!BT) return;  //若是空树则直接返回
        Q = CreatQueue(maxsize); //创建并初始化队列
        AddQ(Q,BT);
        while(!IsEmpty(s))
        {
        
            T=deleteQ(Q);     //出队
            printf("%d\n",T->data);  //访问该节点
            if(T->Left) AddQ(Q,T->Left);   //分别将其左右子入队
            if(T->Right) AddQ(Q,T->Right);  
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200128234424896.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70