二叉树及其遍历算法的应用

王爱法， 杨梅梅，福春霞

(重庆理工大学 a.理学院; b.期刊社， 重庆 400054)

同一数据元素类中的数据元素之间的关系表示数据结构。它有4种常见的结构：集合、树结构、线性结构和图形结构。在计算机中，树是一种表示元素层次和分支的非线性结构。树形结构是一种常用的、重要的数据结构，在日常生活与学习中得到了广泛的应用，比如判断家族关系、部门机构设置等[1-6]。二叉树是树形结构的一种，二叉树是一个连通的无环图，由一个根元素和左子树、右子树构成[2-16]。

遍历是指沿着某条特定的路线来搜索，对树中各个结点依次做一次访问，要将所有结点都遍历一次方可结束。许多树的应用都是基于树的遍历来实现的，例如查找元素、插入元素等。二叉树的基本的遍历规则有3种：前序遍历、中序遍历和后序遍历。对于每一种遍历，树中每个结点都要经过3次。前序遍历在第1次遇到结点时立即访问，中序遍历在第2次遇到结点时访问，后序遍历则在第3次遇到结点时才访问。因为树的定义本身就是递中序归定义，因此采用递归的方法去实现树的3种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在3种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对难一点。

二叉树在计算科学中有着重要的作用，如计算机操作系统中的文件管理、编译程序的语法结构和数据库系统信息组织形式等；在生活中，二叉树可以用在密码学中，利用二叉树的先序遍历、后序便利、中序遍历对密码进行加密和解密；在经济中，二叉树可以用来研究期权的定价模型。所以，二叉树及二叉树的遍历在生活中、学科学习中都有很重要的作用。下面我们着重介绍一下二叉树中序遍历的2种算法。

1 二叉树中序遍历的算法实现

二叉树中序遍历的算法实现包括递归算法和非递归算法。

1.1 递归算法

递归算法是一种直接或间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁且易于理解。

递归算法解决问题的特点：① 递归就是在过程或函数里调用自身；② 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口；③ 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低，所以一般不提倡用递归算法设计程序；④ 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

先序遍历：

Int PreOrder(BiTree T,Int(*Visit)(TElemType e))

{

if (T)

{

if (Visit(T->data))

if (PreOrder(T->lchild,Visit))

if (PreOrder(T->rchild,Visit))

return OK;

return ERROR; //函数不会执行到这一步，不会返回Error。这样写只是为了没有编译警告。

}

else

return OK; //当T为空树时，停止递归。

}

中序遍历：

Int InOrder(BiTree T,Int(*Visit)(TElemType e))

{

if (T)

{

if (InOrder(T->lchild,Visit))

if (Visit(T->data))

if (InOrder(T->rchild,Visit))

return OK;

return ERROR;

}

else

return OK;

}

后序遍历：

Int PostOrder(BiTree T,Int(*Visit)(TElemType e))

{

if (T)

{

if (PostOrder(T->lchild,Visit))

if (PostOrder(T->rchild,Visit))

if (Visit(T->data))

return OK;

return ERROR;

}

else

return OK;

}

1.2 非递归算法

二叉树的非递归遍历要借助堆栈来实现，具体算法为：

1) 设置一个堆栈进行初始化。

2) 把根节点所表示的指针入栈。

3) 当堆栈非空时，重复执行下列步骤：① 出栈会取得一个结点指针，对该结点进行访问；② 若该结点的右孩子不是空，则该结点的右子树指针进栈；③ 若该结点的左孩子不是空，则该结点的左子树指针进栈。

二叉树遍历的非递归算法相对于递归算法，减少了函数调用等开销，具有性能优势。

先序遍历：

Int PreOrder1(BiTree T,Int(*Visit)(TElemType e))

{

Stack *S; //栈S中存储指向树结点的指针。

BiTree p;

S = (Stack*)malloc(sizeof(Stack));

InitStack(S);

Push(S,T); //根指针进栈。

while (!StackEmpty(S))

{

//获取栈顶指针，如果栈顶指针不为空，访问该结点。并将该结点的左子树进栈。

if (GetTop(S,&p) && p)

{

if (!Visit(p->data))

return ERROR;

Push(S,p->lchild);

}

//栈顶指针为空，表明之前压入的左子树或者右子树为空。

else

{

Pop(S,&p); //空指针退栈

if (!StackEmpty(S))

{

Pop(S,&p); //已被访问过的根结点退栈。此时，该退栈结点的左子树已被全部访问过。

Push(S,p->rchild); //右子树进栈。

}

}

}

return OK;

}

中序遍历：

Int InOrder1(BiTree T,Int(*Visit)(TElemType e))

{

Stack *S;

BiTree p;

S = (Stack *)malloc(sizeof(Stack));

InitStack(S);

Push(S,T); //根指针进栈

while (!StackEmpty(S))

{

//向左走到尽头

while (GetTop(S,&p) && p)

{

Push(S,p->lchild);

}

//空指针退栈

Pop(S,&p);

//访问节点，并向右一步

if (!StackEmpty(S))

{

Pop(S,&p);

if (!Visit(p->data))

return ERROR;

Push(S,p->rchild);

}

}

return OK;

}

后序遍历：

Int PostOrder1(BiTree T,Int(*Visit)(TElemType e))

{

Stack *S;

BiTree p,pre=NULL;//pre指向已访问过的最后一个结点。

S = (Stack*)malloc(sizeof(Stack));

InitStack(S);

Push(S,T);//根指针进栈

while (!StackEmpty(S))

{

//获取栈顶指针，如果当前结点有左子树，并且左子树结点不是刚被访问的节点。如果当前结点有右子树，并且右子树结点不是刚被访问的结点。

//表明栈顶指针指向的树结点未被访问，且左子树和右子树均未被访问。此时，将结点的左子树进栈。

if (GetTop(S,&p) && p->lchild && pre != p->lchild && !(p->rchild && pre == p->rchild))

Push(S,p->lchild);

//如果栈顶指针的右子树存在，且未被访问。则将右子树进栈

else if (p->rchild && pre != p->rchild)

Push(S,p->rchild);

//如果左子树和右子树均被访问过，则结点退栈，并进行访问。更新pre。

else

{

Pop(S,&p);

if (!Visit(p->data))

return ERROR;

pre = p;

}

}

return OK;

}

对照递归算法和非递归算法可以发现：递归算法简洁、易懂、可读性强，程序的编写和调试也很方便，但是因为递归算法需要通过系统内部的进栈和出栈来实现，因此消耗的时间和空间多，运行效率低。非递归算法应用指针和堆栈，进行出栈和入栈的方法实现了算法，非递归算法程序总体来说较长，编写和调试要费些时间，但因为其一直在调用其他函数进行进栈出栈，所以其占用的空间较少、用时也较短。

下面通过斐波那契的列子来说明递归算法与非递归算法的效率问题。由于斐波纳契数列是以兔子的繁殖引入的，因此也叫“兔子数列”。它指的是这样一个数列：0,1,1,2,3,5,8,13,…从这组数可以明显看出这样一个规律：从第3个数开始，后边一个数一定是在其之前两个数的和。在数学上，斐波纳契数列可以用这样的公式表示：F(0)=0；F(1)=1；F(n)=F(n-1)+F(n-2),n≥2。通过时间复杂度来比较2种算法的效率：

1) 递归算法时间复杂度O(2n)

由于使用递归时，其执行步骤是：要得到后一个数，必须先计算出之前的两个数，即在每个递归调用时都会触发另外两个递归调用，例如：要得到F(10)之前得先得到F(9)、F(8)，那么得到F(9)之前得先得到F(8)、F(7)、…如此递归下去。

从图1可以看出：这样的计算是以 2 的次方增长的。除此之外也可以看到：F(8)和F(7)的值都被多次计算，如果递归的深度越深，那么F(8)和F(7)的值会被计算更多次，但是这样计算的结果都是一样的，除了其中之一外，其余的都是浪费。递归算法在空间和时间上都比较浪费，占用内存也比较大，效率低下。

图1 二叉树

2) 非递归时间复杂度O(n)

创建一个数组，每次将前两个数相加后直接赋给后一个数。这样的话，有n个数就创建一个包含n个数的一维数组，所以空间复杂度为O(n)，由于只需从头向尾遍历一边，所以时间复杂度也为O(n)。非递归算法虽然代码较复杂，但是其在进栈出栈的过程中会释放空间，时间复杂度和空间复杂度都较少，效率较高。

2 结束语

综上可知，二叉树的递归遍历的代码实现比较简单，但是一般需要调用自身，容易出错；二叉树的非递归遍历的代码实现相对复杂，但不易出错。而递归算法的时间复杂度要远远大于非递归算法的时间复杂度，所以递归算法的效率比较低，应用率低。