文档介绍：树的定义和基本术语
基本术语:
树的表示形式
二叉树
特点
1、每个结点最多有两个孩子(二叉树中不存在度大于 2 的结点) 。
2、子树有左右之分,其次序不能颠倒。
3、二叉树可以是空集合,根可以有空的左子树或空的右子树。
定义:
二叉树不是树的特殊情况,它们是两个概念。
注
二叉树的 5 种基本形态
(a)
空二叉树
A
A
B
A
B
A
C
B
(b)
根和空的
左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
二叉树的性质
性质 1: 在二叉树的第 i 层上至多有 2 i - 1 个结点(i ≥1)。
性质 2:深度为 k 的二叉树至多有 2k-1 个结点(k ≥1)。
性质 3:对任何一棵二叉树 T,如果其叶子数为 n0,度为 2 的结
点数为 n2,则 n0 = n2 + 1。
完全二叉树的性质
性质 4:具有 n 个结点的完全二叉树的深度为log2n+ 1。
性质 5: 如果对一棵有 n 个结点的完全二叉树(深度为log2n+1)
的结点按层序编号(从第 1 层到第log2n+1 层,每层从
左到右),则对任一结点 i (1≤i≤n),有:
(1) 如果 i = 1,则结点 i 是二叉树的根,无双亲;如果 i >1,
则其双亲是结点i / 2。
(2) 如果 2i > n,则结点 i 为叶子结点,无左孩子;否则,其
左孩子是结点 2i。
(3) 如果 2i + 1 > n,则结点 i 无右孩子;否则,其右孩子是
结点 2i + 1。
二叉树的存储结构
1、顺序存储结构
顺序存储结构仅适用于完全二叉树。
2、链式存储结构
lchild data rchild
结点结构
A
B
C
D
E
F
G
A
B
C
D
E
F
G
^
^
^
^
^
^
^
^
在 n 个结点的二叉链
表中,有 n+1个空指针域。
遍历二叉树和线索二叉树
遍历二叉树(重点,是进行其他运算的基础)
先序、中序、后序
线索二叉树
二叉树线索化的目的:利用线索化后的二叉树中的线索就可
以直接找到某些结点在某种遍历序列中的前趋和后继结点。
二叉树线索化的实质:在遍历过程中用线索取代空指针。
在线索树上进行遍历的方法:
1 、从序列中的第一个结点起,依次找后继,直至后继为空。
2 、从序列中的最后一个结点起,依次找前驱,直至前驱为空。
在线索树(中序)中找结点后继的方法:
1 、若右链是线索,则直接指示后继;
2 、若右链是指针,则“右孩找左”。
即:中序后继右孩找左。
在线索树(中序)中找结点前驱的方法:
1 、若左链是线索,则直接指示前驱;
2 、若左链是指针,则“左孩找右”。
即:中序前驱左孩找右。
树和森林
树的存储结构
1 双亲表示法
特点:找双亲容易,找孩子难。
2 孩子表示法(树的链式存储结构)
d 叉树的结点结构
data child1 child2 …… childd
data child1 child2 …… childd parent
1) 多重链表:每个结点有多个指针域,分别指向其子树的根。
d 叉链表
d +1 叉链表
多重链表
A
B ^ ^ ^
C ^ ^ ^
D ^
E ^ ^ ^
F ^ ^ ^
A ^
B ^ ^ ^
C ^ ^ ^
D ^
E ^ ^ ^
F ^ ^ ^
在有 n 个结点、度为 d 的树的 d
叉链表中,有 n×(d-1)+1 个空链域。
结点同构:
结点的指针个
数相等,为树
的度 d 。
A
B
C
D
E
F
A 3
B 0
C 0
D 2
E 0
F 0
节约存储空间,但操作不方便。
结点不同构:
结点的指针个数
不相等,为该结
点的度 d 。
A 3 ^
B 0
C 0
D 2
E 0
F 0
A
B
C
D
E
F