算 称为S的R等价类。
法
实例四：N皇后问题
N皇后问题要求在一个NN格的棋盘上放置N个皇后，
使其互不攻击。按规则，互不攻击的约束条件为：任意两
个皇后不能处于同一行、同一列或同一对角线上，现要求
给出满足约束条件的所有棋盘布局。
3
第 6 章 树和二叉树
6.2 树的概念
定义：
数
数据对象 D：
据
D是具有相同特性的数据元素的集合。
构
与 ③树的度: 树中所有结点的度的最大值
算
法 ④叶子结点: 度为零的结点
⑤分支结点: 度大于零的结点
⑥(从根到结点的)路径：
由从根到该结点所经分支和结点构成。
12
第 6 章 树和二叉树
A
6.2 树的概念
B
C
D
E
F GH I J
基本术语
K
L
M
数 ⑦孩子结点：一个结点的直接后继
据结构与算数据结构
⑧双亲结点: 一个结点的直接前驱 ⑨兄弟结点: 同一双亲结点的孩子结点之间互称~。
法
（3）{ 先序遍历右子树。
先序Vi遍si历t(r结o果ot：->dAatBa)D; G C E F PreOrder(root ->LChild);
PreOrder(root ->RChild);
} 30
}
第 6 章 树和二叉树
A
6.4 二叉树的遍历
B
C
中（根）序遍历的递归定义：
数
D
EF
G
据
结
vo若id二叉InO树r为de空r(B树iT，re则e空ro操ot作) ；否则，
D
E
G
F}BiT∧NoDde, *Bi∧TreEe;∧ ∧ F ∧
∧ G∧
含有n个结点的二叉链表中有2n个指针域，n+1个空26域。
第 6 章 树和二叉树
6.3 二叉树
存储结构：② 链式存储结构：三叉链表
数
据
结点结构: parent lchild data rchild
结
root
构
与
算
A
∧A
法
B
C
Visit(root ->data);
} 32
}
第 6 章 树和二叉树 6.4 二叉树的遍历
练习
A
数
B
C
据
结
D
E
FG
构
与 算
H
JK
法
I
先序：ABDEHICFJGK
法
⑩堂兄弟、祖先结点、子孙结点
结点的层次: 假设根结点的层次为1，依次累加。
树的深度：树中叶子结点所在的最大层次 森林：是m（m≥0）棵互不相交的树的集合
13
第 6 章 树和二叉树
6.2 树的概念
基本操作
①InitTree(Tree);
数 据
②DestoryTree(Tree);
结
③CreatTree(Tree);
构 与 算
{ （1）中序遍历左子树； （2）if (访ro问ot根!=结NU点L；L)
法
（3）{ 中序遍历右子树。
中序In遍O历rd结e果r(：rooDt G->LBCAhilEd);C F Visit(root ->data);
InOrder(root ->RChild);
} 31
}
第 6 章 树和二叉树
第 6 章 树和二叉树
6.1 应用实例
6.2 树的概念
数
6.3 二叉树
据
结
6.4 二叉树的遍历
构
与
6.5 线索二叉树
算
法
6.6 树和森林
6.7 哈夫曼树及其应用
6.8 实例分析与实现
6.9 算法总结
1
第 6 章 树和二叉树 6.1 应用实例
实例一：数据压缩问题
数
在信息传输、数据压缩问题中，我们总是希望找到一
得每个结点均被访问一次，而且仅被访问一次。
存在如何遍历即按什么样的搜索路径遍历的问题
28
第 6 章 树和二叉树
6.4 二叉树的遍历
“二叉树”由三个基本单元组成：根结点、左
子树和右子树。若能依次遍历这三部分，就遍历了
数 据
整个二叉树。
结
设用L、D、R分别表示遍历左子树、访问根结点、
构 遍历右子树，对“二叉树”而言，可以有6 ？种搜索路径
算 法
Ⅱ. 假设i=k时成立，即第k层上至多有2k-1个结点；
Ⅲ. 那么第k+1层上最多有2k-1×2个，即2k个 。
结论成立，证毕。
18
第 6 章 树和二叉树
6.3 二叉树
重要性质：
数
②深度为 k 的二叉树上至多含 2k-1 个结点(k≥1)。
据 结
证明：
构
与
基于上一条性质，深度为 k 的二叉树上的结点数至多为
构
④TreeEmpty(Tree);
与 算
⑤Root(Tree);
法
⑥Parent(Tree,x);
⑦FirstChild(Tree,x);
⑧NextSibling(Tree,x);
⑨InsertChild(Tree,p,Child);
⑩DeleteChild(Tree,p,i); 14
第 6 章 树和二叉树
a
法 中编号为 1 至 n 的结点一一对应。
关系：
b
c
满二叉树必为完全二叉树， d
e
f
g
而完全二叉树不一定是
满二叉树。
hi j
21
完全二叉树
第 6 章 树和二叉树
6.3 二叉树
重要性质：
数
④具有 n 个结点的完全二叉树的深度为
据 结
log2n +1 。
构
与
证明：设完全二叉树的深度为 k
算
则根据第二条性质得 2k-1 -1 < n ≤ 2k -1
与
算 最后一个元素(无后继)。
法 其它数据元素
(一个前驱、一个后继)
树型结构
根结点(无前驱)
多个叶子结点 (无后继) 其它数据元素 (一个前驱、多个后继)
11
第 6 章 树和二叉树
A
6.2 树的概念
B
C
D
E
F GH I J
基本术语
K
L
M
数 据
①结点：数据元素+若干指向子树的分支
结 ②结点的度: 分支的个数
表达式、中缀表达式、后缀表达式，并可以实现表达式的
求值运算。 2
第 6 章 树和二叉树 6.1 应用实例
实例三：等价类划分问题
等价关系是现实世界中广泛存在的一种关系，许多应
数 用问题可归结为按给定的等价关系将集合划分为等价类的
据 结 构 与
问题。问题可描述为：若R是集合S上的一个等价关系，则 由R可得到集合S的唯一划分，即可以按R将S划分为若干个 不相交的子集S1，S2，…，这些子集的并集等于S，子集Si
与 算
全二叉树中任意一个编号为 i 的结点：
法 (1) 若 i=1，则该结点是二叉树的根，无双亲，
否则，编号为 i/2 的结点为其双亲结点；
(2) 若 2i>n，则该结点无左孩子，
否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点，
否则，编号为2i+1 的结点为其右孩子结点。
形态： 5种
数
据
结
构
与 算 法
空二叉树
只有根结点 的二叉树
只有左子树 的二叉树
只有右子树 的二叉树
左、右子树均 非空的二叉树
16
第 6 章 树和二叉树
6.3 二叉树
基本操作：
①Initiate(bt);
数 据
②Destory (bt);
结
③Creat (bt);
构
④Empty(bt);
与 算
⑤Root(bt);
算
法
20+21+ +2k-1 = 2k-1
19
第 6 章 树和二叉树
6.3 二叉树
重要性质：
数
③ 对任何一棵二叉树，若它含有n0 个叶子结点、
据 结 构
n2 个度为 2 的结点，则必存在关系式： n0 = n2+1。
与 算
证明：设二叉树上结点总数 n = n0 + n1 + n2
法
又二叉树上分支总数 b = n1+2n2
23
第 6 章 树和二叉树
6.3 二叉树
存储结构：
数 据
ቤተ መጻሕፍቲ ባይዱ
① 顺序存储结构
结 构
② 链式存储结构
与
算
法
24
第 6 章 树和二叉树
6.3 二叉树
存储结构：① 顺序存储结构 一维数组bt[n]
数
是用一组连续的存储单元来存放二叉树的数据元素 。
据
结
A
A
构 与
B
C
B
算
法
D
E
F
G
C
H I J KL
D
ABCDE F GHI J KL A B
A
6.3 二叉树的遍历与线索化
B
C
后（根）序遍历的递归定义：
数
D
EF
G
据
结
vo若id二叉Po树st为Or空de树r(，Bi则Tr空ee操ro作o；t) 否则，