二叉树非递归深度优先DFS算法

青旅半醒 2022-06-07 02:14 207阅读 0赞

二叉树可以递归遍历，实现简洁，易于理解。这里介绍二叉树的非递归的三种遍历，以下图二叉树为例讲解。

![SouthEast][]

**先前声明**

#define ELEMENTTYPE char
    typedef struct node* pnode;
    typedef struct node* PBintree;
    
    struct node{
        ELEMENTTYPE n;
        pnode lchild;
        pnode rchild;
    };

**先序遍历非递归实现**

上图的先序遍历顺序为：ABDECF

思路：

1）从二叉树的根结点开始，将其压入栈

2）当栈不为空时，取栈顶元素作为当前树（左子树或右子树），赋值给p并弹出；否则，遍历结束

3）如果p不为空，访问p并将p的右子树、左子树（可能为空树）依次（优先访问左子树）压入栈中

4）返回 2）

C++实现：

void pre_order(PBintree t)
    {
        if(t==NULL) return;
        stack<pnode> s;
        pnode p = t;
        s.push(p);
        while(!s.empty()){
            p=s.top();
            s.pop();
            if(p){
                cout<<p->n;
                s.push(p->rchild);
                s.push(p->lchild);
            }
        }
    }

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

上图的中序遍历顺序为：DBEAFC

思路：

1）从二叉树的根结点开始，将其赋值给p作为当前结点

2）不断将p及p的左子树压入栈，直到p为空

3）取栈顶元素并弹出，赋值给p作为当前结点，访问p

4）将p的右子树赋值给p作为当前结点

5）如果栈不为空（遍历结束） 或者 p不为空，返回2）

C++实现：

void in_order(PBintree t)
    {
        if(t==NULL) return;
        stack<pnode> s;
        pnode p = t;
        while(p || !s.empty()){
            while(p){
                s.push(p);
                p=p->lchild;
            }
            p=s.top();
            s.pop();
            cout<<p->n;
            p=p->rchild;
        }
    }

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

上图的后序遍历顺序为：DEBFCA

遍历方法：

首先由该二叉树找到其左子树，遍历其左子树，遍历完返回到这颗二叉树；

然后由该二叉树找到其右子树，遍历其右子树，遍历完再次返回这颗二叉树，此时才能访问该二叉树的根结点。

思路：

从上面可分析出，在后序遍历二叉树时，一棵二叉树可能要进、出栈各两次，只有它第二次出栈后才能访问其根结点。因此，为了区分同一颗二叉树的两次出栈，需要给各结点增加一个标示量tag，用来记录是第一次还是第二次出栈。如果是第一次，先不访问二叉树的根结点；如果是第二次，则访问。

可以改进思路，为了节省空间，取消标示量tag；为了节省时间，每颗二叉树只进栈和出栈一次。为此，需要在二叉树出栈时增加判断：如果是栈顶二叉树的左子树回来，直接遍历右子树。如果是从栈顶二叉树的右子树回来，直接执行出栈，并访问根结点。算法步骤：

1）从二叉树的根结点开始，将其置为当前子树p

2）将p压入栈，如果p有左子树，则将p的左子树置为当前p，将p压入栈

3）如果p没有左子树，但是有右子树，则将p的右子树置为当前p，将p压入栈，重复2），直到p没有左子树也没有右子树

4）取栈顶元素并弹出，置为当前p，访问p

5）如果栈不为空，而且此时栈顶元素的左子树就是p（从左子树退回），则进入栈顶元素右子树；如果此时栈顶元素的右子树不 是p（从右子树返回），则返回 4），直到栈为空而且p为空（遍历结束）

C++实现：

void aft_order(PBintree t){
        stack<pnode> s;
        PBintree p = t;
        while(p||!s.empty()){
            while(p){
                s.push(p);
                p=p->lchild?p->lchild:p->rchild;
            }                                        //循环到当前处理的点
            p=s.top();                               //访问栈顶二叉树的根
            s.pop();
            cout<<p->n;
            if(!s.empty() && p==(s.top())->lchild)   //栈不为空，且从左子树退回
                p=(s.top())->rchild;                 //直接进入栈顶元素的右子树
            else
                p=NULL;                              //从右子树回来，退到上一层处理
        }
    }

[SouthEast]: /images/20220607/2b6d972828f74c05aa36b0101f4c6290.png