第 六 章 树和二叉树
6.1 树的定义和基本术语
6.2 二叉树
6.2.1 二叉树的定义
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
6.6 赫夫曼树及其应用
6.6.1 最优二叉树 (赫夫曼树 )
第六章 树和二叉树
6.1 树的定义和基本术语
?非线性数据结构 。
?树的递归定义：
?树 (tree)是 n(n>=0)个结点的有限集 。
? 当 n>0时,
? (1)有且仅有一个特定的称为根 (root)的结点 ;
? (2)当 n>1时,其余结点可分为 m(m>0)个互不相
交的有限集 T1,T2,...,Tm,其中每个集合本身又是一
棵树 。 称为 子树 (subtree)。
树的示例
空树
n=0
层次
1
2
3
4
一般的树
A
B C D
E F G H I
J K L
只有根结点
的树 n=1
A
树的抽象数据类型定义：
? ADT Tree｛
? 数据对象 D,D是具有相同特性的数据元素的集合 。
? 数据关系 R：若 D为空集, 则称为空树 ;
? 若 D仅含一个数据元素, 则 R为空集, 否则 R＝ ｛ H｝,
H是如下二元关系：
? （ 1） 在 D中存在唯一的称为根的数据元素 root,它在
关系 H下无前驱；
? （ 2） 若 D－ ｛ root｝ ≠ φ, 则存在 D－ ｛ root｝ 的一个
划分 D1,D2,...,Dm （ m＞ 0）, 对任意 j≠ k（ 1≤j,k≤ m）
有 Dj∩ Dk=φ, 且对任意的 i（ 1≤i≤ m）, 唯一存在数据
元素 xiξ Di,有 <root,xi>ξ H;
? （ 3） 对应于 D－ ｛ root｝ 的划分, H－ ｛ <root,x1>,....，
<root,xm>｝ 有唯一的一个划分 H1,H2,...,Hm （ m＞ 0）,
对任意 j≠ k（ 1≤j,k≤ m） 有 Hj∩ Hk=φ, 且对任意的 i
（ 1≤i≤ m）, Hi 是 Di上的二元关系, （ Di,{Hi}） 是一
棵符合本定义的树, 称为根 root的子树 。
树的抽象数据类型定义：
基本操作（之一）
? INITTREE（ ＆ T） ；
? 操作结果：构造空树 T。
? DESTROYTREE（ ＆ T） ；
? 初始条件：树 T存在 。
? 操作结果：销毁树 T。
? CREATETREE（ ＆ T,DEFINITION） ；
? 初始条件,DEFINITION给出树 T的定义 。
? 操作结果：按 DEFINITION构造树 T。
? CLEARTREE（ ＆ T） ；
? 初始条件：树 T存在 。
? 操作结果：将树 T清为空树 。
树的抽象数据类型定义：
基本操作（之二）
? TREEEMPTY（ T）
? 初始条件：树 T存在 。
? 操作结果：若 T为空树, 则返回 TURE,否则 FALSE。
? TREEDEPTH（ T）
? 初始条件：树 T存在 。
? 操作结果：返回 T的深度 。
? ROOT（ T）
? 初始条件：树 T存在 。
? 操作结果：返回 T的根 。
? VALUE（ T,CUR_E） ；
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：返回 CUR＿ E的值 。
树的抽象数据类型定义：
基本操作（之三）
? ASSIGN（ T,CUR_E,VALUE）
? 初始条件：树 T存在,CUR＿ E是 T中某个结点。
? 操作结果：结点 CUR_E赋值 为 VALUE。
? PARENT（ T,CUR＿ E）
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：若 CUR＿ E是 T的非根结点, 则返回它的双亲, 否则
函数值为, 空, 。
? LEFTCHILD（ T,CUR＿ E）
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：若 CUR＿ E是 T的非叶子结点, 则返回它的最左孩子,
否则返回, 空, 。
? RIGHTSIBLING（ T,CUR＿ E）
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：若 CUR＿ E有右兄弟, 则返回它的右兄弟, 否则函数
值为, 空, 。
树 的 抽 象 数 据 类型 定 义,
基本操作 （ 之四 ）
? INSERTCHILD（ ＆ T,＆ P,I,C） ；
? 初始条件：树 T存在, P指向 T中某个结点, 1≤I≤P所指结
点的度＋ 1,非空树 C与 T不相交 。
? 操作结果：插入 C为 T中 P指结点的第 I棵子树 。
? DELETECHILD（ ＆ T,＆ P,I） ；
? 初始条件：树 T存在, P指向 T中某个结点, 1≤I≤P指结点
的度 。
? 操作结果：删除 T中 P所指结点的第 I棵子树 。
? TRAVERSETREE（ T,VISIT（ ）） ；
? 初始条件：树 t存在, VISIT是对结点操作的应用函数 。
? 操作结果：按某种次序对 T的每个结点调用函数 VISIT（ ）
一次且至多一次 。 一旦 VISIT（ ） 失败, 则操作失败 。
? ｝ ADT TREE
树的基本术语（之一）
?子树 (subtree)
?结点
?结点的度 (degree)
?叶子 (leaf)(终端结点 )
?分支结点 (非终端结点 )
?树的度
A
B C D
F G H I
L
树的基本术语（之二）
? 孩子 (child)
? 双亲 (parent)
? 兄弟 (sibling)
? 堂兄弟
? 祖先
? 子孙
A
B C D
F G H I
L
树的基本术语（之三）
?子树 (subtree)
? 层次 (level)
? 深度 (depth)
? 有序树
? 无序树
? 森林, m(m>=0)棵
互不相交的树的集
合,
A
B C D
F G H I
L
6.2 二叉树
6.2.1 二叉树的定义
?二叉树 (binary tree),度不超过 2的有序树 。
?二叉树的五种基本形态
(a) 空二叉树 ; (b)仅有根结点的二叉树； (c)右子树为空的 二叉树；
(d)左、右子树均为非空的 二叉树； (e)左 子树为空 的二叉树。
(a)
A
(b)
A
(c)
A
(d)
A
(e)
6.2.2 二叉树的性质
性质 1,在二叉树的第 i层上至多有 2(i-1)个结点 (i>=1).
?性质 2,深度为 k的二叉
树至多有 2k-1个结点
(k>=1).
? k-1
? Nk = ∑ 2 i = 2k-1
? i = 0
?性质 3:对任何一棵二叉
树 T,如果其叶结点数为
n0,度为 2的结点数为 n2,
则 n0 = n2 + 1,一般的二叉树
A
B D
E F H I
J K L
层次
1
2
3
4
满二叉树的定义,
?一棵深度为 k且
有 2k-1个结点
的二叉树称为
满二叉树 。
?k = 3
?k = 4
1
2 3
4 5 6 7
8 9 1410 11 1512 13
完全二叉树的定义,
? 深度为 k的, 有 n个结点的二叉树,
? 当且仅当其每一个结点都与深度为 k的
满二叉树中编号从 1至 n的结点一一对应时,
? 称之为完全二叉树 。 1
2 3
4 5 6
完 全 二 叉 树 和
非完全二叉树举例,
1
2 3
4 5 6 7
8 9 10 11 12
完全二叉树
1
2 3
4 5 6
非完全二叉树
完全二叉树
?性质 4：
?具有 n个结点的完全二叉树的深度为 [log2n]*+1。
?性质 5：
? 如果对一棵有 n个结点的完全二叉树 （ 其深度
为 [log2n]*+1） 的结点按层序编号 （ 从第 1层到第
[log2n]*+1层, 每层从左到右 ）, 则对任一结点 i
（ 1≤i≤ n）, 有
?（ 1） 如果 i＝ 1,则结点 i是二叉树的根, 无双亲；
如果 i＞ 1,则其双亲 PARENT（ i） 是结点 [i/2]*。
（ 2） 如果 2i＞ n,则结点 i无左孩子 （ 结点 i为叶
子结点 ）, 否则其左孩子 LCHILD（ i） 是结点 2i。
?（ 3） 如果 2i＋ 1＞ n,则结点 i无右孩子；
? 否则其右孩子 RCHILD（ i） 是结点 2i+1.
6.2.3 二叉树的存储结构
一、顺序存储结构
? //--------二叉树的顺序存储表示 ------------
? # define MAX_TREE_SIZE 100
? typedef TElemType SqBiTree[MAX_TREE_SIZE];
? SqBiTree bt;
? 上一节完全二叉树的十二个结点的顺序存储为：
?
? 上一节非完全二叉树的六个结点的顺序存储
? （ 需 7个存储空间 ） 为：
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 0 5 6
最坏情况,深度为 k的且只有 k个结点的单支树需要长度为 2k-1的一维数组。
二、链式存储结构
? typedef struct BiTNode {
? TElemType data;
? struct BiTNode *lchild,*rchild; //左右孩子指针
? }BiTNode,*BiTree;
rchilddatalchild
data
parent
lchild rchild
datalchild rchildparent
链式存储结构示例
树的二叉两链表示。三叉链表示略
A
B
C D
G
E F
A
B
C D
E F
G
?
?
? ? ?
? ?
?
B
D
A ?
E?
F? ?
G? ?
C? ?
0
1
2
3
4
5
6
1
2 3
4 5
6
基本操作的函数原型说明 (一 )
? Status CreateBiTree(BiTree &T);
? //按先序次序输入二叉树中结点的值 （ 一个字符 ）,
? 空格字符表示空树,
? //构造二叉链表表示的二叉树 T。
? Status PreOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数
? //先序遍历二叉树 T,对每个结点调用函数 Visit一次且仅
一次 。
? //一旦 Visit( ) 失败, 则操作失败 。
基本操作的函数原型说明 (二 )
? Status InOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数 。
? //中序遍历二叉树 T,一旦 Visit( ) 失败, 则操作失败 。
? Status PostOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数 。
? //后序遍历二叉树 T,一旦 Visit( ) 失败, 则操作失败 。
? Status LevelOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数 。
? //层序遍历二叉树 T,一旦 Visit( ) 失败, 则操作失败 。
实验与习题
?理论习题 6.1-6.7
6.1 树的定义和基本术语
6.2 二叉树
6.2.1 二叉树的定义
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
6.6 赫夫曼树及其应用
6.6.1 最优二叉树 (赫夫曼树 )
第六章 树和二叉树
6.1 树的定义和基本术语
?非线性数据结构 。
?树的递归定义：
?树 (tree)是 n(n>=0)个结点的有限集 。
? 当 n>0时,
? (1)有且仅有一个特定的称为根 (root)的结点 ;
? (2)当 n>1时,其余结点可分为 m(m>0)个互不相
交的有限集 T1,T2,...,Tm,其中每个集合本身又是一
棵树 。 称为 子树 (subtree)。
树的示例
空树
n=0
层次
1
2
3
4
一般的树
A
B C D
E F G H I
J K L
只有根结点
的树 n=1
A
树的抽象数据类型定义：
? ADT Tree｛
? 数据对象 D,D是具有相同特性的数据元素的集合 。
? 数据关系 R：若 D为空集, 则称为空树 ;
? 若 D仅含一个数据元素, 则 R为空集, 否则 R＝ ｛ H｝,
H是如下二元关系：
? （ 1） 在 D中存在唯一的称为根的数据元素 root,它在
关系 H下无前驱；
? （ 2） 若 D－ ｛ root｝ ≠ φ, 则存在 D－ ｛ root｝ 的一个
划分 D1,D2,...,Dm （ m＞ 0）, 对任意 j≠ k（ 1≤j,k≤ m）
有 Dj∩ Dk=φ, 且对任意的 i（ 1≤i≤ m）, 唯一存在数据
元素 xiξ Di,有 <root,xi>ξ H;
? （ 3） 对应于 D－ ｛ root｝ 的划分, H－ ｛ <root,x1>,....，
<root,xm>｝ 有唯一的一个划分 H1,H2,...,Hm （ m＞ 0）,
对任意 j≠ k（ 1≤j,k≤ m） 有 Hj∩ Hk=φ, 且对任意的 i
（ 1≤i≤ m）, Hi 是 Di上的二元关系, （ Di,{Hi}） 是一
棵符合本定义的树, 称为根 root的子树 。
树的抽象数据类型定义：
基本操作（之一）
? INITTREE（ ＆ T） ；
? 操作结果：构造空树 T。
? DESTROYTREE（ ＆ T） ；
? 初始条件：树 T存在 。
? 操作结果：销毁树 T。
? CREATETREE（ ＆ T,DEFINITION） ；
? 初始条件,DEFINITION给出树 T的定义 。
? 操作结果：按 DEFINITION构造树 T。
? CLEARTREE（ ＆ T） ；
? 初始条件：树 T存在 。
? 操作结果：将树 T清为空树 。
树的抽象数据类型定义：
基本操作（之二）
? TREEEMPTY（ T）
? 初始条件：树 T存在 。
? 操作结果：若 T为空树, 则返回 TURE,否则 FALSE。
? TREEDEPTH（ T）
? 初始条件：树 T存在 。
? 操作结果：返回 T的深度 。
? ROOT（ T）
? 初始条件：树 T存在 。
? 操作结果：返回 T的根 。
? VALUE（ T,CUR_E） ；
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：返回 CUR＿ E的值 。
树的抽象数据类型定义：
基本操作（之三）
? ASSIGN（ T,CUR_E,VALUE）
? 初始条件：树 T存在,CUR＿ E是 T中某个结点。
? 操作结果：结点 CUR_E赋值 为 VALUE。
? PARENT（ T,CUR＿ E）
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：若 CUR＿ E是 T的非根结点, 则返回它的双亲, 否则
函数值为, 空, 。
? LEFTCHILD（ T,CUR＿ E）
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：若 CUR＿ E是 T的非叶子结点, 则返回它的最左孩子,
否则返回, 空, 。
? RIGHTSIBLING（ T,CUR＿ E）
? 初始条件：树 T存在, CUR＿ E是 T中某个结点 。
? 操作结果：若 CUR＿ E有右兄弟, 则返回它的右兄弟, 否则函数
值为, 空, 。
树 的 抽 象 数 据 类型 定 义,
基本操作 （ 之四 ）
? INSERTCHILD（ ＆ T,＆ P,I,C） ；
? 初始条件：树 T存在, P指向 T中某个结点, 1≤I≤P所指结
点的度＋ 1,非空树 C与 T不相交 。
? 操作结果：插入 C为 T中 P指结点的第 I棵子树 。
? DELETECHILD（ ＆ T,＆ P,I） ；
? 初始条件：树 T存在, P指向 T中某个结点, 1≤I≤P指结点
的度 。
? 操作结果：删除 T中 P所指结点的第 I棵子树 。
? TRAVERSETREE（ T,VISIT（ ）） ；
? 初始条件：树 t存在, VISIT是对结点操作的应用函数 。
? 操作结果：按某种次序对 T的每个结点调用函数 VISIT（ ）
一次且至多一次 。 一旦 VISIT（ ） 失败, 则操作失败 。
? ｝ ADT TREE
树的基本术语（之一）
?子树 (subtree)
?结点
?结点的度 (degree)
?叶子 (leaf)(终端结点 )
?分支结点 (非终端结点 )
?树的度
A
B C D
F G H I
L
树的基本术语（之二）
? 孩子 (child)
? 双亲 (parent)
? 兄弟 (sibling)
? 堂兄弟
? 祖先
? 子孙
A
B C D
F G H I
L
树的基本术语（之三）
?子树 (subtree)
? 层次 (level)
? 深度 (depth)
? 有序树
? 无序树
? 森林, m(m>=0)棵
互不相交的树的集
合,
A
B C D
F G H I
L
6.2 二叉树
6.2.1 二叉树的定义
?二叉树 (binary tree),度不超过 2的有序树 。
?二叉树的五种基本形态
(a) 空二叉树 ; (b)仅有根结点的二叉树； (c)右子树为空的 二叉树；
(d)左、右子树均为非空的 二叉树； (e)左 子树为空 的二叉树。
(a)
A
(b)
A
(c)
A
(d)
A
(e)
6.2.2 二叉树的性质
性质 1,在二叉树的第 i层上至多有 2(i-1)个结点 (i>=1).
?性质 2,深度为 k的二叉
树至多有 2k-1个结点
(k>=1).
? k-1
? Nk = ∑ 2 i = 2k-1
? i = 0
?性质 3:对任何一棵二叉
树 T,如果其叶结点数为
n0,度为 2的结点数为 n2,
则 n0 = n2 + 1,一般的二叉树
A
B D
E F H I
J K L
层次
1
2
3
4
满二叉树的定义,
?一棵深度为 k且
有 2k-1个结点
的二叉树称为
满二叉树 。
?k = 3
?k = 4
1
2 3
4 5 6 7
8 9 1410 11 1512 13
完全二叉树的定义,
? 深度为 k的, 有 n个结点的二叉树,
? 当且仅当其每一个结点都与深度为 k的
满二叉树中编号从 1至 n的结点一一对应时,
? 称之为完全二叉树 。 1
2 3
4 5 6
完 全 二 叉 树 和
非完全二叉树举例,
1
2 3
4 5 6 7
8 9 10 11 12
完全二叉树
1
2 3
4 5 6
非完全二叉树
完全二叉树
?性质 4：
?具有 n个结点的完全二叉树的深度为 [log2n]*+1。
?性质 5：
? 如果对一棵有 n个结点的完全二叉树 （ 其深度
为 [log2n]*+1） 的结点按层序编号 （ 从第 1层到第
[log2n]*+1层, 每层从左到右 ）, 则对任一结点 i
（ 1≤i≤ n）, 有
?（ 1） 如果 i＝ 1,则结点 i是二叉树的根, 无双亲；
如果 i＞ 1,则其双亲 PARENT（ i） 是结点 [i/2]*。
（ 2） 如果 2i＞ n,则结点 i无左孩子 （ 结点 i为叶
子结点 ）, 否则其左孩子 LCHILD（ i） 是结点 2i。
?（ 3） 如果 2i＋ 1＞ n,则结点 i无右孩子；
? 否则其右孩子 RCHILD（ i） 是结点 2i+1.
6.2.3 二叉树的存储结构
一、顺序存储结构
? //--------二叉树的顺序存储表示 ------------
? # define MAX_TREE_SIZE 100
? typedef TElemType SqBiTree[MAX_TREE_SIZE];
? SqBiTree bt;
? 上一节完全二叉树的十二个结点的顺序存储为：
?
? 上一节非完全二叉树的六个结点的顺序存储
? （ 需 7个存储空间 ） 为：
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 0 5 6
最坏情况,深度为 k的且只有 k个结点的单支树需要长度为 2k-1的一维数组。
二、链式存储结构
? typedef struct BiTNode {
? TElemType data;
? struct BiTNode *lchild,*rchild; //左右孩子指针
? }BiTNode,*BiTree;
rchilddatalchild
data
parent
lchild rchild
datalchild rchildparent
链式存储结构示例
树的二叉两链表示。三叉链表示略
A
B
C D
G
E F
A
B
C D
E F
G
?
?
? ? ?
? ?
?
B
D
A ?
E?
F? ?
G? ?
C? ?
0
1
2
3
4
5
6
1
2 3
4 5
6
基本操作的函数原型说明 (一 )
? Status CreateBiTree(BiTree &T);
? //按先序次序输入二叉树中结点的值 （ 一个字符 ）,
? 空格字符表示空树,
? //构造二叉链表表示的二叉树 T。
? Status PreOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数
? //先序遍历二叉树 T,对每个结点调用函数 Visit一次且仅
一次 。
? //一旦 Visit( ) 失败, 则操作失败 。
基本操作的函数原型说明 (二 )
? Status InOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数 。
? //中序遍历二叉树 T,一旦 Visit( ) 失败, 则操作失败 。
? Status PostOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数 。
? //后序遍历二叉树 T,一旦 Visit( ) 失败, 则操作失败 。
? Status LevelOrderTraverse(BiTree T,
Status(*Visit)(TElemType e));
? //采用二叉链表存储结构,Visit是对结点操作的应用函数 。
? //层序遍历二叉树 T,一旦 Visit( ) 失败, 则操作失败 。
实验与习题
?理论习题 6.1-6.7
