武汉软件工程职业学院《数据结构讲义》第14讲-2叉树、树和森林.docVIP

武汉软件工程职业学院《数据结构讲义》第14讲-2叉树、树和森林

第四章树

第四章树

第十四

第十四讲二叉树、树和森林

1．掌握树的存储结构。

2．掌握树／森林与二叉树的相互转换，

3.树的遍历方法。

教学重点：

树／森林与二叉树的相互转换

教学难点：

树／森林与二叉树的相互转换

授课内容

4.5二叉树、树和森林

4.5.1树的存储结构

树的存储结构有多种形式。下面介绍三种常用的存储结构。

双亲数组表示发

这种存储结构是利用每个结点（除根结点外）只有唯一双亲的特点，用一维数组来存储一棵一般的树。图4－5－1便是一棵树及其双亲表示的存储结构。在这种结构中，寻找一个结点的双亲时，只要访问它的parent域，便可立即得到它的双亲的存储位置；但是，若要寻找一个结点的孩子时，则需遍历整个数组。

A

A

F

H

BCD

E

G

I

J

5

J

5

I

5

H

3

G

1

F

1

E

0

D

0

C

0

B

-1

A

0

1

2

3

4

5

6

7

8

9

图4－5－1树的双亲表示法

结点定长的孩子链表表示法

图4－5－1所示的树，它是一个三叉树，可用三叉链表来存储。其结点结构为：一个数据域和三个指针域。指针域用于指向该结点的各个孩子结点。该树的三重链表如图4－5－2(a)所示。

孩子－兄弟二叉链表表示法

进行整理。把虚线改为实线，把结点按层次排列。

二叉树还原为一般树的示例，如图4－5－4所示。

A

A

I

F

H

G

J

D

E

A

B

I

F

H

G

J

CD

E

A

I

F

H

G

J

D

E

A

I

F

H

G

J

D

E

图4－5－4二叉树还原为一般树

B

BE

C

I

I

I

I

B

C

C

B

4.5.3森林与二叉树的转换

森林是树的有限集合，如图4－5－5（a）所示。

森林转换为二叉树

森林转换为二叉树的步骤为：

将森林中每棵子树转换成相应的二叉树，形成有若干二叉树的森林。

按森林中树的先后次序，依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树，这样整个森林就生成了一棵二叉树。实际上第一棵树的根结点便是生成后的二叉树的根结点。图4－5－5是森林转化为二叉树的示例。

(a)

(a)一般树的森淋

A

BC

D

F

G

F

H

IJ

K

A

C

D

F

BGI

F

H

J

K

A

C

D

F

G

BFI

H

J

K

A

C

D

F

G

BF

H

J

K

(b)二叉树的森林

(c)第二棵树并入第一棵树

(d)最终结果

图4－5－5森林转换为二叉树

I

二叉树还原为森林

将一棵由森林转换得到的二叉树还原为森里的步骤是：

抹线。将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去，这样就得到包含有若干棵二叉树的森林。

还原。将每棵二叉树按二叉树还原为一般树的方法还原为一般树，即得到森林。

这部分的图示，请读者自己练习画出。