【面试题之算法部分】二叉树的遍历

时间：2021-07-26 14:21:58

本篇文章主要目的是详细讨论二叉树的前序、中序和后序遍历算法，包括递归版和迭代版。首先给出递归版的一般思想：

  • 前序遍历：先访问根节点，前序遍历左子树，前序遍历右子树。
  • 中序遍历：中序遍历左子树，访问根节点，中序遍历右子树。
  • 后序遍历：后序遍历左子树，后序遍历右子树，访问根结点。

我们首先定义节点的结构

typedef struct node{
int val;
    node *lChild;
    node *rChild;
}BiTree；

一. 前序遍历

递归版本：

void PreOrder(BiTree* T)
{
if(!T) return;
    visit(T); //访问根节点的值
    PreOrder(T->lChild); //递归访问左子树
    PreOrder(T->rChild); //递归访问右子树
}

visit(Bitree *T)
{
    cout << T->val << " "　<< endl;
}

递归版本的时间复杂度为O(n)，但是由于空间复杂度的常系数较迭代版本更高，我们可以改用等效迭代版本。

迭代版本1：

#define HasRChild(x) ((x).rChild)
#define HasLChild(x) ((x).lChild)

void PreOrder(BiTree *T)
{
stack<BiTree *> s;
if(T) s.push(T);
while(!s.empty())
    {
        T = s.top();
        s.pop();
        visit(T); //每次先访问根节点
if(HasRChild(*T)) s.push(T->rChild); //将右孩子入栈
if(HasLChild(*T)) s.push(T->lChild); //将左孩子入栈
    }
}

迭代版本2：

我们先沿最左侧通路自顶向下访问访问沿途节点，再自底而上一次遍历这些节点的右子树。其实遍历过程和迭代版本1大同小异。

void visitAlongLeftBranch(BiTree *x, stack<BiTree *> &s)
{
while(x)
    {
        visit(x);
if(x->rChild) s.push(x->rChild);
        x = x->lChild;
    }
}

void PreOrder(BiTree *x)
{
stack<BiTree *> s;
while(true)
    {
        visitAlongLeftBranch(x, s);
if(s.empty()) break;
        x = s.top();
        s.pop();
    }
}

二. 中序遍历

注意二叉查找树的中序遍历是数据的升序过程。

递归版本：

void InOrder(BiTree *T)
{
if(!T) return;
    Inorder(T->lChild);
    visit(T);
    InOrder(T->rChild);
}

将中序遍历递归版本改成迭代版本的难度在于：尽管右子树的递归是属于严格尾递归的，但是右子树的递归并不是，我们可以参看前序遍历迭代版本2的思想。

迭代版本1：

void visitAlongLeftBranch(BiTree *x, stack<BiTree *> s)
{
while(x)
    {
        s.push(x);
        x = x->lChild;
    }
}
void InOrder(BiTree *x)
{
stack<BiTree *> s;
while(true)
    {
        visitLongLeftBranch(x, s); //不断将左侧节点入栈
if(s.empty()) break;
        x = s.top();
        s.pop();
        visit(x); //自底向*问左侧节点
        x = x->rChild; //进入右子树
    }
}

进一步优化，可将上面的两个while循环改成一个循环
迭代版本2

void InOrder(Bitree *x)
{
stack<Bitree *> s;
while(true)
    {
if(x)
        {
            s.push(x);
            x = x->lChild;
        }
else
        {
if(!empty())
            {
                x = s.top();
                s.pop();
                visit(x);
                x = x->rChild;
            }
else break;
        }
    }
}

以上版本都需要辅助栈，尽管时间复杂度没有什么实质影响，但所需的空间复杂度正比于二叉树的高度，最坏情况下将达到O(n)(退化成单链)。为此，我们继续优化，如果node节点内有parent指针，我们借助parent指针来实现。基于一个事实：中序遍历中前后元素关系满足调用succ()函数（寻找其直接后继的函数）前后两元素的关系。
简单来讲，假设我现在遍历到节点A，按中序遍历下一个节点是B。那同样，我对A调用succ()后返回的节点一定也是B。

void Inorder(BiTree *x)
{
    bool backtrace = false;
while(true)
    {
if(!backtrace && x->lchild) x = x->lChild;
else
        {
            visit(x);
if(x->rChild)
            {
                x = x->rChild;
                backtrace = false;
            }
else
            {
if(!(x = succ(x))) break;
                backtrace = true;
            }
        }
    }
}

//直接后继函数
BiTree* succ(BiTree* x)
{
if(x->rChild) //如果存在右子树，则直接后继是右子树中的最左子孙
    {
        x = x->rChild->lChild;
while(x) x = x->lChild;
    }
else //如果不存在右子树，则直接后继是“包含x节点于左子树中的最低祖先”
    {
while(x == x->parent->rChild) x =  x->parent;
        x = x->parent;
    }
}

三. 后序遍历

递归版本:

void PostOrder(Bitree *T)
{
if(!T) return;
    PostOrder(T->lChild);
    PostOrder(T->rChild);
    visit(T);
}

迭代版本：

在后序遍历算法的递归版中，由于左、右子树递归遍历均严格的不属于尾递归，因此实现对应的迭代式算法难度更大，不过，仍可套用之前的思路。
我们思考的起点依然是，此时首先访问哪个节点？如下图所示，从左侧水平向右看去，未被遮挡的最高叶节点v——称作最高左侧可见节点（HLVFL）——即为后序遍历首先访问的节点。注意，该节点有可能是左孩子，也有可能是右孩子。故图中以垂直边示意它与其父节点的联边。
【面试题之算法部分】二叉树的遍历

考察连接于v与树根之间的唯一通路（粗线所示），与先序和中序遍历类似，自底而上沿着该通路，整个后序遍历也可以分解为若干个片段。每个片段，分别起始于通路的一个节点，并包括三步： 访问当前节点；遍历其右兄弟（若存在）为根的子树；以及向上回溯至父节点（若存在）并转入下一片段。
基于以上理解，导出迭代式后序遍历算法：

void gotoHLVFL(stack<BiTree *> &s) //以s栈节点为根的子树中，寻找最高左侧可见节点（HLVFL）
{
while(BiTree *x = s.top()) //自顶向下，反复检查当前节点(即栈顶)
    {
if(HasLChild(*x)) //尽可能向左
        {
if(HasRChild(*x)) s.push(x->rChild); //若有右孩子，优先入栈
            s.push(x->lChild); //然后才转至左孩子
        }
else s.push(x->rChild); //实不得已才向右
    }
    s.pop(); //返回前弹出在栈顶的空节点
}

PostOrder(Bitree *x)
{
stack<Bitree *> s;
if(x) s.push(x);
while(!s.empty())
    {
//如果栈顶元素非当前元素之父，则必为当前元素的右兄弟，所以需要递归以右兄弟为根的树，继续寻找最高左侧可见节点（HLVFL）
if(s.top() != x->parent) gotoHLVFL(s); 
        x = s.top();
        s.pop();
        visit(x);
    }
}

参考文献：
《数据结构c++语言版》，邓俊辉
标签：

相关文章