电脑系统制作方法

第六章 树和二叉树前面我们学习的线性数据结构，每个 元素都有唯一的前驱(第一个除外)和后 继(最后一个除外),但是在现实应用中， 一些问题的数据元素之间的关系就不这样 简单，例如元素有多个前驱、多个后继。 本章学习一种非线性数据结构一树， 数据元素之间是一种层次关系，元素有且 只有一个前驱，但可以有多个后继。

数据结构课程的内容一对多 (1:n)

第六章 树和二叉树

树的概念和基本术语 二叉树 二叉树遍历 线索二叉树 树与森林 霍夫曼树

6.1树的概念和基本术语树的定义树是由 n (n 0) 个结点的有限集合。如 果 n = 0,称为空树；如果 n > 0,则 有且仅有一个特定的称之为根(Root)的结 点，它只有直接后继，但没有直接前驱； 当n > 1,除根以外的其它结点划分为 m (m >0) 个互不相交的有限集 T1, T2 ,…, Tm, 其中每个集合本身又是一棵树，并且称为 根的子树(SubTree)。

例如AA

B

C

D I J

只有根结点的树K

EL

F

G HM

有13个结点的树 其中:A是根,其余结点分成三个互不相交的子集， T1={B,E,F,K,L}; T2={C,G}; T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树

树的基本术语树的结点：包含一个数据元素及若干指向子树 的分支； 孩子结点：结点的子树的根称为该结点的孩子 双亲结点：B结点是A结点的孩子，则A结点是B 结点的双亲； A 兄弟结点：同一双亲的孩子 结点； B C D 堂兄结点：双亲在同一层的 结点互为堂兄弟。 E F G H I J 结点层：根结点的层定义为1; K L M 根的孩子为第二层结点，依 此类推；

树的高度：树中结点的最大层次. 结点的度：结点子树的个数 树的度： 树内各结点的度的最大值。 叶子结点：也叫终端结点，是度为0的结点； 分枝结点：度不为0的结点； 有序树：子树有序的树，(子树不能互换) 如：家族树； A 无序树：不考虑子树的顺序；B C D I J

EK L

F

G HM

森林：是m(m≥0)棵互 不相交的树的集合

root

FB

AC D

EK

FL

G

H

I

JM

任何一棵非空树是一个二元组 Tree = (root,F) 其中：root 被称为根结点， F 被称为子树森林

路径：树中的k 个结点n1,n2,… ,nk,满 足ni 是ni + 1 的双亲，n1到nk有一条路径 路径长度：分支数=路径上结点个数一1 注意 根没有双亲，叶子没有孩子； vi是vj 的双亲，则L ( vi ) = L(vj)- 1 ; 堂兄弟的双亲是兄弟关系吗？ 有序树和无序树的区别；AB E K L F C G H M D I J

对比树型结构和线性结构的结构特点 树型结构 线性结构 第一个数据元素 (无前驱) 根结点 (无前驱)

最后一个数据元素 (无后继) 其它数据元素 (一个前驱、 一个后继)

多个叶子结点 (

无后继)其它数据元素 (一个前驱、 多个后继)

1. 如图所示的树回答下面题： 1)哪个是根结点？ 2)哪些是叶子结点？ 3)哪个是E的父结点？ 4)哪些是E的子孙点？ B 5)哪些是E的兄弟结点？哪 些是C的兄弟结点？ 6)结点B和结点I的层数分别 D 是多少？ 7)树的深度是多少？ 8)以结点G为根的子树的深 H 度是多少？ 9)树的度是多少？

A ○ C ○ E F G ○○ ○

○

○

I J ○ ○ ○

树的常见表示方法1.直观表示法：用圆圈表示结点，元素写在 圆圈中，连线表示元素之间的关系.根在上， 叶子在下(即树向下生长)

2 、集合表示法： 根据树的集合定义，写出集合划分。

3 、文氏图表示法： 集合表示的一种直观表示，用图表示集合。

4 、目录表示法： 将一棵树描述为一本书，书--章--节--小节

5 、广义表表示法： 将一棵树描述为一个广义表，子树就对应子 表。

人们最常用的是第一种，但是不适合计算机！

树的基本操作 InitTree(&T); 操作结果：构造空树T。 DestroyTree(&T); 初始条件：树T存在。 操作结果：销毁树T。 CreateTree(&T,definition) 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree(&T); 初始条件：树T存在。 操作结果：将树T清为空树。