二叉树的非递归遍历介绍

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在二叉树遍历类型中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。

​三种遍历方式访问节点的顺序是一致的，不同之处在于，有的遍历流程把访问到的节点暂存起来，达成某种条件后再将节点输出。

​ 前序： 到达一个节点后，即刻输出该节点的值，并继续遍历其左右子树。

​ 中序： 到达一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。

​ 后序: 到达一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。

​ 快速确定遍历序列的方法：

图中在入口到出口的曲线上用

三种符号分别标记出了先序、中序和后序访问各结点的时刻。

1.前序遍历

前序遍历按照 “根结点 - 左孩子 - 右孩子” 的顺序进行访问。

递归实现

void preOrder1(BinTree *root)      //递归前序遍历
{
    if(root!=NULL)
    {
        cout<<root->data<<"";
        preOrder1(root->lchild);
        preOrder1(root->rchild);
    }
}

非递归实现

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树;当访问其左子树时，再访问它的右子树。因此其处理过程如下：

对于任一结点 P：

访问结点 P，并将结点 P 入栈;

判断结点 P 的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点 P，循环至 1); 若不为空，则将 P 的左孩子置为当前的结点 P;

直到 P 为 NULL 并且栈为空，则遍历结束。

void preOrder2(BinTree *root)     //非递归前序遍历 
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL || !s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<"";  //入栈前输出节点的值
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

2.中序遍历

中序遍历按照 “左孩子 - 根结点 - 右孩子” 的顺序进行访问。

递归实现

void inOrder1(BinTree *root)      //递归中序遍历
{
    if(root!=NULL)
    {
        inOrder1(root->lchild);
        cout<<root->data<<"";
        inOrder1(root->rchild);
    }
}

非递归实现

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点 P，

若其左孩子不为空，则将 P 入栈并将 P 的左孩子置为当前的 P，然后对当前结点 P 再进行相同的处理;

若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的 P 置为栈顶结点的右孩子;

直到 P 为 NULL 并且栈为空则遍历结束

void inOrder2(BinTree *root)      //非递归中序遍历
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<"";  //出栈前输出栈顶节点的值
            s.pop();
            p=p->rchild;
        }
    }    
}

3.后序遍历

后序遍历按照 “左孩子 - 右孩子 - 根结点” 的顺序进行访问。

递归实现

void postOrder1(BinTree *root)    //递归后序遍历
{
    if(root!=NULL)
    {
        postOrder1(root->lchild);
        postOrder1(root->rchild);
        cout<<root->data<<"";
    }    
}

非递归实现

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。

第一种思路：对于任一结点 P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还未被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

但是这种解法每个节点会入栈和出栈两次，效率不高。

void postOrder2(BinTree *root)    //非递归后序遍历
{
    stack<BTNode*> s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)              //沿左子树一直往下搜索，直至出现没有左子树的结点 
        {
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty())
        {
            temp=s.top();
            s.pop();
            if(temp->isFirst==true)     //表示是第一次出现在栈顶 
             {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;    
            }
            else    //第二次出现在栈顶 
             {
                cout<<temp->btnode->data<<"";
                p=NULL;
            }
        }
    }    
}

第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点 P，先将其入栈。如果 P 不存在左孩子和右孩子，则可以直接访问它;或者 P 存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将 P 的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

void postOrder3(BinTree *root)     //非递归后序遍历
{
    stack<BinTree*> s;
    BinTree *cur;                      //当前结点 
    BinTree *pre=NULL;                 //前一次访问的结点 
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->lchild==NULL&&cur->rchild==NULL)||
           (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
        {
            cout<<cur->data<<"";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
              s.pop();
            pre=cur; 
        }
        else
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)    
                s.push(cur->lchild);
        }
    }    
}

以上就是关于“二叉树的非递归遍历介绍”，如果大家想了解更多相关知识，可以关注一下本站的Java在线学习，相信对大家一定会有所帮助的。