第 8 章 树和二叉树
树
二叉树
二叉树设计
二叉树遍历
线索二叉树
哈夫曼树
等价问题
树与二叉树的转换
树的遍历
主
要
知
识
点
8.1 树
1.
1.
树的定义
树的定义
树是由 n(n≥0) 个结点组成的有限集合 T 。 n=0 的树称为
空树；对 n>0 的树，有 :(1) 仅有一个特殊的结点称为根结点，
根结点没有前驱结点； (2) 当 n>1 时，除根结点外其余的结点
分为 m(m>0) 个互不相交的有限集合 T
1
,T
2
，…， T
m
，其中每
个集合 T
i
本身又是一棵结构和树类似的子树。
注：树的定义具有递归性，即“树中还有树”。
若干术语
若干术语
结点：由数据元素和构造数据元素之
间关系的指针组成
A
B
C
G
E
I
D
H
F
J
FLK
结点的度：结点所拥有的子树的个数
叶结点：度为 0 的结点，也称作
终端结点
分支结点：度不为 0 的结点
孩子结点：树中一个结点的子树的根结点
双亲结点：若树中某结点有孩子结点，则这个结点就
称作它的孩子结点的双亲结点
兄弟结点：具有相同的双亲结点的结点
树的度：树中所有结点的度的最大值
结点的层次：从根结点到树中某结点所经路径上的分支数
树的深度：树中所有结点的层次的最大值
无序树：树中任意一个结点的各孩子结点之间的次序
构成无关紧要的树
有序树：树中任意一个结点的各孩子结点有严格排列
次序的树
森林： m （ m≥0 ）棵树的集
合
2.
2.
树的表示方法
树的表示方法
(1) 直观表示法
(2) 形式化表示法
(3) 凹入表示法
