欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树遍历:前序,中序,后序,层序的递归以及非递归实现

程序员文章站 2022-05-16 14:21:27
...

树,是一种在实际编程中经常遇到的数据结构,它的逻辑很简单:除根节点之外每个节点都有且只有一个父节点,除叶子节点之外所有节点都有一个或多个子节点。我们说的二叉树,就是指子节点最多2个的树。

二叉树中,最重要的操作就是遍历。二叉树的遍历分为:

1.前序遍历:先访问根节点,再访问左子节点,最后访问右子节点。

2.中序遍历:先访问左子节点,再访问根节点,最后访问右子节点。

3.后序遍历:先访问左子节点,再访问右子节点,最后访问根节点。

4.层序遍历:也就是我们说的“广度优先”或者“宽度优先”遍历。先访问第一层节点,再访问第二层...直到最后一层。每一层的访问顺序都是从左到右。

在本文中,将写出二叉树的前中后序遍历的递归实现以及非递归实现,还有层序遍历的实现。

 

首先,我们给出二叉树的定义。

typedef struct BinaryTree
{
    int _data;
    struct BinaryTree * _lchild;
    struct BinaryTree * _rchild;
}Tree,*pTree;

可以看到,一个树中节点结构包括值域,左孩子节点和右孩子节点。叶子节点的左右孩子为空。

然后是三种遍历的递归实现。

 

  • 前序遍历的递归实现
void PreOrderRecursion(pTree node)
{
    if(node == nullptr)    return;
    cout<<node->_data<<" ";
    PreOrderRecursion(node->_lchild);
    PreOrderRecursion(node->_rchild);
}

从根节点开始,先打印出根节点的值,再递归左子树,最后递归右子树。

中序、后序遍历的思想和前序一样,只需要调整打印的顺序即可,所以下面不再赘述。

void InOrderRecursion(pTree node)
{
    if(node == nullptr)    return;
    InOrderRecursion(node->_lchild);
    cout << node->_data<<" ";
    InOrderRecursion(node->_rchild);
}

void PostOrderRecursion(pTree node)
{
    if(node == nullptr)    return;
    PostOrderRecursion(node->_lchild);
    PostOrderRecursion(node->_rchild);
    cout << node->_data<<" ";
}

 

 

接下来是三种遍历的非递归实现。我们说到其实递归的本质就是栈,既然不使用递归,那么我们就要用到栈。

其中,前序遍历和中序遍历的思想也十分相似,只是后序遍历有些许不同。

此处前序遍历的非递归有两种实现,思想有些许不同。

 

前序遍历的非递归实现方法1:

思想:使用栈,首先判断输入合法性。随后将头节点首先入栈 ,保证栈中开始至少有一个元素。使用一个while循环,只要栈还非空就一直进行。循环体中首先获取栈顶节点,将其打印后直接出栈,并将其的右孩子和左孩子依次入栈(如果存在的话)。根据栈的FILO特性,最后入栈的左孩子将在下一轮中成为栈顶元素。这样就能满足前序遍历的特点。

void PreOrderIteration1(pTree node)
{
    if(node == nullptr)    return;
    stack<pTree> s;
    pTree p = node;
    s.push(p);
    
    while(!s.empty())
    {
        p = s.top();
        cout<<p->_data<<" ";
        s.pop();

        if(p->_rchild)    s.push(p->_rchild);
        if(p->_lchild)    s.push(p->_lchild);
    }
}

前序遍历非递归实现方法2:

思想:循环开始,从栈顶节点(除第一次是根节点)开始不断左探,入栈并打印,直到左孩子为空;然后指针指向栈顶元素的右孩子,开启下一轮循环。

void PreOrderIteration2(pTree node)
{
    stack<pTree> s;
    pTree p = node;

    while(!s.empty() || p != nullptr)
    {
        while(p != nullptr)            //不断左探的过程
        {
            cout<< p->_data << " ";
            s.push(p);
            p = p->_lchild;
        }

        if(!s.empty())                //最后访问右孩子
        {
            p = s.top();
            s.pop();
            p = p->_rchild;
        }
    }
}

总地来说,还是第一种方法更好理解也便于记忆。

中序遍历非递归实现:

思想:与前序遍历非递归方法2的思想相同,只是不在不断左探的时候打印,而是在出栈的时候打印。

void InOrderIteration(pTree node)
{
    if (node == nullptr)     return;
    pTree p = node;
    stack<pTree> s;
    while(!s.empty() || p != nullptr)
    {
        while(p != nullptr)
        {
            s.push(p);
            p = p->_lchild;
        }
        if(!s.empty())
        {
            p = s.top();
            cout << p->_data <<" ";
            s.pop();
            p = p->_rchild;
        }
    }
}

后序遍历非递归实现:

思想:相对于前序和中序,后续遍历的实现就稍显麻烦。我们要保证一个节点要在左孩子和右孩子之后才能访问,那么有下面三种情况:

1.它是叶子节点,没有左右孩子。可以直接访问。

2.它有左右孩子,但是左右孩子都已经被访问过,也可以直接访问该节点。

3.有左右孩子,且左右孩子没有访问过。此时要先入栈右孩子,再入栈左孩子。

为了确认一个节点的左右孩子是否被访问过,我们就要定义一个pPre指针。访问过一个节点后,就将pPre指向它,在下一轮判断就可以通过p->lchild || p->rchild  == pPre来作为子节点是否被访问过的条件了。

void PostOrderIteration(pTree node)
{
    pTree pCur = node;        //用来保存当前节点的指针
    pTree pPre = nullptr;     //保存上一个访问的节点的指针
    stack<pTree> s;
    s.push(pCur);
    
    while(s.!empty())
    {
        pCur = s.top();
        if((pCur->_lchild == nullptr && pCur->_rchild == nullptr) ||              //没有左右孩子的情况
           (pPre != nullptr && (pPre == pCur->_lchild || pPre == pCur->_rchild))) //左右孩子访问过的情况
        {
            cout << pCur->_data << " ";
            s.pop();
            pPre = pCur;
        }
        else
        {
            if(pCur->_rchild != nullptr)    s.push(pCur->_rchild);
            if(pCur->_lchild != nullptr)    s.push(pCur->_lchild);
        }
    }
}

 

最后是层序遍历。和其他三种遍历不同的是,层序遍历使用队列来实现。先进先出也很符合层序遍历的特点。

void LevelOrder(pTree node)
{
    pTree p = node;
    if(node == nullptr)    return;
    queue<pTree> q;
    for(q.push(p);q.size();q.pop())        //只要队列不空就一直出队
    {
        p = q.front();
        cout << p->_data <<" ";
        if(p->_lchild)    q.push(p->_lchild);
        if(p->_rchild)    q.push(p->_rchild);
    }
}