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

2018-12-17 11:06王爱法杨梅梅福春霞
重庆理工大学学报(自然科学) 2018年11期
关键词:二叉树指针结点

王爱法, 杨梅梅,福春霞

(重庆理工大学 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 结束语

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

猜你喜欢
二叉树指针结点
LEACH 算法应用于矿井无线通信的路由算法研究
基于八数码问题的搜索算法的研究
二叉树创建方法
垂悬指针检测与防御方法*
为什么表的指针都按照顺时针方向转动
一种由层次遍历和其它遍历构造二叉树的新算法
一种由遍历序列构造二叉树的改进算法
浅析C语言指针
基于单链表的二叉树非递归遍历算法