二叉树的递归遍历和非递归(循环)遍历实现


二叉树的递归遍历和非递归(循环)遍历实现

struct BinTree
{
    int data;
    BinTree * left;
    BinTree * right;
};

递归版本

void PreOrder(BinTree * root)
{
    if(root != nullptr)
    {
        cout << root->data;
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

循环版本

  1. 访问节点 p 并将节点 p 入栈
  2. 判断节点 p 的左孩子是否为空，若不为空，则输出左孩子，并将 P 指向新的左孩子，直至左孩子为空
  3. 若左孩子为空，这时候左孩子的父节点都已经输出完毕，此时父节点在栈中，因此将 p 指向出栈的节点的右孩子，遍历右分支
  4. 直至指针为空并栈为空，遍历结束
  5. 中序遍历只需要调整输出语句即可
void PreOrder(BinTree * root)
{
    stack<BinTree *> s;
    BinTree *p = root;
    while(p != nullptr || !s.empty())
    {
        while(p != nullptr)
        {
            cout << p->data << " ";
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

后序遍历的循环实现难一些

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

void postOrder(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中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

本文永久更新链接地址：

相关内容