? 3.5.1 树的基本概念
3.5.2 树的存储
3.5.3 二叉树 的基本概念
3.5.4 二叉树的存储
3.5.5 二叉树的遍历
3.5.6 树与森林的二叉树表示
3.5.7 二叉树的应用
3.5 树与二叉树
3.5.1 树的基本概念
1,树的定义
树是以分支关系定义的层次结构。
倒生树：树根在上，根上分茎，茎上分叶
是族谱、社会组织机构一类实体的逻辑抽象树的定义
对定义的理解
（ 1）有限集
（ 2）递归定义：树，根，子树
（ 3）有且仅有一个根结点不存在空树
（ 4）子树是互不相交的有限集
（ 5）树的层次性有且仅有一个根结点除根结点以外的结点有且仅有一个父结点树的定义
树是一种数据结构
Tree = ( D,R )
D：元素的集合
R：元素关系的集合
（父、子关系 前驱、后继关系）
各结点没有或仅有一个父结点
有且仅有一个根结点
各结点可以有任意个子树树的定义
2,树的术语
1）结点
2）度与深度根结点没有前驱，仅有后继结点的度：该结点拥有的子树数目。
树的度：最大的结点度深度：最大的层次数叶结点(茎 )分支结点没有后继，仅有前驱有且仅有一个前驱，可以有多个后继树的术语树的术语孩子 兄弟 祖先 子孙双亲 孩子
A
3） A节点的树的术语
4）路径（树枝，分支）
从 K1出发自上而下到 K2所经历的所有结点序列
K1
K2
K3 K4
K5 K6 K7
K1 K4 K7 K2
树的术语
5）有序树与无序树
有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。
树的术语
6）森林
不相交的树的集合树的存储
3.5.2 树的存储
1,连续顺序存储
K1
K2 K5
K4 K6
a [ 0 ]
a [ 1 ]
a [ 2 ]
a [ 3 ]
a [ 4 ]
连续线性的下标不能很好的反映树的分支关系（非线性）
树的存储
2,链接存储－－多重链表
树的节点 对应于 链表的链点
树节点间的分支关系用链点间的指针描述
链点可能有多个指针－－ 多重链表,每个指针描述对应节点的一个分支关系
有且仅有一个根链点
不同的指针指向不同的子树根链点
一个子树有仅有一个根链点
DATA
子树 1 2 3
二叉树
3.5.3 二叉树
1、定义
二叉树是结点的有限集，或为空，或由根的左、
右子树组成，左右子树又分别是符合定义的二叉树。
对比树的定义：
空二叉树 树的定义中没有空树的概念
不多于 2个孩子 树的节点可以有任意个子树
子树有左右之分 无序树可不区分左右
树的其它定义适用于二叉树：根茎叶、度、路径仍然是递归定义。 二叉树是树吗？
二叉树
（ 4）二叉树的形态空树 无子树 仅有左子树 有左右子树仅有右子树二叉树的性质
2,二叉树的性质
（ 1）在二叉树的第 i层上最多有 2i-1个结点
第 i层的结点数最多是第 i-1层的两倍
（ 2）深度为 k的二叉树最多有 2k - 1个结点
（ 3）叶结点数比具有两个孩子的结点数多 个1
二叉树的性质
（ 3）叶结点数比具有两个孩子的结点数多 1个设 n0为叶结点个数，
n1为具有一个孩子的分支结点个数，
n2为具有两个孩子的分支结点个数，
n为结点总个数结论,n0 = n2 + 1;
条件 1,n = n0 + n1 + n2
条件 2,n = 分支的个数 + 1
设为分支的个数为 B
条件 3,B = 2 n2 + n1
所以,2n2 + n1 + 1 = n0 + n1 + n2
二叉树的性质
（ 4）深度为 K的 满二叉树,结点个数为 2k-1
满二叉树：所有的结点有两个孩子,所有的叶结点都位于同一层。
满二叉树：“装满”节点的二叉树
半满二叉树：深度为 K的二叉树,K－ 1层是满二叉树,K层节点个数不足 2K－ 1个二叉树的性质
（ 5）具有 n个节点的 完全二叉树,深度为
[log2n]+1
完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。
如果对节点数为 n的完全二叉树自上而下，从左至右依次编号，则节点 i的父结点为 [ i / 2 ]
1
2 3
4 5 6
若 2i≤n，则
i的 左 后继是
2i；若 2i>n,
则 i无 左 后继
若 2i＋ 1≤n，
则 i的 右 后继是
2i＋ 1；若 2i>n,
则 i无 右 后继完全二叉树
关于完全二叉树的其他描述形式
如果对满二叉树的节点从上至下，从左至右连续编号，具有 n个节点的完全二叉树各节点与同样深度的满二叉树的前 n个节点一一对应
叶节点仅位于下两层，对任一节点，若其右子树的深度为 1，则其左子树的深度不小于 1
二叉树满二叉树半满二叉树完全二叉树非完全二叉树半满二叉树半满二叉树非完全二叉树顺序存储二叉树
3.5.4 二叉树存储
1,顺序存储二叉树
将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点 i，我们可以知道它的父结点为 [ i/2 ]，两个孩子分别为 2i和 2i＋ 1。
一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系
如此存放，将浪费较多空间顺序存储二叉树
例 H
A C
B D E G
F I K J M O U P
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
AH BC ED FG KI MJ O PU
a[1] a[15]
H
A C
B E G
F I U PM
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
AH BC E FG I M PU
a[1] a[15]
一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。
用链表实现二叉树
2,用链表实现二叉树
二叉树链点的定义
二叉树的定义
typedef struct tnode_type{
elemtype data;
struct tnode_type *Lchild;
struct tnode_type *Rchild;
}tnode_type;
data
Lchile Rchild
typedef struct tree_type{
tnode_type *root;
int num;
}tree_type;
左孩子，左子树右孩子，右子树根结点指针链式存储结构
lchild Data rchild
A ^
D
B
^ C ^
^ E ^ ^ F ^
图为一般二叉树的二叉链表结构
A
E
C
B
D
F
每个结点由数据域、左指针域和右指针域组成。
用链表实现二叉树二叉树的遍历
3.5.5 二叉树的遍历
A
B
C
中根遍历中序遍历
（ LDR）
先根遍历先序遍历
（ DLR）
后根遍历后序遍历
（ LRD）?以根被访问顺序来划分不同的遍历方法
在子树的访问顺序中始终以左子树优先特点：
左 根 右根 左 右左 右 根作用：查找某个结点，
或对二叉树中全部结点进行某种处理，就需要遍历。遍历,指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。
二叉树的遍历
2）先根遍历（先序遍历） A
B
C D
EF
G H
I
J
K
L
M
N
O
P QA B C F G E H D I J K L M N O P Q
根 左 右二叉树的遍历
1）中根遍历（中序遍历） A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
F G C E H B D J I A L N P O Q M K
左 根 右二叉树的遍历
3）后根遍历（后序遍历） A
B
C D
EF
G H
I
J
K
L
M
N
O
P QG F H E C J I D B P Q O N M L K A
左 右 根例,已知前序遍历,ABCDEFG 中序遍历,CBDAFEG
写出该二叉树的后序遍历分析,前序遍历中的第一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
C D B F G E A 后序遍历例,已知后序遍历,CDBFGEA 中序遍历,CBDAFEG
写出该二叉树的前序遍历分析,后序遍历中的最后一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
A B C D E F G 前序遍历二叉树的遍历
中根遍历算法
算法实现分析
遍历过程：
从根开始
A
B
C
1、找到 B，但不访问 B
2、根据 B找到 A，访问 A
3、再回到 B、访问 B
4,根据 B找到 C，访问 C
方法一、利用栈来实现回朔回到 回溯
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
1、树（子树）根入栈，不访问
2、左子树入栈，左子树的各子树根依次入栈即反复进行步骤 1
3、当左子树为空时，出栈，访问根结点
4,根节点右子树入栈
（新树入栈，到步骤 1去遍历右子树）
5、当右子树为空时，
出栈，访问（祖先）爷结点，
将爷结点的右子树入栈
（新树入栈，回到步骤 1)
总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，就再出栈一个节点，访问，出栈节点右子树入栈
A
B
C
FG
EH
D
算法框架
“遍历”
while( ! end_of(tree)){
......
}
中根访问与堆栈
while( ! end_of(tree)){
if( p != NULL ){
push(stack,p)
p = p->Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild; }}
p指针指向即将访问的子树
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
A
p
B
C
FG
E
NULL
NULL NULL
中根访问与堆栈
while( ! end_of(tree)){
if( p != NULL ){
push(stack,p)
p = p->Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild;}
}
end_of(tree)的实现
empty(stack)
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
A
P指针
“假入栈,,先放一个假节点在栈里，当最后一个节点 K出栈时，会连续两次出栈，获得栈空的满足
K
^_^
NULLNULL
算法框架
while( ! empty(tree)){
if( p != NULL ){
push(stack,p)
p = p->Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild;
}}
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
A
P指针
K
NULL
观察 A出栈时和 K出栈时的 P指针情况，可利用
A出栈后
p = k;
且栈为空
K出栈后
p ＝ NULL
且栈为空
P != NULL || !empty(stack)
end_of(tree)的实现
算法框架中根访问与堆栈
void inorder( tree){
tnode_type * p;
create_stack( stack );
p = tree->root;
访问结点
while( p != NULL || ! empty(stack) ){
if ( p != NULL){
push(stack,p);
p = p -> Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild;}}
}
中根遍历算法（ 利用栈来实现回朔 ）
中根遍历算法（ 利用递归的遍历算法 ）
方法二：利用递归调用来实现回溯
中根遍历递归算法
void inorder( root ){
if( root->Lchild != NULL)
inorder (root->Lchild);
process(root);
if( root->Rchild != NULL)
inorder(root->Rchild);
}
左 根 右左 根 右
void inorder( A ){
if( A->Lchild != NULL)
inorder (A->Lchild);
process( A );
if( A->Rchild != NULL)
inorder(A->Rchild);
}
void inorder( B ){
if( B->Lchild != NULL)
inorder (B->Lchild);
process( B );
if( B->Rchild != NULL)
inorder( B->Rchild);
}
void inorder( C ){
if( C->Lchild != NULL)
inorder ( C->Lchild);
process( C );
if( C->Rchild != NULL)
inorder( C->Rchild);
}
void inorder( D ){
if( D->Lchild != NULL)
inorder ( D->Lchild);
process( D );
if( D->Rchild != NULL)
inorder( D->Rchild);
}
A
B
c
D
BCAD
后根遍历递归算法
void postorder( root ){
if( root->Lchild != NULL)
postorder (root->Lchild);
if( root->Rchild != NULL)
postorder(root->Rchild);
process(root);
}
左 右 根利用递归的遍历算法利用递归的遍历算法
先根遍历递归算法
void preorder( root ){
process(root);
if( root->Lchild != NULL)
preorder (root->Lchild);
if( root->Rchild != NULL)
preorder(root->Rchild);
}
根 左 右
A
B
C
中根遍历中序遍历
ABC
BAC 先根遍历先序遍历
ACB 后根遍历后序遍历
void inorder( root ){
if( root->Lchild != NULL)
inorder (root->Lchild);
process(root);
if( root->Rchild != NULL)
inorder(root->Rchild);
}
void postorder( root ){
if( root->Lchild != NULL)
postorder (root->Lchild);
if( root->Rchild != NULL)
postorder(root->Rchild);
process(root);
}
void preorder( root ){
process(root);
if( root->Lchild != NULL)
preorder (root->Lchild);
if( root->Rchild != NULL)
preorder(root->Rchild);
}
利用递归的遍历算法二叉树的遍历
对比递归与非递归算法
递归算法更简洁，更多依靠系统提供的“用户程序调用栈”，该栈的使用对用户是不可见的
非递归算法在算法中直接掌握栈结构的调用
二叉树的深度决定了递归调用的深度，决定了栈的长度。
当二叉树的深度较深时，系统提供的“用户程序调用栈”可能出现溢出，这时需要算法自行掌握栈的使用。
二叉树的遍历
例：二叉排序树
建立二叉树时，将关键值小于根结点的结点放在左子树，关键值大于根结点的的结点放在右子树，
就可以形成一颗 二叉排序树
如学生成绩分别为 71,65,40,88,67,90、
60,70,77……,以下方式建立二叉排序树
71
65
40
88
67 90
60 70
77
中序遍历二叉排序树，获得从低到高的排序结果！
例,已知前序遍历,ABCDEFG 中序遍历,CBDAFEG
写出该二叉树的后序遍历分析,前序遍历中的第一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
C D B F G E A 后序遍历例,已知后序遍历,CDBFGEA 中序遍历,CBDAFEG
写出该二叉树的前序遍历分析,后序遍历中的最后一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
A B C D E F G 前序遍历
3.5.6 树和森林转换为二叉树
（ 1）树转换为二叉树方法,· 对每个孩子进行从左到右的排序；
· 在兄弟之间加一条连线；
· 对每个结点，除了左孩子外，去除其与其余孩子之间的联系；
· 以根结点为轴心，将整个树顺时针转 45度。
树与二叉树的转换
I
A
B C D
E F G H
(b)A
B C D
E G HF I
(a)
A
B
E
F
C
D
G
H
I
(d)
A
B C D
E F G H I
(c)
树与二叉树的转换特点：转换后的二叉树，根结点没有右子树
A
DCB
E
F H I
G
J
E
F
A
D
C
B H
I
G
J
A
D
C
B
E
F
H
I
G
J
A
D
C
B
E
F
H
I
G
J
方法：
·将各棵树分别转成二叉树；
·把每棵树的根结点用线连起来；
·以第一棵树的根结点作为二叉树的根结点,按顺时针方向旋转 。
森林与二叉树的转换二叉树的应用 ——二叉排序树
3.5.7 二叉树的应用
例：建立二叉排序树，进行排序和提高查询算法效率
问题分析
输入：一组无序元素
输出：二叉排序树
核心算法分析
分析从假设二叉排序树已部分建立，现输入一个新元素开始
71
65
40
88
67 90
60
70
核心算法分析
1、新元素与树根结点比较。
2、如果比根小，则取根的左子树，回到 1；如果根无左子树，则将新结点插入在根结点左孩子处
3、如果比根大，取根的右子树，回到 1；如果根无右子树，则将新结点插入在根结点右孩子处
71
65
40
88
67 90
60
70
二叉树的应用 ——二叉排序树
核心算法
1、新元素与树根结点比较。
2、如果比根小，则取根的左子树，回到 1；如果根无左子树，则将新结点插入在根结点左孩子处
3、如果比根大，取根的右子树，回到 1；如果根无右子树，
则将新结点插入在根结点右孩子处设 p指向树根；
if(new_node->data < p->data){
p = p->Lchild;}
if(p->Lchild == NULL)
p->Lchile = new_node;
break;}
{
while( p != NULL){
}
二叉树的应用 ——二叉排序树
2
20
6 15
二叉树的应用 ——哈夫曼树
例：哈夫曼树 最优二叉树 最小费用树
什么是哈夫曼树、怎样建立、有什么用?
哈夫曼树是最优二叉树
最优？
路径 带权 总长 最小
路径？从树根到节点经历的分支序列，路径长度是分支数目
总长？从根到所有节点的路径长度之和
带权？（仅）叶节点带有权值
带权路径长度：路径长度 × 权值
树的带权路径长度：所有带权路径长度之和二叉树的应用 ——哈夫曼树
5 7 2 4 5
7
2
4
5
7
2 4带权路径长：
5× 2＋ 7× 2＋ 2× 2＋ 4× 2＝ 36
5× 2＋ 7× 3＋ 4× 3＋ 2× 1＝ 46
2× 3＋ 4× 3＋ 5× 2＋ 7× 1＝ 35 哈夫曼树二叉树的应用 ——哈夫曼树
哈夫曼树的建立
1)带有权值的节点分别构成独立的树
2)每次选择两个最小权值的根的树
3)生成一个新的根将选出的树挂在下面，分别为左右子树新的根的权值为两个子树的权值之和
4)反复进行直到所有的节点都挂到一颗树上
5 7 2 46
5
7
2 4
11
(a)
(b)
5
7
2 4
(c)
证明：按这个过程建立的二叉树是最优二叉树（略）
二叉树的应用 ——哈夫曼编码
哈夫曼树的应用,利用哈夫曼树构造通讯中电文编码
5
117
2 4
0 1
1
1
0
0
规定：在二叉树上向左使用 0编码，向右使用 1编码假设,A出现 117次,B出现 2次，
C出现 4次,D出现 5次根据哈夫曼树
A使用 0编码 B用 110
C用 111 D用 10
总编码长 117× 1＋ 5× 2＋ 4× 3＋ 2× 3 ＝ 145位否则，要使用 256位！
14
6 8
3 3 4 4
2 2
0
00
0
1
11
1
T ; A
C S
各字符编码是 T ； A C S
00 01 10 110 111
上述电文编码：
11010111011101000011111000011000
方法：
（ 1） 用 { 2,4,2,3,3 }作为叶子结点的权值生成一棵哈夫曼树,并将对应权值 wi的叶子结点注明对应的字符；
（ 2） 约定左分支表示字符,0”,右分支表示字符 ‘ 1’
（ 3） 从叶子结点开始,顺着双亲反推上去,直到根结点,路径上的 ‘ 0’或 ‘ 1’连接的序列就是结点对应的字符的二进制编码的 逆序 。
例,要传输的电文是 {CAS； CAT； SAT； AT}
要传输的字符集是 D={C,A,S,T,； }
每个字符出现的频率是 W={ 2,4,2,3,3 }
注意：编码的总长度恰好为哈夫曼树的带权路径长 。
二叉树的应用 ——哈夫曼编码
3 5
8
1711
55
9
27 28
C D
A
E
B
0
0
0
0
1
1
1
1
例,设电文中出现的字符为 A,B,C,D,E，每个字母在电文中出现的次数分别为 9,7,3,5,11，按哈夫曼得出 C的编码是：
C的编码是 1100
课堂练习课后作业
教材第 121页，第 8,9,10,12,20,22题
3.5.2 树的存储
3.5.3 二叉树 的基本概念
3.5.4 二叉树的存储
3.5.5 二叉树的遍历
3.5.6 树与森林的二叉树表示
3.5.7 二叉树的应用
3.5 树与二叉树
3.5.1 树的基本概念
1,树的定义
树是以分支关系定义的层次结构。
倒生树：树根在上，根上分茎，茎上分叶
是族谱、社会组织机构一类实体的逻辑抽象树的定义
对定义的理解
（ 1）有限集
（ 2）递归定义：树，根，子树
（ 3）有且仅有一个根结点不存在空树
（ 4）子树是互不相交的有限集
（ 5）树的层次性有且仅有一个根结点除根结点以外的结点有且仅有一个父结点树的定义
树是一种数据结构
Tree = ( D,R )
D：元素的集合
R：元素关系的集合
（父、子关系 前驱、后继关系）
各结点没有或仅有一个父结点
有且仅有一个根结点
各结点可以有任意个子树树的定义
2,树的术语
1）结点
2）度与深度根结点没有前驱，仅有后继结点的度：该结点拥有的子树数目。
树的度：最大的结点度深度：最大的层次数叶结点(茎 )分支结点没有后继，仅有前驱有且仅有一个前驱，可以有多个后继树的术语树的术语孩子 兄弟 祖先 子孙双亲 孩子
A
3） A节点的树的术语
4）路径（树枝，分支）
从 K1出发自上而下到 K2所经历的所有结点序列
K1
K2
K3 K4
K5 K6 K7
K1 K4 K7 K2
树的术语
5）有序树与无序树
有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。
树的术语
6）森林
不相交的树的集合树的存储
3.5.2 树的存储
1,连续顺序存储
K1
K2 K5
K4 K6
a [ 0 ]
a [ 1 ]
a [ 2 ]
a [ 3 ]
a [ 4 ]
连续线性的下标不能很好的反映树的分支关系（非线性）
树的存储
2,链接存储－－多重链表
树的节点 对应于 链表的链点
树节点间的分支关系用链点间的指针描述
链点可能有多个指针－－ 多重链表,每个指针描述对应节点的一个分支关系
有且仅有一个根链点
不同的指针指向不同的子树根链点
一个子树有仅有一个根链点
DATA
子树 1 2 3
二叉树
3.5.3 二叉树
1、定义
二叉树是结点的有限集，或为空，或由根的左、
右子树组成，左右子树又分别是符合定义的二叉树。
对比树的定义：
空二叉树 树的定义中没有空树的概念
不多于 2个孩子 树的节点可以有任意个子树
子树有左右之分 无序树可不区分左右
树的其它定义适用于二叉树：根茎叶、度、路径仍然是递归定义。 二叉树是树吗？
二叉树
（ 4）二叉树的形态空树 无子树 仅有左子树 有左右子树仅有右子树二叉树的性质
2,二叉树的性质
（ 1）在二叉树的第 i层上最多有 2i-1个结点
第 i层的结点数最多是第 i-1层的两倍
（ 2）深度为 k的二叉树最多有 2k - 1个结点
（ 3）叶结点数比具有两个孩子的结点数多 个1
二叉树的性质
（ 3）叶结点数比具有两个孩子的结点数多 1个设 n0为叶结点个数，
n1为具有一个孩子的分支结点个数，
n2为具有两个孩子的分支结点个数，
n为结点总个数结论,n0 = n2 + 1;
条件 1,n = n0 + n1 + n2
条件 2,n = 分支的个数 + 1
设为分支的个数为 B
条件 3,B = 2 n2 + n1
所以,2n2 + n1 + 1 = n0 + n1 + n2
二叉树的性质
（ 4）深度为 K的 满二叉树,结点个数为 2k-1
满二叉树：所有的结点有两个孩子,所有的叶结点都位于同一层。
满二叉树：“装满”节点的二叉树
半满二叉树：深度为 K的二叉树,K－ 1层是满二叉树,K层节点个数不足 2K－ 1个二叉树的性质
（ 5）具有 n个节点的 完全二叉树,深度为
[log2n]+1
完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。
如果对节点数为 n的完全二叉树自上而下，从左至右依次编号，则节点 i的父结点为 [ i / 2 ]
1
2 3
4 5 6
若 2i≤n，则
i的 左 后继是
2i；若 2i>n,
则 i无 左 后继
若 2i＋ 1≤n，
则 i的 右 后继是
2i＋ 1；若 2i>n,
则 i无 右 后继完全二叉树
关于完全二叉树的其他描述形式
如果对满二叉树的节点从上至下，从左至右连续编号，具有 n个节点的完全二叉树各节点与同样深度的满二叉树的前 n个节点一一对应
叶节点仅位于下两层，对任一节点，若其右子树的深度为 1，则其左子树的深度不小于 1
二叉树满二叉树半满二叉树完全二叉树非完全二叉树半满二叉树半满二叉树非完全二叉树顺序存储二叉树
3.5.4 二叉树存储
1,顺序存储二叉树
将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点 i，我们可以知道它的父结点为 [ i/2 ]，两个孩子分别为 2i和 2i＋ 1。
一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系
如此存放，将浪费较多空间顺序存储二叉树
例 H
A C
B D E G
F I K J M O U P
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
AH BC ED FG KI MJ O PU
a[1] a[15]
H
A C
B E G
F I U PM
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
AH BC E FG I M PU
a[1] a[15]
一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。
用链表实现二叉树
2,用链表实现二叉树
二叉树链点的定义
二叉树的定义
typedef struct tnode_type{
elemtype data;
struct tnode_type *Lchild;
struct tnode_type *Rchild;
}tnode_type;
data
Lchile Rchild
typedef struct tree_type{
tnode_type *root;
int num;
}tree_type;
左孩子，左子树右孩子，右子树根结点指针链式存储结构
lchild Data rchild
A ^
D
B
^ C ^
^ E ^ ^ F ^
图为一般二叉树的二叉链表结构
A
E
C
B
D
F
每个结点由数据域、左指针域和右指针域组成。
用链表实现二叉树二叉树的遍历
3.5.5 二叉树的遍历
A
B
C
中根遍历中序遍历
（ LDR）
先根遍历先序遍历
（ DLR）
后根遍历后序遍历
（ LRD）?以根被访问顺序来划分不同的遍历方法
在子树的访问顺序中始终以左子树优先特点：
左 根 右根 左 右左 右 根作用：查找某个结点，
或对二叉树中全部结点进行某种处理，就需要遍历。遍历,指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。
二叉树的遍历
2）先根遍历（先序遍历） A
B
C D
EF
G H
I
J
K
L
M
N
O
P QA B C F G E H D I J K L M N O P Q
根 左 右二叉树的遍历
1）中根遍历（中序遍历） A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
F G C E H B D J I A L N P O Q M K
左 根 右二叉树的遍历
3）后根遍历（后序遍历） A
B
C D
EF
G H
I
J
K
L
M
N
O
P QG F H E C J I D B P Q O N M L K A
左 右 根例,已知前序遍历,ABCDEFG 中序遍历,CBDAFEG
写出该二叉树的后序遍历分析,前序遍历中的第一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
C D B F G E A 后序遍历例,已知后序遍历,CDBFGEA 中序遍历,CBDAFEG
写出该二叉树的前序遍历分析,后序遍历中的最后一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
A B C D E F G 前序遍历二叉树的遍历
中根遍历算法
算法实现分析
遍历过程：
从根开始
A
B
C
1、找到 B，但不访问 B
2、根据 B找到 A，访问 A
3、再回到 B、访问 B
4,根据 B找到 C，访问 C
方法一、利用栈来实现回朔回到 回溯
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
1、树（子树）根入栈，不访问
2、左子树入栈，左子树的各子树根依次入栈即反复进行步骤 1
3、当左子树为空时，出栈，访问根结点
4,根节点右子树入栈
（新树入栈，到步骤 1去遍历右子树）
5、当右子树为空时，
出栈，访问（祖先）爷结点，
将爷结点的右子树入栈
（新树入栈，回到步骤 1)
总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，就再出栈一个节点，访问，出栈节点右子树入栈
A
B
C
FG
EH
D
算法框架
“遍历”
while( ! end_of(tree)){
......
}
中根访问与堆栈
while( ! end_of(tree)){
if( p != NULL ){
push(stack,p)
p = p->Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild; }}
p指针指向即将访问的子树
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
A
p
B
C
FG
E
NULL
NULL NULL
中根访问与堆栈
while( ! end_of(tree)){
if( p != NULL ){
push(stack,p)
p = p->Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild;}
}
end_of(tree)的实现
empty(stack)
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
A
P指针
“假入栈,,先放一个假节点在栈里，当最后一个节点 K出栈时，会连续两次出栈，获得栈空的满足
K
^_^
NULLNULL
算法框架
while( ! empty(tree)){
if( p != NULL ){
push(stack,p)
p = p->Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild;
}}
A
B
C D
EF
G H
I
J
K
L
M
N
O
P Q
A
P指针
K
NULL
观察 A出栈时和 K出栈时的 P指针情况，可利用
A出栈后
p = k;
且栈为空
K出栈后
p ＝ NULL
且栈为空
P != NULL || !empty(stack)
end_of(tree)的实现
算法框架中根访问与堆栈
void inorder( tree){
tnode_type * p;
create_stack( stack );
p = tree->root;
访问结点
while( p != NULL || ! empty(stack) ){
if ( p != NULL){
push(stack,p);
p = p -> Lchild;
}
else{
p = pop(stack);
process(p);
p = p->Rchild;}}
}
中根遍历算法（ 利用栈来实现回朔 ）
中根遍历算法（ 利用递归的遍历算法 ）
方法二：利用递归调用来实现回溯
中根遍历递归算法
void inorder( root ){
if( root->Lchild != NULL)
inorder (root->Lchild);
process(root);
if( root->Rchild != NULL)
inorder(root->Rchild);
}
左 根 右左 根 右
void inorder( A ){
if( A->Lchild != NULL)
inorder (A->Lchild);
process( A );
if( A->Rchild != NULL)
inorder(A->Rchild);
}
void inorder( B ){
if( B->Lchild != NULL)
inorder (B->Lchild);
process( B );
if( B->Rchild != NULL)
inorder( B->Rchild);
}
void inorder( C ){
if( C->Lchild != NULL)
inorder ( C->Lchild);
process( C );
if( C->Rchild != NULL)
inorder( C->Rchild);
}
void inorder( D ){
if( D->Lchild != NULL)
inorder ( D->Lchild);
process( D );
if( D->Rchild != NULL)
inorder( D->Rchild);
}
A
B
c
D
BCAD
后根遍历递归算法
void postorder( root ){
if( root->Lchild != NULL)
postorder (root->Lchild);
if( root->Rchild != NULL)
postorder(root->Rchild);
process(root);
}
左 右 根利用递归的遍历算法利用递归的遍历算法
先根遍历递归算法
void preorder( root ){
process(root);
if( root->Lchild != NULL)
preorder (root->Lchild);
if( root->Rchild != NULL)
preorder(root->Rchild);
}
根 左 右
A
B
C
中根遍历中序遍历
ABC
BAC 先根遍历先序遍历
ACB 后根遍历后序遍历
void inorder( root ){
if( root->Lchild != NULL)
inorder (root->Lchild);
process(root);
if( root->Rchild != NULL)
inorder(root->Rchild);
}
void postorder( root ){
if( root->Lchild != NULL)
postorder (root->Lchild);
if( root->Rchild != NULL)
postorder(root->Rchild);
process(root);
}
void preorder( root ){
process(root);
if( root->Lchild != NULL)
preorder (root->Lchild);
if( root->Rchild != NULL)
preorder(root->Rchild);
}
利用递归的遍历算法二叉树的遍历
对比递归与非递归算法
递归算法更简洁，更多依靠系统提供的“用户程序调用栈”，该栈的使用对用户是不可见的
非递归算法在算法中直接掌握栈结构的调用
二叉树的深度决定了递归调用的深度，决定了栈的长度。
当二叉树的深度较深时，系统提供的“用户程序调用栈”可能出现溢出，这时需要算法自行掌握栈的使用。
二叉树的遍历
例：二叉排序树
建立二叉树时，将关键值小于根结点的结点放在左子树，关键值大于根结点的的结点放在右子树，
就可以形成一颗 二叉排序树
如学生成绩分别为 71,65,40,88,67,90、
60,70,77……,以下方式建立二叉排序树
71
65
40
88
67 90
60 70
77
中序遍历二叉排序树，获得从低到高的排序结果！
例,已知前序遍历,ABCDEFG 中序遍历,CBDAFEG
写出该二叉树的后序遍历分析,前序遍历中的第一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
C D B F G E A 后序遍历例,已知后序遍历,CDBFGEA 中序遍历,CBDAFEG
写出该二叉树的前序遍历分析,后序遍历中的最后一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
A B C D E F G 前序遍历
3.5.6 树和森林转换为二叉树
（ 1）树转换为二叉树方法,· 对每个孩子进行从左到右的排序；
· 在兄弟之间加一条连线；
· 对每个结点，除了左孩子外，去除其与其余孩子之间的联系；
· 以根结点为轴心，将整个树顺时针转 45度。
树与二叉树的转换
I
A
B C D
E F G H
(b)A
B C D
E G HF I
(a)
A
B
E
F
C
D
G
H
I
(d)
A
B C D
E F G H I
(c)
树与二叉树的转换特点：转换后的二叉树，根结点没有右子树
A
DCB
E
F H I
G
J
E
F
A
D
C
B H
I
G
J
A
D
C
B
E
F
H
I
G
J
A
D
C
B
E
F
H
I
G
J
方法：
·将各棵树分别转成二叉树；
·把每棵树的根结点用线连起来；
·以第一棵树的根结点作为二叉树的根结点,按顺时针方向旋转 。
森林与二叉树的转换二叉树的应用 ——二叉排序树
3.5.7 二叉树的应用
例：建立二叉排序树，进行排序和提高查询算法效率
问题分析
输入：一组无序元素
输出：二叉排序树
核心算法分析
分析从假设二叉排序树已部分建立，现输入一个新元素开始
71
65
40
88
67 90
60
70
核心算法分析
1、新元素与树根结点比较。
2、如果比根小，则取根的左子树，回到 1；如果根无左子树，则将新结点插入在根结点左孩子处
3、如果比根大，取根的右子树，回到 1；如果根无右子树，则将新结点插入在根结点右孩子处
71
65
40
88
67 90
60
70
二叉树的应用 ——二叉排序树
核心算法
1、新元素与树根结点比较。
2、如果比根小，则取根的左子树，回到 1；如果根无左子树，则将新结点插入在根结点左孩子处
3、如果比根大，取根的右子树，回到 1；如果根无右子树，
则将新结点插入在根结点右孩子处设 p指向树根；
if(new_node->data < p->data){
p = p->Lchild;}
if(p->Lchild == NULL)
p->Lchile = new_node;
break;}
{
while( p != NULL){
}
二叉树的应用 ——二叉排序树
2
20
6 15
二叉树的应用 ——哈夫曼树
例：哈夫曼树 最优二叉树 最小费用树
什么是哈夫曼树、怎样建立、有什么用?
哈夫曼树是最优二叉树
最优？
路径 带权 总长 最小
路径？从树根到节点经历的分支序列，路径长度是分支数目
总长？从根到所有节点的路径长度之和
带权？（仅）叶节点带有权值
带权路径长度：路径长度 × 权值
树的带权路径长度：所有带权路径长度之和二叉树的应用 ——哈夫曼树
5 7 2 4 5
7
2
4
5
7
2 4带权路径长：
5× 2＋ 7× 2＋ 2× 2＋ 4× 2＝ 36
5× 2＋ 7× 3＋ 4× 3＋ 2× 1＝ 46
2× 3＋ 4× 3＋ 5× 2＋ 7× 1＝ 35 哈夫曼树二叉树的应用 ——哈夫曼树
哈夫曼树的建立
1)带有权值的节点分别构成独立的树
2)每次选择两个最小权值的根的树
3)生成一个新的根将选出的树挂在下面，分别为左右子树新的根的权值为两个子树的权值之和
4)反复进行直到所有的节点都挂到一颗树上
5 7 2 46
5
7
2 4
11
(a)
(b)
5
7
2 4
(c)
证明：按这个过程建立的二叉树是最优二叉树（略）
二叉树的应用 ——哈夫曼编码
哈夫曼树的应用,利用哈夫曼树构造通讯中电文编码
5
117
2 4
0 1
1
1
0
0
规定：在二叉树上向左使用 0编码，向右使用 1编码假设,A出现 117次,B出现 2次，
C出现 4次,D出现 5次根据哈夫曼树
A使用 0编码 B用 110
C用 111 D用 10
总编码长 117× 1＋ 5× 2＋ 4× 3＋ 2× 3 ＝ 145位否则，要使用 256位！
14
6 8
3 3 4 4
2 2
0
00
0
1
11
1
T ; A
C S
各字符编码是 T ； A C S
00 01 10 110 111
上述电文编码：
11010111011101000011111000011000
方法：
（ 1） 用 { 2,4,2,3,3 }作为叶子结点的权值生成一棵哈夫曼树,并将对应权值 wi的叶子结点注明对应的字符；
（ 2） 约定左分支表示字符,0”,右分支表示字符 ‘ 1’
（ 3） 从叶子结点开始,顺着双亲反推上去,直到根结点,路径上的 ‘ 0’或 ‘ 1’连接的序列就是结点对应的字符的二进制编码的 逆序 。
例,要传输的电文是 {CAS； CAT； SAT； AT}
要传输的字符集是 D={C,A,S,T,； }
每个字符出现的频率是 W={ 2,4,2,3,3 }
注意：编码的总长度恰好为哈夫曼树的带权路径长 。
二叉树的应用 ——哈夫曼编码
3 5
8
1711
55
9
27 28
C D
A
E
B
0
0
0
0
1
1
1
1
例,设电文中出现的字符为 A,B,C,D,E，每个字母在电文中出现的次数分别为 9,7,3,5,11，按哈夫曼得出 C的编码是：
C的编码是 1100
课堂练习课后作业
教材第 121页，第 8,9,10,12,20,22题
