第五章 树树是一类重要的非线性数据结构，是以分支关系定义的层次结构
§ 5.1 树的定义
定义
定义：树 (tree)是 n(n>0)个结点的有限集 T,其中：
有且仅有一个特定的结点，称为树的 根 (root)
当 n>1时，其余结点可分为 m(m>0)个 互不相交 的有限集
T1,T2,……T m,其中每一个集合本身又是一棵树，称为根的子树 (subtree)
特点：
树中至少有一个结点 —— 根
树中各子树是互不相交的集合
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树
基本术语
结点 (node)—— 表示树中的元素，包括数据项及若干指向其子树的分支
结点的度 (degree)—— 结点拥有的子树数
叶子 (leaf)—— 度为 0的结点
孩子 (child)—— 结点子树的根称为该结点的孩子
双亲 (parents)—— 孩子结点的上层结点叫该结点的 ~
兄弟 (sibling)—— 同一双亲的孩子
树的度 —— 一棵树中最大的结点度数
结点的层次 (level)—— 从根结点算起，根为第一层，
它的孩子为第二层 ……
深度 (depth)—— 树中结点的最大层次数
森林 (forest)—— m(m?0)棵互不相交的树的集合
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先
§ 5.2 二叉树
定义
定义：二叉树是 n(n?0)个结点的有限集，它或为空树
(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成
特点
每个结点至多有二棵子树 (即不存在度大于 2的结点 )
二叉树的子树有左、右之分，且其次序不能任意颠倒
基本形态
A
只有根结点的二叉树
空二叉树
A
B
右子树为空
A
B
左子树为空
A
B C
左、右子树均非空
二叉树性质
性质 1,)1(2 1 ii i 个结点层上至多有在二叉树的第证明：用归纳法证明之
i=1时，只有一个根结点,是对的
假设对所有 j(1?j<i)命题成立，即第 j层上至多有 个结点那么，第 i-1层至多有 个结点又二叉树每个结点的度至多为 2
第 i层上最大结点数是第 i-1层的 2倍，即故命题得证
122 01i
12?j
22?i
12 222 ii
性质 2：深度为 k的二叉树至多有 个结点 (k?1)12?k
证明：由性质 1，可得深度为 k 的二叉树最大结点数是
122)(
1 1
1
kk
i
k
i
ii 层的最大结点数第
性质 3：对任何一棵二叉树 T,如果其终端结点数为 n0，
度为 2的结点数为 n2,则 n0=n2+1
证明,n1为二叉树 T中度为 1的结点数因为：二叉树中所有结点的度均小于或等于 2
所以：其结点总数 n=n0+n1+n2
又二叉树中，除根结点外，其余结点都只有一个分支进入设 B为分支总数，则 n=B+1
又：分支由度为 1和度为 2的结点射出,?B=n1+2n2
于是,n=B+1=n1+2n2+1=n0+n1+n2
n0=n2+1
几种特殊形式的二叉树
满二叉树
定义,~12 个结点的二叉树称为且有一棵深度为?
kk
特点：每一层上的结点数都是最大结点数
完全二叉树
定义：深度为 k,有 n个结点的二叉树当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至 n的结点一一对应时，
称为 ~
特点
叶子结点只可能在层次最大的两层上出现
对任一结点，若其右分支下子孙的最大层次为 l,则其左分支下子孙的最大层次必为 l 或 l+1
性质
性质 4,
1l o g 2?nn 深度为个结点的完全二叉树的具有
1
2 3
11
4 5
8 9 12 13
6 7
10 14 15
1
2 3
11
4 5
8 9 12
6 7
10
1
2 3
4 5
6 7
1
2 3
4 5 6
性质 5：如果对一棵有 n个结点的完全二叉树的结点按层序编号，
则对任一结点 i(1?i?n),有：
(1) 如果 i=1,则结点 i是二叉树的根，无双亲；如果 i>1,则其双亲是?i/2?
(2) 如果 2i>n,则结点 i无左孩子；如果 2i?n,则其左孩子是 2i
(3) 如果 2i+1>n,则结点 i无右孩子；如果 2i+1?n,则其右孩子是 2i+1
§ 5.3 树的存储结构
树的存储结构
双亲表示法
实现：定义结构数组存放树的结点，每个结点含两个域：
数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中位置
特点：找双亲容易，找孩子难
typedef struct node
{ datatype data;
int parent;
}JD;
JD t[M];
a
b c
d e f
hg i
a
c
d
e
f
g
h
i
b
0
1
2
2
3
5
5
5
1
0 9
6
0
1
2
3
4
5
7
8
9
data parent
0号单元不用或存结点个数如何找孩子结点
孩子表示法
多重链表：每个结点有多个指针域，分别指向其子树的根
结点同构：结点的指针个数相等，为树的度 D
结点不同构：结点指针个数不等，为该结点的度 d
data child1 child2 ………,childD
data degree child1 child2 ………,childd
孩子链表：每个结点的孩子结点用单链表存储，再用含 n个元素的结构数组指向每个孩子链表孩子结点,typedef struct node
{ int child; //该结点在表头数组中下标
struct node *next; //指向下一孩子结点
}JD;
表头结点,typedef struct tnode
{ datatype data; //数据域
struct node *fc; //指向第一个孩子结点
}TD;
TD t[M]; //t[0]不用
a
b c
d e f
hg i
6
0
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3 ^
4 5 ^
^
97 8 ^
6 ^
^
^
^
^如何找双亲结点
带双亲的孩子链表
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3
4 5
97 8
6
^
^
^
^
^
^
^
^
^
0
1
2
2
3
5
5
5
1
parenta
b c
d e f
hg i
孩子兄弟表示法（二叉树表示法）
实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点
特点
操作容易
破坏了树的层次
typedef struct node
{ datatype data;
struct node *fch,*nsib;
}JD;
a
b c
d e f
hg i
a
b c
d e f
g h i
^
^
^
^ ^ ^
^ ^ ^ ^
二叉树的存储结构
顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素
特点：
结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树
a
b c
d e
f g
a b c d e 0 0 0 0 f g
1 2 3 4 5 6 7 8 9 10 11
链式存储结构
二叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild;
}JD;
lchild data rchild
A
B
C D
E F
G
在 n个结点的二叉链表中，有 n+1个空指针域
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
三叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild,*parent;
}JD;
lchild data parent rchild
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
树与二叉树转换
A
CB E
D
树 A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应
将树转换成二叉树
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I
树转换成的二叉树其右子树一定为空
将 二叉 树转换成树
加线：若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双亲用线连起来
抹线：抹掉原二叉树中双亲与右孩子之间的连线
调整：将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
森林转换成二叉树
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
A
B C D
E
F
G
H I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原：将孤立的二叉树还原成树
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
§ 5.4 树和二叉树的遍历
树的遍历
遍历 —— 按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列
常用方法
先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树
后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点
按层次遍历：先访问第一层上的结点，然后依次遍历第二层,…… 第 n层的结点
A
B C D
E F G H
I J K L M
N O
先序遍历：
后序遍历：
层次遍历：
A B E F I G C D H J K L N OM
E I F G B C J K N O L M H D A
A B C D E F G H I J K L MN O
二叉树的遍历
方法
先序遍历：先访问根结点,然后分别先序遍历左子树、右子树
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后序遍历：先后序遍历左、右子树，然后访问根结点
按层次遍历：从上到下、从左到右访问各结点
D
L R
LDR,LRD,DLR
RDL,RLD,DRL
A
D
B C
D L R
A
D L R
D L R
B
D
C
D L R
先序遍历序列,A B D C
先序遍历,
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
中序遍历,
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
后序遍历序列,D B C A
后序遍历,
B
-
+ /
a *
b -
e f
c d
先序遍历,
中序遍历：
后序遍历：
层次遍历,
- + a * b - c d / e f
-+a *b -c d /e f
- + a * b - c d/ e f
-+a *b -c d /e f
算法
递归算法
Ch5_1.c
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
先序序列,A B D C
非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NULL
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E
p (8)
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
A
B
C D
E F
G
i
访问,C B E G D F A
p=NULL
(15)
Ch5_4.c
Ch5_40.C
后序遍历非递归算法
遍历算法应用
按先序遍历序列建立二叉树的二叉链表，已知先序序列为：
A B C D E? G F
求二叉树深度算法
Ch5_5.c
ch5_6.c
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^Ch5_1.c
统计二叉树中叶子结点个数算法
§ 5.5 二叉树的应用
哈夫曼树 (Huffman)—— 带权路径长度最短的树
定义
路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的 ~
路径长度：路径上的分支数
树的路径长度：从树根到每一个结点的路径长度之和
树的带权路径长度：树中所有带权结点的路径长度之和
—结点到根的路径长度—
—权值—其中：
记作：
k
k
n
k
kk
l
w
lww p l?
1
Huffman树 —— 设有 n个权值 {w1,w2,……wn},构造一棵有 n
个叶子结点的二叉树，每个叶子的权值为 wi,则 wpl最小的二叉树叫 ~
例 有 4个结点，权值分别为 7,5,2,4，构造有 4个叶子结点的二叉树
a b c d
7 5 2 4WPL=7*2+5*2+2*2+4*2=36
d
c
a b
2
4
7 5
WPL=7*3+5*3+2*1+4*2=46
a
b
c d
7
5
2 4
WPL=7*1+5*2+2*3+4*3=35
n
k
KK LWW P L
1
构造 Huffman树的方法 —— Huffman算法
构造 Huffman树步骤
根据给定的 n个权值 {w1,w2,……wn},构造 n棵只有根结点的二叉树，令起权值为 wj
在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和
在森林中删除这两棵树，同时将新得到的二叉树加入森林中
重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例
a
7
b5 c
2
d
4
a
7
b5
c
2
d
4
6
a
7
b5
c
2
d
4
6
11
a
7
b5
c
2
d
4
6
11
18
例 w={5,29,7,8,14,23,3,11}
5 1429 7 8 23 3 11
1429 7 8 23 11
35
8
87
151429 23
35
811
11
35
8
191429 23
87
15
11
35
8
1929 23
14
87
15
29
29
14
87
15
29
11
35
8
1923
42
11
35
8
1923
42
29
14
87
15
29
58
11
35
8
1923
42
29
14
87
15
29
58
100
Huffman算法实现
Ch5_8.c
一棵有 n个叶子结点的 Huffman树有 2n-1个结点
采用顺序存储结构 —— 一维结构数组
结点类型定义
typedef struct
{ int data;
int pa,lc,rc;
}JD;
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
0
0
0
7
5
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
(1)
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
3
0
0
7
5
2
4
6
0
0
0
0
0
0
4
0
0
0
0
5
5
0
0
0
k
x1=3,x2=4
m1=2,m2=4
(2)
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
3
2
0
7
5
2
4
6
11
0
0
0
0
0
4
5
0
0
6
5
5
6
0
0
k
x1=2,x2=5
m1=5,m2=6
(3)
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
3
2
1
7
5
2
4
6
11
18
0
0
0
0
4
5
6
7
6
5
5
6
7
0
k
x1=1,x2=6
m1=7,m2=11
(4)
Ch5_8.c
Huffman树应用
最佳判定树等级分数段比例
ABCDE
0~59 60~69 70~79 80~89 90~100
0.05 0.15 0.40 0.30 0.10
a<60
a<90
a<80
a<70
E
Y
N
D
Y
N
C
Y
N
B
Y
N
A
70?a<80
a<60
C
Y
N
B
Y
N
D
Y
N
E
Y
N
A
80?a<90
60?a<70
E A
D
E
C
a<80
a<70
a<60
a<90
E
Y
N
D
Y
NC
Y
N B
Y
N
A
Huffman编码：数据通信用的二进制编码
思想：根据字符出现频率编码，使电文总长最短
编码：根据字符出现频率构造 Huffman树，然后将树中结点引向其左孩子的分支标,0”，引向其右孩子的分支标,1”；每个字符的编码即为从根到每个叶子的路径上得到的 0,1序列例 要传输的字符集 D={C,A,S,T,; }
字符出现频率 w={2,4,2,3,3}
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
译码：从 Huffman树根开始，从待译码电文中逐位取码。
若编码是,0”，则向左走；若编码是,1”，则向右走，
一旦到达叶子结点，则译出一个字符；再重新从根出发，
直到电文结束例 电文是 {CAS;CAT;SAT;AT}
其编码,11010111011101000011111000011000”
电文为,1101000”
译文只能是,CAT”
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
线索二叉树
定义：
前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为 ~
线索：指向前驱或后继结点的指针称为 ~
线索二叉树：加上线索的二叉链表表示的二叉树叫 ~
线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫 ~
实现
在有 n个结点的二叉链表中必定有 n+1个空链域
在线索二叉树的结点中增加两个标志域
lt,若 lt =0,lc 域指向左孩子；若 lt=1,lc域指向其前驱
rt,若 rt =0,rc 域指向右孩子；若 rt=1,rc域指向其后继
结点定义：
typedef struct node
{ int data;
int lt,rt;
struct node *lc,*rc;
}JD;
lc lt data rt rc
A
B
C
D
E
A
B D
C E
T
先序序列,ABCDE
先序线索二叉树
0 0
0 01 1
1 1 ^1 1
A
B
C
D
E
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
A
B
C
D
E
A
B D
C E
T
后序序列,CBEDA
后序线索二叉树
0 0
0 01 1
1 11 1^
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
头结点：
lt=0,lc指向根结点
rt=1,rc指向遍历序列中最后一个结点遍历序列中第一个结点的 lc域和最后一个结点的 rc域都指向头结点
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
t
0 1
pr
p
i
P->A
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
A
B D
C E
bt
^^
^ ^ ^ ^
0 0
0 00 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^^
^ ^ ^ ^
t
0 1
pr
p
i
P->A
P->B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 00 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^^
^ ^ ^ ^
t
0 1
pr
P=NULL
i
P->A
P->B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 00 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^^
^ ^ ^ ^
t
0 1
pr
P
i
P->A
输出,B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 00 0
0 00 0
1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^ ^
t
0 1
pr
P
输出,B
i
P->A
P->C
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^ ^
t
0 1
pr
P=NULL
i
P->A
P->C
输出,B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^ ^
t
0 1
pr
P
i
P->A
输出,B C
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 00 01
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^
t
0 1
pr
P=NULL
i
P->A
输出,B C
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^
t
0 1
pr
P
i
输出,B C A
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 01 01
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P
i
输出,B C A
pr
P->D
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P
i
输出,B C A
pr
P->D
P->E
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P=NULL
i
输出,B C A
pr
P->D
P->E
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P
i
输出,B C A E
pr
P->D
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 01
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^
t
0 1
P=NULL
i
输出,B C A E
pr
P->D
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^
t
0 1
P
i
输出,B C A E D
pr
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 1 1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
t
0 1
P=NULL
i
输出,B C A E D
pr
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 11 1
1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
输出,B C A E D
A
B D
C E
t
0 1
1
1 1 1 1
1
0 0
0 0
算法
按中序线索化二叉树
遍历中序线索二叉树
Ch5_20.c
在中序线索二叉树中找结点后继的方法：
（ 1）若 rt=1,则 rc域直接指向其后继
（ 2）若 rt=0,则结点的后继应是其右子树的左链尾（ lt=1)的结点在中序线索二叉树中找结点前驱的方法：
（ 1）若 lt=1,则 lc域直接指向其前驱
（ 2）若 lt=0,则结点的前驱应是其左子树的右链尾（ rt=1)的结点
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
二叉排序树
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根结点；
否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列Ch5_9.c
二叉排序树的删除要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点，只需修改 p双亲 f的指针 f->lchild=NULL
f->rchild=NULL
p只有左子树或右子树
p只有左子树，用 p的左孩子代替 p (1)(2)
p只有右子树，用 p的右孩子代替 p (3)(4)
p左、右子树均非空
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，
将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p (5)
若 C无右子树，用 C取代 p (6)
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
(6)
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
§ 5.1 树的定义
定义
定义：树 (tree)是 n(n>0)个结点的有限集 T,其中：
有且仅有一个特定的结点，称为树的 根 (root)
当 n>1时，其余结点可分为 m(m>0)个 互不相交 的有限集
T1,T2,……T m,其中每一个集合本身又是一棵树，称为根的子树 (subtree)
特点：
树中至少有一个结点 —— 根
树中各子树是互不相交的集合
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树
基本术语
结点 (node)—— 表示树中的元素，包括数据项及若干指向其子树的分支
结点的度 (degree)—— 结点拥有的子树数
叶子 (leaf)—— 度为 0的结点
孩子 (child)—— 结点子树的根称为该结点的孩子
双亲 (parents)—— 孩子结点的上层结点叫该结点的 ~
兄弟 (sibling)—— 同一双亲的孩子
树的度 —— 一棵树中最大的结点度数
结点的层次 (level)—— 从根结点算起，根为第一层，
它的孩子为第二层 ……
深度 (depth)—— 树中结点的最大层次数
森林 (forest)—— m(m?0)棵互不相交的树的集合
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先
§ 5.2 二叉树
定义
定义：二叉树是 n(n?0)个结点的有限集，它或为空树
(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成
特点
每个结点至多有二棵子树 (即不存在度大于 2的结点 )
二叉树的子树有左、右之分，且其次序不能任意颠倒
基本形态
A
只有根结点的二叉树
空二叉树
A
B
右子树为空
A
B
左子树为空
A
B C
左、右子树均非空
二叉树性质
性质 1,)1(2 1 ii i 个结点层上至多有在二叉树的第证明：用归纳法证明之
i=1时，只有一个根结点,是对的
假设对所有 j(1?j<i)命题成立，即第 j层上至多有 个结点那么，第 i-1层至多有 个结点又二叉树每个结点的度至多为 2
第 i层上最大结点数是第 i-1层的 2倍，即故命题得证
122 01i
12?j
22?i
12 222 ii
性质 2：深度为 k的二叉树至多有 个结点 (k?1)12?k
证明：由性质 1，可得深度为 k 的二叉树最大结点数是
122)(
1 1
1
kk
i
k
i
ii 层的最大结点数第
性质 3：对任何一棵二叉树 T,如果其终端结点数为 n0，
度为 2的结点数为 n2,则 n0=n2+1
证明,n1为二叉树 T中度为 1的结点数因为：二叉树中所有结点的度均小于或等于 2
所以：其结点总数 n=n0+n1+n2
又二叉树中，除根结点外，其余结点都只有一个分支进入设 B为分支总数，则 n=B+1
又：分支由度为 1和度为 2的结点射出,?B=n1+2n2
于是,n=B+1=n1+2n2+1=n0+n1+n2
n0=n2+1
几种特殊形式的二叉树
满二叉树
定义,~12 个结点的二叉树称为且有一棵深度为?
kk
特点：每一层上的结点数都是最大结点数
完全二叉树
定义：深度为 k,有 n个结点的二叉树当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至 n的结点一一对应时，
称为 ~
特点
叶子结点只可能在层次最大的两层上出现
对任一结点，若其右分支下子孙的最大层次为 l,则其左分支下子孙的最大层次必为 l 或 l+1
性质
性质 4,
1l o g 2?nn 深度为个结点的完全二叉树的具有
1
2 3
11
4 5
8 9 12 13
6 7
10 14 15
1
2 3
11
4 5
8 9 12
6 7
10
1
2 3
4 5
6 7
1
2 3
4 5 6
性质 5：如果对一棵有 n个结点的完全二叉树的结点按层序编号，
则对任一结点 i(1?i?n),有：
(1) 如果 i=1,则结点 i是二叉树的根，无双亲；如果 i>1,则其双亲是?i/2?
(2) 如果 2i>n,则结点 i无左孩子；如果 2i?n,则其左孩子是 2i
(3) 如果 2i+1>n,则结点 i无右孩子；如果 2i+1?n,则其右孩子是 2i+1
§ 5.3 树的存储结构
树的存储结构
双亲表示法
实现：定义结构数组存放树的结点，每个结点含两个域：
数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中位置
特点：找双亲容易，找孩子难
typedef struct node
{ datatype data;
int parent;
}JD;
JD t[M];
a
b c
d e f
hg i
a
c
d
e
f
g
h
i
b
0
1
2
2
3
5
5
5
1
0 9
6
0
1
2
3
4
5
7
8
9
data parent
0号单元不用或存结点个数如何找孩子结点
孩子表示法
多重链表：每个结点有多个指针域，分别指向其子树的根
结点同构：结点的指针个数相等，为树的度 D
结点不同构：结点指针个数不等，为该结点的度 d
data child1 child2 ………,childD
data degree child1 child2 ………,childd
孩子链表：每个结点的孩子结点用单链表存储，再用含 n个元素的结构数组指向每个孩子链表孩子结点,typedef struct node
{ int child; //该结点在表头数组中下标
struct node *next; //指向下一孩子结点
}JD;
表头结点,typedef struct tnode
{ datatype data; //数据域
struct node *fc; //指向第一个孩子结点
}TD;
TD t[M]; //t[0]不用
a
b c
d e f
hg i
6
0
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3 ^
4 5 ^
^
97 8 ^
6 ^
^
^
^
^如何找双亲结点
带双亲的孩子链表
6
1
2
3
4
5
7
8
9
a
c
d
e
f
g
h
i
b
data fc
2 3
4 5
97 8
6
^
^
^
^
^
^
^
^
^
0
1
2
2
3
5
5
5
1
parenta
b c
d e f
hg i
孩子兄弟表示法（二叉树表示法）
实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点
特点
操作容易
破坏了树的层次
typedef struct node
{ datatype data;
struct node *fch,*nsib;
}JD;
a
b c
d e f
hg i
a
b c
d e f
g h i
^
^
^
^ ^ ^
^ ^ ^ ^
二叉树的存储结构
顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素
特点：
结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树
a
b c
d e
f g
a b c d e 0 0 0 0 f g
1 2 3 4 5 6 7 8 9 10 11
链式存储结构
二叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild;
}JD;
lchild data rchild
A
B
C D
E F
G
在 n个结点的二叉链表中，有 n+1个空指针域
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
三叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild,*parent;
}JD;
lchild data parent rchild
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
树与二叉树转换
A
CB E
D
树 A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应
将树转换成二叉树
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I
树转换成的二叉树其右子树一定为空
将 二叉 树转换成树
加线：若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双亲用线连起来
抹线：抹掉原二叉树中双亲与右孩子之间的连线
调整：将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
森林转换成二叉树
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
A
B C D
E
F
G
H I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原：将孤立的二叉树还原成树
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
§ 5.4 树和二叉树的遍历
树的遍历
遍历 —— 按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列
常用方法
先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树
后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点
按层次遍历：先访问第一层上的结点，然后依次遍历第二层,…… 第 n层的结点
A
B C D
E F G H
I J K L M
N O
先序遍历：
后序遍历：
层次遍历：
A B E F I G C D H J K L N OM
E I F G B C J K N O L M H D A
A B C D E F G H I J K L MN O
二叉树的遍历
方法
先序遍历：先访问根结点,然后分别先序遍历左子树、右子树
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后序遍历：先后序遍历左、右子树，然后访问根结点
按层次遍历：从上到下、从左到右访问各结点
D
L R
LDR,LRD,DLR
RDL,RLD,DRL
A
D
B C
D L R
A
D L R
D L R
B
D
C
D L R
先序遍历序列,A B D C
先序遍历,
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
中序遍历,
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
后序遍历序列,D B C A
后序遍历,
B
-
+ /
a *
b -
e f
c d
先序遍历,
中序遍历：
后序遍历：
层次遍历,
- + a * b - c d / e f
-+a *b -c d /e f
- + a * b - c d/ e f
-+a *b -c d /e f
算法
递归算法
Ch5_1.c
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
先序序列,A B D C
非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NULL
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E
p (8)
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
A
B
C D
E F
G
i
访问,C B E G D F A
p=NULL
(15)
Ch5_4.c
Ch5_40.C
后序遍历非递归算法
遍历算法应用
按先序遍历序列建立二叉树的二叉链表，已知先序序列为：
A B C D E? G F
求二叉树深度算法
Ch5_5.c
ch5_6.c
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^Ch5_1.c
统计二叉树中叶子结点个数算法
§ 5.5 二叉树的应用
哈夫曼树 (Huffman)—— 带权路径长度最短的树
定义
路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的 ~
路径长度：路径上的分支数
树的路径长度：从树根到每一个结点的路径长度之和
树的带权路径长度：树中所有带权结点的路径长度之和
—结点到根的路径长度—
—权值—其中：
记作：
k
k
n
k
kk
l
w
lww p l?
1
Huffman树 —— 设有 n个权值 {w1,w2,……wn},构造一棵有 n
个叶子结点的二叉树，每个叶子的权值为 wi,则 wpl最小的二叉树叫 ~
例 有 4个结点，权值分别为 7,5,2,4，构造有 4个叶子结点的二叉树
a b c d
7 5 2 4WPL=7*2+5*2+2*2+4*2=36
d
c
a b
2
4
7 5
WPL=7*3+5*3+2*1+4*2=46
a
b
c d
7
5
2 4
WPL=7*1+5*2+2*3+4*3=35
n
k
KK LWW P L
1
构造 Huffman树的方法 —— Huffman算法
构造 Huffman树步骤
根据给定的 n个权值 {w1,w2,……wn},构造 n棵只有根结点的二叉树，令起权值为 wj
在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和
在森林中删除这两棵树，同时将新得到的二叉树加入森林中
重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例
a
7
b5 c
2
d
4
a
7
b5
c
2
d
4
6
a
7
b5
c
2
d
4
6
11
a
7
b5
c
2
d
4
6
11
18
例 w={5,29,7,8,14,23,3,11}
5 1429 7 8 23 3 11
1429 7 8 23 11
35
8
87
151429 23
35
811
11
35
8
191429 23
87
15
11
35
8
1929 23
14
87
15
29
29
14
87
15
29
11
35
8
1923
42
11
35
8
1923
42
29
14
87
15
29
58
11
35
8
1923
42
29
14
87
15
29
58
100
Huffman算法实现
Ch5_8.c
一棵有 n个叶子结点的 Huffman树有 2n-1个结点
采用顺序存储结构 —— 一维结构数组
结点类型定义
typedef struct
{ int data;
int pa,lc,rc;
}JD;
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
0
0
0
7
5
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
(1)
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
3
0
0
7
5
2
4
6
0
0
0
0
0
0
4
0
0
0
0
5
5
0
0
0
k
x1=3,x2=4
m1=2,m2=4
(2)
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
3
2
0
7
5
2
4
6
11
0
0
0
0
0
4
5
0
0
6
5
5
6
0
0
k
x1=2,x2=5
m1=5,m2=6
(3)
lc data rc pa
1
2
3
4
5
6
7
0
0
0
0
3
2
1
7
5
2
4
6
11
18
0
0
0
0
4
5
6
7
6
5
5
6
7
0
k
x1=1,x2=6
m1=7,m2=11
(4)
Ch5_8.c
Huffman树应用
最佳判定树等级分数段比例
ABCDE
0~59 60~69 70~79 80~89 90~100
0.05 0.15 0.40 0.30 0.10
a<60
a<90
a<80
a<70
E
Y
N
D
Y
N
C
Y
N
B
Y
N
A
70?a<80
a<60
C
Y
N
B
Y
N
D
Y
N
E
Y
N
A
80?a<90
60?a<70
E A
D
E
C
a<80
a<70
a<60
a<90
E
Y
N
D
Y
NC
Y
N B
Y
N
A
Huffman编码：数据通信用的二进制编码
思想：根据字符出现频率编码，使电文总长最短
编码：根据字符出现频率构造 Huffman树，然后将树中结点引向其左孩子的分支标,0”，引向其右孩子的分支标,1”；每个字符的编码即为从根到每个叶子的路径上得到的 0,1序列例 要传输的字符集 D={C,A,S,T,; }
字符出现频率 w={2,4,2,3,3}
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
译码：从 Huffman树根开始，从待译码电文中逐位取码。
若编码是,0”，则向左走；若编码是,1”，则向右走，
一旦到达叶子结点，则译出一个字符；再重新从根出发，
直到电文结束例 电文是 {CAS;CAT;SAT;AT}
其编码,11010111011101000011111000011000”
电文为,1101000”
译文只能是,CAT”
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
线索二叉树
定义：
前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为 ~
线索：指向前驱或后继结点的指针称为 ~
线索二叉树：加上线索的二叉链表表示的二叉树叫 ~
线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫 ~
实现
在有 n个结点的二叉链表中必定有 n+1个空链域
在线索二叉树的结点中增加两个标志域
lt,若 lt =0,lc 域指向左孩子；若 lt=1,lc域指向其前驱
rt,若 rt =0,rc 域指向右孩子；若 rt=1,rc域指向其后继
结点定义：
typedef struct node
{ int data;
int lt,rt;
struct node *lc,*rc;
}JD;
lc lt data rt rc
A
B
C
D
E
A
B D
C E
T
先序序列,ABCDE
先序线索二叉树
0 0
0 01 1
1 1 ^1 1
A
B
C
D
E
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
A
B
C
D
E
A
B D
C E
T
后序序列,CBEDA
后序线索二叉树
0 0
0 01 1
1 11 1^
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
头结点：
lt=0,lc指向根结点
rt=1,rc指向遍历序列中最后一个结点遍历序列中第一个结点的 lc域和最后一个结点的 rc域都指向头结点
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
t
0 1
pr
p
i
P->A
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
A
B D
C E
bt
^^
^ ^ ^ ^
0 0
0 00 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^^
^ ^ ^ ^
t
0 1
pr
p
i
P->A
P->B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 00 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^^
^ ^ ^ ^
t
0 1
pr
P=NULL
i
P->A
P->B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 00 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^^
^ ^ ^ ^
t
0 1
pr
P
i
P->A
输出,B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 00 0
0 00 0
1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^ ^
t
0 1
pr
P
输出,B
i
P->A
P->C
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^ ^
t
0 1
pr
P=NULL
i
P->A
P->C
输出,B
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 00 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^ ^
t
0 1
pr
P
i
P->A
输出,B C
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 00 01
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^
t
0 1
pr
P=NULL
i
P->A
输出,B C
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^ ^
t
0 1
pr
P
i
输出,B C A
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
0 01 01
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P
i
输出,B C A
pr
P->D
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P
i
输出,B C A
pr
P->D
P->E
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P=NULL
i
输出,B C A
pr
P->D
P->E
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 0
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^ ^
t
0 1
P
i
输出,B C A E
pr
P->D
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 01
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^
t
0 1
P=NULL
i
输出,B C A E
pr
P->D
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
^
t
0 1
P
i
输出,B C A E D
pr
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 01 1 1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
A
B D
C E
bt
^
t
0 1
P=NULL
i
输出,B C A E D
pr
JD *zxxsh(JD *bt)
{ JD *p,*pr,*s[M],*t;
int i=0;
t=(JD *)malloc(sizeof(JD));
t->lt=0; t->rt=1; t->rc=t;
if(bt==NULL) t->lc=t;
else
{ t->lc=bt; pr=t; p=bt;
do{ while(p!=NULL)
{ s[i++]=p; p=p->lc; }
if(i>0)
{ p=s[--i];
printf("%c ",p->data);
if(p->lc==NULL)
{ p->lt=1; p->lc=pr;}
if(pr->rc==NULL)
{ pr->rt=1; pr->rc=p;}
pr=p; p=p->rc;
}
}while(i>0||p!=NULL);
pr->rc=t; pr->rt=1; t->rc=pr;
}
return(t);
}
0 0
0 01 0
1 11 1
1
算法
按中序线索化二叉树
Ch5_20.c
A
B
C
D
E
输出,B C A E D
A
B D
C E
t
0 1
1
1 1 1 1
1
0 0
0 0
算法
按中序线索化二叉树
遍历中序线索二叉树
Ch5_20.c
在中序线索二叉树中找结点后继的方法：
（ 1）若 rt=1,则 rc域直接指向其后继
（ 2）若 rt=0,则结点的后继应是其右子树的左链尾（ lt=1)的结点在中序线索二叉树中找结点前驱的方法：
（ 1）若 lt=1,则 lc域直接指向其前驱
（ 2）若 lt=0,则结点的前驱应是其左子树的右链尾（ rt=1)的结点
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
二叉排序树
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根结点；
否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列Ch5_9.c
二叉排序树的删除要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点，只需修改 p双亲 f的指针 f->lchild=NULL
f->rchild=NULL
p只有左子树或右子树
p只有左子树，用 p的左孩子代替 p (1)(2)
p只有右子树，用 p的右孩子代替 p (3)(4)
p左、右子树均非空
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，
将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p (5)
若 C无右子树，用 C取代 p (6)
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
(6)
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
