第三讲 树(上)

3.1 树与树的表示

1.查找

查找是指根据某个给定关键字K,从集合R中找出关键字与K相同的记录。它分为以下两类:

(1)静态查找:集合中记录是固定的,没有插入和删除操作。

(2)动态查找:集合中记录是动态变化的,除了查找,还可能发生插入和删除。

首先举一个顺序查找的例子。此例需要注意,其设置了一个哨兵,因此可以减少判断中的一个条件。这个例子要求是在Element[1]~Element[n]中查找关键字为K的数据元素,其结构体如下:

则查找算法代码如下:

时间复杂性O(n)。

再举一个二分查找的例子。二分查找遵循以下要求:假设n个数据元素的关键字满足有序,并且是连续存放。

例如,假设有13个数据元素,按照关键字由小到大顺序存放,二分查找关键字为444的数据。

5

16

39

45

51

98

100

202

226

321

368

444

501

理论步骤是如表1.1所示。

表1.1 二分法步骤

left

right

mid

value

comparsion

1

13

7

100

100<444,右侧

8

13

10

321

321<444,右侧

11

13

12

444

444=444,结束

程序代码如下:

时间复杂度是O(logN)

2.树的定义和术语

树(Tree):n(n≥0)个结点构成的有限集合。当n=0时,称为空树。

对于任一棵非空树(n>0),它具备以下性质:

(1)树种有一个称为根的特殊结点,用r表示;

(2)其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,称为原来树的“子树”。

(3)子树是不相交的;

(4)除了根结点外,每个结点有且只有一个父节点;

(5)一棵N个结点的树有N-1条边。

树的一些基本术语:

(1)结点的度:结点子树个数。

(2)树的度:树的所有结点中最大的度数。

(3)叶结点:度为0的结点。

(4)父结点:有子树的结点是其子树的根结点的父结点。

(5)子结点:若A结点是B结点的父结点,则称B结点是A结点的子结点。

(6)兄弟结点:具有同一父结点的各结点彼此是兄弟结点。

(7)路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,…nk,其中ni是ni+1的父结点。路径所包含边的个数为路径的长度。

(8)祖先结点:沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。

(9)子孙节点:某一结点的子树中的所有结点是这个结点的子孙。

(10)结点的层次:规定根结点在1层,其它任一结点的层数是其父结点的层数加1。

(11)树的深度:树种所有结点总的最大层次是这棵树的深度。

3.树的表示

    数组、链表都是很难表示树的,因为树的结构是多变的,无法统一规定。因此在这里用“儿子-兄弟表示法”,结构如下面所示。

Element

FirstChild

NextSibling

如图1左所示的树结构可以表示为图1右所示的表示法。

 1524538762128265.jpg

图1

把这个树往右转向45°,可以看出,这是一个度为2的树。这种方法也被称为——二叉树

3.2 二叉树

1.二叉树的定义

    二叉树T:一个有穷的结点集合。这个集合可以为空。若不为空,则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

二叉树的五种基本形态如图2所示,几种特殊二叉树如图3所示。

1524538779384852.jpg 

图2

1524538792735225.jpg 

图3

对完全二叉树左一个说明。完全二叉树可以是满二叉树缺少最低一层最右侧几个,只要前面都对的起来即可,但是绝不能在中间缺几个(如图3右下角)

2.二叉树的几个重要性质

(1)一个二叉树第i层的最大结点数为:2i-1,i≥1。

(2)深度为k的二叉树最大节点数是2k-1,k≥1。

(3)对任何非空二叉树T,若n0表示叶结点的个数,n2是度为2的非叶结点个数,那么两者满足n0=n2+1。

3.二叉树的抽象数据类型定义

类型名称:二叉树

数据对象集:一个有穷的结点集合。若不为空,则由根结点和其左、右二叉子树组成。

操作集:BT∈BinTree,Item∈ElementType,重要的操作有:

    (1)Boolean IsEmpty(BinTree BT):判断BT是否为空;

(2)void Traversal(BinTree BT):遍历,按某顺序访问每个结点;

(3)BinTree CreatBinTree():创建一个二叉树。

二叉树常用的便利方法有:

(1)void PreOrderTraversal(BinTree BT):先序——根、左子树、右子树;

(2)void InOrderTraversal(BinTree BT):中序——左子树、根、右子树;

(3)void PostOrderTraversal(BinTree BT):后序:左子树、右子树、根;

(4)void LevelOrderTraversal(BinTree BT):层次遍历:从上到下、从左到右。

4.二叉树的存储结构

(1)顺序存储结构

完全二叉树:按从上至下、从左到右顺序存储,n个结点的完全二叉树的结点父子关系,可以使用顺序存储结果。如图4所示。

 4.jpg

图4

这个完全二叉树很有规律,很容易找到其父结点和子结点。我们可以发现:

①非根节点(序号i>1)的父结点的序号是[i/2](在这里[]表示取整);

②结点(序号为i)的左孩子结点序号为2i(若2i>=n,就没有左孩子);

③结点(序号为i)的右孩子结点序号为2i+1(若2i+1>=n,就没有右孩子)。

推广来说,一般二叉树也可以采用这种结构,方法就是通过补空位使其变成完全二叉树。但这样的结果是会造成空间浪费。

(2)链表存储

一般二叉树的结点可以用下面的方式表示:

Left

Data

Right

其代码表示如下:

5.二叉树的递归遍历

(1)先序遍历

遍历过程为:

①访问根结点;②先序遍历其左子树,先序遍历其右子树。

程序如下所示:

(2)中序遍历

遍历过程为:

①中序遍历其左子树;②访问根结点;③中序遍历其右子树。

程序如下所示:

(3)后序遍历

便利过程:

①后续遍历其左子树;②后续遍历其右子树;③访问根结点。

代码如下:

6.二叉树的非递归遍历(以中序为例)

基本思路:使用堆栈

如图5所示的二叉树,我们以此未来来介绍利用堆栈进行处理的方法,输出顺序为:DBEFAGHCI。处理的方法见表3.1所示。

5.jpg 

图5

表3.1 使用堆栈算法的表格示意

序号

当前结点

堆栈(从左到右相当于从底到顶)

步骤说明

1

A

[A]

首先把A压入堆栈

2

B

[AB]

B为A的左孩子,压入堆栈

3

D

[ABD]

D为B的左孩子,压入堆栈

4

[AB]

D无孩子,将D推出堆栈

5

[A]

B推出堆栈

6

F

[AF]

由于F为B右孩子,在B推出时将F压入堆栈

7

E

[AFE]

E为F左孩子,压入堆栈

8

[AF]

E无孩子,将E推出堆栈

9

[A]

将F推出堆栈

10

[]

将A推出堆栈

11

C

[C]

将G压入堆栈

12

G

[CG]

G为C的左孩子,压入堆栈

13

[C]

G没有左孩子,G推出堆栈

14

H

[CH]

将G的右孩子压入堆栈

15

[C]

H无孩子,H推出堆栈

16

 []

将C推出堆栈

17

I

[I]

将I压入堆栈

18

[]

将I推出堆栈

具体执行代码如下:

同理可得,中序遍历为:

7.层序遍历

层次遍历是利用队列的方式进行。遍历从根结点开始,首先将根结点指针入队,然后开始执行下面三个操作:

(1)从队列中取出一个元素;

(2)访问该元素所指结点;

(3)若钙元素所指结点的左、右孩子结点费控,则将其左、右孩子的指针顺序入队。

不断执行这三步操作,直到队列为空,再无元素可取,二叉树的层序遍历就完成了。其代码如下所示:

8.遍历应用的例子

【例1】遍历二叉树的应用:输出二叉树中的叶子结点。

【例2】求二叉树的高度。

【例3】二元运算表达式树及其遍历

如图6所示。

6.jpg

图6

三种遍历可以得到三种不同的访问结果:

(1)中序遍历得到中缀表达式:a + b * c + d * e + f * g

(2)先序遍历得到前缀表达式:+ + a * b c * + * d e f g

(3)后序遍历得到后缀表达式:a b c * + d e * f + g * +

由此直接将表达式存入链表就可以了。

【例4】由两种遍历序列确定二叉树:已知三种遍历中的任意两种遍历序列,能否唯一确定一棵二叉树呢?

只需要确保其中一个是中序遍历,就可以唯一确定。如果只有前序遍历、后序遍历,这就不可能找到唯一的。

下面以先序和中序遍历序列来确定一棵二叉树。

先序遍历序列的第一个结点就是根结点。这个根结点能够在中序遍历序列中将其余结点分割成两个子序列,根结点前面部分是左子树上的结点,而根结点后面的部分是右子树上的结点。

根据这两个子序列,在先序序列中找到对应的左子序列和右子序列,它们分别对应左子树和右子树。

然后对左子树和右子树分别递归使用相同的方法继续分解。

9.二叉树的创建

    由于树是非线性结构,创建一棵二叉树必须首先确定树种结点的输入顺序,常用的方法是先序创建层序创建两种。