1
第七章 树和二叉树数据结构
线性结构（线性表，栈，队列，串等）
非线性结构：至少存在一个数据元素有不止一个直接前驱或后继（ 树,图等）
2
7.1.1 树的定义 (形式化定义 )：
树,T＝ {K,R}。 K是包含 n个结点的有穷集合
(n>0),关系 R满足以下条件,
(1)有且仅有一个结点 k0∈ K,它对于关系 R来说没有前驱结点,结点 k0称作树的 根 。
(2)除结点 k0外,K中的每个结点对于关系 R来说都有且仅有一个前驱结点 。
(3)K中每个结点对于关系 R来说可以有多个后继结点 。
7.1 树的概念
3
7.1 树的概念
7.1.1 树的定义 (递归定义）
树 (Tree)是由 n(n>=0)个结点组成的有限集
（记为 T），对任意一颗树 T有：
（ 1）存在唯一一个称为 根 (Root)的结点；
（ 2）当 n>1时，其余的结点可分为 m(m>0)个互不相交的子集 T1,T2,T3… Tm，其中每个子集又是一棵树，并称其为根的 子树 (Subtree)。
4
A
n=1,只有根结点的树
A
B C D
E F G H I J
K L M
n>1有子树的树 根子树
N=0,空树
7.1.2 树的逻辑表示方法
1
2 3
4 5
6 7
1
2
4
5
6
7
3
凹入表表示法
1
2
4 5 36 7
文氏图表示法
1（ 2（ 4,5（ 6,7））,3）
括号表示法
结点的度,
结点拥有的子树数,
树的度：
树内各结点的度的最大值。 m次树或 m叉树,
叶子（终端结点）,度为 0的结点。
非终端结点（分支结点）,度不为 0的结点。
路径,从树中一个结点自上而下到另一个结点之间的分支构成一条路径。
路径长度,路径上的分支数目称作路径长度。
孩子,结点的子树的根称为该结点的孩子。相应地，
该结点称为孩子的双亲。 兄弟,同一双亲的孩子互为兄弟。
A
B C D
E F G H I J
K L M
7.1.3 树的基本术语
7
结点的祖先,从根到该结点所经分支上的所有结点。
结点的子孙,其子树中的任意结点
结点的层次,从根开始定义起，根为第一层，根的孩子为第二层，以此类推，可得各结点的层次。
层次,1
2
3
4
堂兄弟,其双亲在同一层的非兄弟结点互为堂兄弟。
深度,树中结点的最大层次。
有序树,如果树中结点的各子树看成从左到右是有序的，则称为有序树；否则称为无序树。
A
B C D
E F G H I J
K L M
8
森林,是 m（ m≥0) 颗互不相交的树的集合。
对于树而言，其子树的集合即为森林。
A
B C D
E F G H I J
K L M
故森林和树可以相互递归定义。
9
7.1.4 树的性质性质 1,树中的结点数等于所有结点的度数加 1。
证明：
在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点。也就是说,每个非根结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数 (度数 ),从而可得树中的结点数等于所有结点的度数加 1。
1
2 3
4 5
6 7
10
性质 2 度为 m的树中第 i层上至多有 mi-1个结点（ i≥1）。
证明 (采用数学归纳法 )
当 时,只有一个根结点,显然成立。1?i 101 mm i
假设第 层上至多有 个结点，由于 m叉树的每个结点的度至多为 m，故在第 层上的最大结点数为上一层第 层的最大结点数的 m倍。
故有 成立。
1?i 2?im
i
1?i
12 ii mmm
11
证明：
由树的性质 2可知,第 i层上最多结点数为 mi-1
(i=1,2,…,h),显然当高度为 h的 m次树 (即度为 m的树 )
上每一层都达到最多结点数时,整个 m次树具有最多结点数,因此有：
整个树的最多结点数 = 每一层最多结点数之和性质 3:高度为 h的 m次树至多有 个结点。11mmh
1210?+++mmmm h…
1
1
m
m h
证明,设具有 n个结点的 m次树的高度为 h,若在该树中前 h-1层都是满的,即每一层的结点数都等于 mi-1个
(1≤i≤h -1),第 h层 (即最后一层 )的结点数可能满,也可能不满,则该树具有最小的高度。由此可得如下关系：
性质 4:
具有 n个结点的 m次树的最小高度为)1)1((log +?mnm
1
1
1
11
<
m
mn
m
m hh
因 h只能取整数，故)1)1((log + mnh m
hmnh m?+?<? )1)1((lo g1去分母并取对数后得：
即 1)1)1((log)1)1((log ++?<?+? mnhmn
mm
hmnh m?+?<? )1)1((log1
13
(1) 树状结构中的每个结点都有一个前驱。
(2) 度为 m的树中至少有一个度为 m的结点。
判断题填空题
(1)高度为 h，度为 m的树中至少有 ______个结点，
至多有 ______个结点。
(2) 一颗共有 n个结点的树，其中所有分支结点的度均为 k，则该树中的叶子结点个数为 _____。
(3) 一颗含有 n个结点的 k叉树，可能达到的最大深度为 _____和最小深度为 _____ 。
(F)
(T)
h+m-1
1
1
m
mh
n-k+1
[n(k-1)+1]/k
Logk(n(k-1)+1)
14
7.1.5 树的基本运算树的运算主要分为三大类：
第一类,寻找满足某种特定关系的结点,
如寻找当前结点的双亲结点等；
第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第 i个孩子结点等；
第三类,遍历树中每个结点。
树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次 。 树的遍历运算的算法主要有先根遍历和后根遍历两种 。
1,先根遍历先根遍历过程为：
(1)访问根结点；
(2)按照从左到右的次序先根遍历根结点的每一棵子树。
A B E F C G D H M I J
A
B C D
E F G H I J
M
2,后根遍历后根遍历过程为：
(1)按照从左到右的次序后根遍历根结点的每一棵子树；
(2)访问根结点 。 A
B C D
E F G H I J
ME F B G C M H I J D A
7.1.6 树的存储结构
1,双亲存储结构这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置 。
a
b c
d e
f g 4g
6
4f5
1e4
1d3
0c2
0b1
-1a0
伪指针
18
a
b c
d e
f g
4g6
4f5
1e4
1d3
0c2
0b1
-1a0
伪指针找某节点的双亲,
找某节点的孩子,需扫描整个表格伪指针给出
19
2,孩子链存储结构孩子链存储结构可按树的度 (即树中所有结点度的最大值 )设计结点的孩子结点指针域个数 。
a
b c d
e
a
^^b ^^^c ^^^d
^^^e
较浪费空间特点,难查找结点的双亲
20
3,孩子兄弟链存储结构孩子兄弟链存储结构是为每个结点设计三个域：
一个数据元素域,一个指向其第一个孩子结点指针域,一个指向其下一个兄弟结点指针域。
^a
b c^
^e^
^d^
a
b c d
e
优点,有利于将一般的树转化为二叉树 (后面将详细讨论 )
不足,查找双亲结点难,
7.2.1 二叉树的概念二叉树,二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
特点,每个结点至多只有两颗子树，且子树有左右之分，
其次序不能颠倒。
7.2 二叉树概念和性质
(a)
空二叉树
A
(b)单结点的二叉树
A
L_T
(c)根和左子树
A
R_T
(d)根和右子树
A
R_TL_T
(e)根和左右子树二叉树的五种基本形态：
二叉树是度为 2的有序树？
22
满二叉树：
深度为 4的满二叉树。
层次,1 结点数,1
2 2
3 4
4 8
特点,每一层上的结点数都是最大结点数，即 2i-1。
深度为 k且有 2k-1个结点的二叉树。
该二叉数中所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层。
两类 特殊 的二叉树
1
2
4
8 9
5
10
3
6 7
11 12 13 14 15
满二叉树结点的编号方法,
根为 1,按照层数从小到大,
同一层从左到右的次序连续编号
1
2
4
8 9
5
10
3
6 7
11 12 13 14
还是满二叉树吗？
不是，因为编号为 7的结点是分支结点,但无右孩子结点,所以此二叉树不是满二叉树！
24
1
2
4
8 9
5
10
3
6 7
11 12 13
是满二叉树吗？
不是，因为编号为 7
的结点是叶子结点,
但没有位于最下一层,所以此二叉树不是满二叉树！
25
完全二叉树：
深度为 k有 n个结点的二叉树，当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至 n
的结点一一对应 (位置对应 ）时，称之为完全二叉树。
1
2
4
8 9
5
10
3
6 7
11 12
1
2
4
8
5
9
3
6 7
10 11 12
26
完全二叉树的特点：
（ 1）叶子结点只可能在层次最大的两层上出现。
（ 2）对任一结点，若其右分支下的子孙的最大层次为 k,则其左分支下的子孙的最大层次必为 k或 k+1。
（ 3）深度为 k的完全二叉树，前 k-1层结点构成的二叉树必为满二叉树。
完全二叉树又定义为：
若一颗二叉树至多只有最下面的两层上结点的度数可以小于 2，并且最下一层的结点都集中在该层最左边的若干位置上，则称此二叉树为 完全二叉树 。
1
2
4
8 9
5
10
3
6 7
11 12
7.2.2 二叉树的性质性质 1,非空二叉树上叶子结点数等于双分支结点数加 1。
设其终端结点数为 n0，度为 2的结点数为 n2，则 n0=n2+1。
证明：
210 nnnn ++?
在二叉树中，除了根结点，其余结点都有一个分支指向它，设 B为分支总数，
则 n=B+1。由于这些分支是由度为 1或为 2的结点发出的，所以有,21 2nnB +?
故,)1(12 21210 +?++?++? Bnnnnnn 120 +?n
设 n1为二叉树 T中度为 1的结点数。因为二叉树中所有结点的度均小于或等于 2，所以其结点总数为,1
2 3
4 5
6
28
已知二叉树中叶子数为 50,单分支的结点数为 30,则总结点数 。
一棵二叉树有 67个结点,这些结点的度要么是 0,要么是 2。 这棵二叉树中度为 2
的结点有 ( )个
n=n0+n1+n2=n0+n1+n0-1=2n0+n1-1
=2*50+30-1=129
n=n0+n2=n2+1+n2=2n2+1=67
故 n2＝ 33
29
性质 3,深度为 k的二叉树至多有 个结点。12?k
性质 2,在二叉树的第 i层上至多有 2i-1个结点
(i≥1)
30
1
2
4
8 9
5
10
3
6 7
11 12
性质 4 对完全二叉树中编号为 i的结点
(1≤i≤n,n≥1,n为结点数 )有：
(1) 若 i≤?n/2?,即 2i≤n,则编号为 i的结点为分支结点,否则为叶子结点 。
(2) 若 n为奇数,则每个 分支 结点都既有左孩子结点,也有右孩子结点； 若 n为偶数,则编号最大的分支结点 (编号为 n/2)只有左孩子结点,没有右孩子结点,
其余 分支 结点都有左,右孩子结点 。
31
(3) 若编号为 i的结点有左孩子结点,则左孩子结点的编号为 2i；若编号为 i的结点有右孩子结点,则右孩子结点的编号为 (2i+1)。
(4) 除树根结点外,若一个结点的编号为 i,则它的双亲结点的编号为?i/2?,也就是说,当 i为偶数时,其双亲结点的编号为 i/2,它是双亲结点的左孩子结点,当 i
为奇数时,其双亲结点的编号为 (i-1)/2,它是双亲结点的右孩子结点 。 1
2
4
8 9
5
10
3
6 7
11 12
32
性质 5 具有 n个 (n＞ 0)结点的完全二叉树的高度为?log2n+1?或?log2n?+1。
由完全二叉树的定义和树的性质 3可推出 。
参照树的性质 4的证明方法自己证明
33
(1) n(n>2)个结点的二叉树中至少有一个度为 2的结点。
(2) 不存在这样的二叉树：它有 n个度为 0的结点，
n-1个度为 1的结点,n-2个度为 2的结点。
(3) 在任何一棵完全二叉树中，终端结点或者和分支结点一样多，或者只比分支结点多一个。
(4) 完全二叉树中的每个结点或者没有孩子或者有 2个孩子。
判断题
(T)
(F)
(T)
(F)
34
7.2.3 二叉树与树、森林之间的转换
A
B C D
A
B
C
D
1,树与二叉树间的转换
将树转换成二叉树的具体过程
加线,在兄弟之间加一连线
抹线,对每个结点，除了其第一个孩子外，去除其与其余孩子之间的关系
旋转,对于横着的连线，以树的根结点为轴心，将其顺时针转 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
森林转换成二叉树 (方法一）
设森林 F={T1,T2,T3,…,Tn}，将其转化为二叉树 B
（ 1）若森林 F为空，即 n=0,则 B为空树
（ 2）若 F非空，则 B的根 root为森林中第一棵树的根
Root(T1);B的左子树是从 T1中根结点的子树森林 F1转换而成的二叉树，其右子树是从森林 {T2,T3,…,Tn}转换而成的二叉树。
2,森林与二叉树间的转换
38
A
B C D
E
F
G
H I
J
A
B C D E
F
G
H I
JB
C DC
D
B
C
D 左子树
39
A
B
C
D
E
F
G
H I
J
E
F G
H I
J
H
I
J
A
B
C
D
E
F G
H
I
J
40
森林转换成二叉树（方法二）
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
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 GH
I
J
41
二叉树转换成森林
抹线,将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原,将孤立的二叉树还原成树
A
B
C
D
E
F GH
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
42
7.3 二叉树的存储结构
顺序存储结构,把二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中，在这个存储序列中,必须能反映出结点之间的逻辑关系 。
实现的方法,将二叉树的结点元素按 满二叉树 的结点位置自上而下、自左而右存储到一个一维数组中。
顺序存储结构
#define MaxSize 100
typedef char ElemType;
typedef struct { ElemType data[MaxSize];
int n; }SqBTree;
SqBTree bt;
a
b
d
h i
e
j
c
f g
k l
逻辑关系：
结点 i的 lchild的编号为 2i
rchild的编号为 2i+1
parent的编号为?i/2?
11109876543210
lkjihgfedcba
下标 12
1
2
4
8 9
5
10
3
6 7
11 12 13 14 15
编号下标关系：
i的 lchild的下标为 2i-1
rchild的下标为 2i
parent的下标为?(i-1)/2?
1110987654321 12
0
0
0 0
a
b
d
g h
e
i
c
f
j k
编号逻辑关系,结点 i的 lchild的编号为 2i
rchild的编号为 2i+1
parent的编号为?i/2?
最坏的情况下，一个深度为 k且只有 k个结点的单支树却需要长度为 2k-1的一维数组。
1110987654321
kjihgfedcba
14013012060 15111098754321 kjihgfedcba
14
0
13
0
12
0
6
0
15111098754321
k0000f00c0a
45
链式存储结构二叉树 的结点包含结点数据元素和左右分支，所以表示二叉树的链表结点必须有,数据域,左、右指针域 。
有时为了便于查找结点双亲，在结点结构中增加一个指向 双亲的指针域。
lchild data rchild
lchild data parent rchild
二叉链表三叉链表 data
lchild rchild
parent
二叉链表的存储表示：
typedef struct node{
ElemType data;
struct node *lchild,*rchild;
} BTNode;
46
特征,含有 n个结点的二叉链表中有 n+1个空链域。
n个结点共有 2n个链域，除根结点外，其余结点均需一个链域来指出，即 n-1个链域指示 除根结点外 的其他结点，故有 2n-(n-1)=n+1个空链域,
A
B
C D
E F
G
^A
B
^C^ D
E^ ^F^
^G^
二叉链表
47
7.5 二叉树的基本运算及其实现
创建二叉树 CreateBTNode(b,str),根据二叉树括号表示法的字符串建立二叉树的二叉链表
查找结点 FindNode(b,x),在二叉树 b中寻找 data域值为 x的结点,并返回指向该结点的指针。
找孩子结点 LchildNode(p)和 RchildNode(p),分别求二叉树中结点 *p的左孩子结点和右孩子结点。
求高度 BTNodeDepth(b),求二叉树 b的高度。若二叉树为空,则其高度为 0；否则,其高度等于左子树与右子树中的最大高度加 l。
输出二叉树 DispBTNode(b),以括号表示法输出一棵二叉树。
48
说明
void CreateBTNode(BTNode * &b,char *str)
该算法将主函数传给形参 str的字符型数组进行扫描,创建一颗采用链式存储方式的二叉树,通过形参 b将所创建的二叉树根结点的地址,传,回给主函数调用处语句的对应实参。
1.创建二叉树 CreateBTNode(b,str)
char Btree[]={"A(B(D(G)),C(E,F))"};
要求调用前,与 str对应的实参数组存储的是一颗采用括号表示法表示的二叉树,如,
49
创建二叉树 CreateBTNode(b,str)
用 ch扫描采用括号表示法表示二叉树的字符串。分以下几种情况：
① 若 ch='('：则将前面刚创建的结点作为双亲结点进栈,并置 k=1,表示其后创建的结点将作为这个结点的左孩子结点；
② 若 ch=')'：表示栈中结点的左右孩子结点处理完毕,
退栈；
③ 若 ch=‘,’：表示其后创建的结点为右孩子结点；
④ 其他情况,表示要创建一个结点,并根据 k值建立它与栈中结点之间的联系,当 k=1时,表示这个结点作为栈中结点的左孩子结点,当 k=2时,表示这个结点作为栈中结点的右孩子结点。如此循环直到 str处理完毕。
A(B(D(,G)),C(E,F))
50
根据括号表达式 A(B(D(,G)),C(E,F))建立二叉链表的过程如下,建立结点 A
b
∧ ∧A
st
A (k=1)
建立结点 B
∧ ∧B
∧ ∧
B (k=1)
建立结点 D
∧ ∧D
∧ ∧
D (k=1)=2
∧ ∧G
建立结点 G
∧ ∧=2
建立结点 C
∧ ∧C
C =1
建立结点 E
∧ ∧E
∧ ∧
∧ ∧
=2
∧ ∧F
∧ ∧
51
查找结点 FindNode(b,x)
采用递归算法在二叉树 b中查找值为 x的结点。找到后返回其指针,否则返回 NULL。 算法如下：
BTNode *FindNode(BTNode *b,ElemType x)
{ BTNode *p;
if (b==NULL) return NULL;
else if (b->data==x) return b;
else
{ p=FindNode(b->lchild,x);
if (p!=NULL) return p;
else return FindNode(b->rchild,x);
}
}
52
找孩子结点 LchildNode(p)和 RchildNode(p)
直接返回 *p结点的左孩子结点或右孩子结点的指针。 算法如下：
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
A
B
C D
E F
53
求高度 BTNodeDepth(b)
求二叉树的高度的递归模型 f()如下：
int BTNodeDepth(BTNode *b)
{ int lchildh,rchildh;
if (b==NULL) return(0); /*空树的高度为 0*/
else
{ lchildh=BTNodeDepth(b->lchild);
rchildh=BTNodeDepth(b->rchild);
return(lchildh>rchildh)?
(lchildh+1):(rchildh+1);
}
}
A
B
C D
E F
+>?>?
其它若
1)}((),(max{
NULLb0)(
rchildbflchildbfbf
54
7.5 二叉树的遍历遍历二叉树,按一定的次序访问二叉树中所有结点，且每个结点仅被访问一次。它是最基本的运算，
是二叉树中所有其他运算的基础。
“遍历,是任何类型均有的操作，对线性结构而言，
只有一条搜索路径（因为每个结点只有一个后继），
故不需要另加讨论。而二叉树是非线性结构，有些结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。
55
7.5.1二叉树遍历概念与 7.1.5(p170)所介绍过的一般树的遍历相似，
二叉树遍历也是按照一定的次序访问二叉树中所有的结点,且每个结点仅访问一次的过程。但二叉树有自身的特点,共有三种遍历方法：
.先序遍历
.中序遍历
.后序遍历
56
1,先序遍历先序遍历二叉树的过程是：
(1)访问根结点；
(2)先序遍历 左子树；
(3)先序遍历 右子树 。
A
B C
FED
G
A B D GC E F
所有结点都访问过一遍，遍历结束。
先序遍历序列,
(设访问根结点的操作为输出该结点 )
57
void PreOrder(BTNode *b) /*先序遍历的递归算法 */
{
if (b!=NULL)
{ printf("%c ",b->data); /*访问根结点 */
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
58
2,中序遍历中序遍历二叉树的过程是：
(1)中序遍历 左子树；
(2)访问根结点 ；
(3)中序遍历 右子树 。
A
B C
FED
G
G B A E C FD
所有结点都访问过一遍，遍历结束。
中序遍历序列,
/*中序遍历的递归算法 */
void InOrder(BTNode *b)
{
if (b!=NULL)
{ InOrder(b->lchild);//中序遍历左子树
printf("%c ",b->data); //访问根结点
InOrder(b->rchild); //中序遍历右子树
}
}
60
A
B C
FED
G
G D B E F C A
3,后序遍历后序遍历二叉树的过程是：
(1)后序遍历 左子树；
(2)后序遍历 右子树；
(3)访问根结点 。
所有结点都访问过一遍，遍历结束。
后序遍历序列,
/*后序遍历递归算法 */
void PostOrder(BTNode *b)
{
if (b!=NULL)
{ PostOrder(b->lchild);//后序遍历左子树
PostOrder(b->rchild);//后序遍历右子树
printf("%c ",b->data); //访问根结点
}
}
62
二叉树遍历算法小结：
A
B C
FED
G
A B D GC E F
G B A E C FD
G D B E F C A
先序序列,
中序序列,
后序序列,
先序遍历中序遍历后序遍历由此可见,不论使用何种方式，遍历结果都是一个线性表,因而遍历一颗二叉树实质上是对其进行线性化的操作。
63
层次遍历从 上到下、从左到右 的次序遍历二叉树右图的二叉树的层次遍历次序为：
A B C D E F G
A
B
C D
E F
G遍历二叉树的算法分析：
时间复杂度,遍历的基本操作是访问结点，则不论按何种次序遍历，对含有 n个结点的二叉树，其时间复杂度为 O(n)
64
7.6 二叉树的构造
定理 7.1：任何 n(n≥0) 个不同结点的二又树,都可由它的中序序列和先序序列惟一地确定。
a
b c b
c
a c
a
b
a
b c
先序序列 中序序列例 已知结点的先序序列和中序序列分别为：
先序序列,A B C D E F G
中序序列,C B E D A F G。求此二叉树
A
C
B
E
D
F
G
先序,BCDE
中序,CBED
先序,FG
中序,FG
A
B
C E
D
F
G
先序,DE
中序,ED
A
B
C
F
GD
E
前题：确定树的根及其左右子树
66
1.用先序序列的第一个结点作为根结点 ;
2.在中序序列中查找根结点的位置,并以此为界将中序序列划分为左,右两个序列 (左,右子树 );
3.根据左,右子树的中序序列中的结点个数,将前序序列去掉根结点后的序列划分为左,右两个序列,
它们分别是左,右子树的前序序列 ;
4.对左,右子树的前序序列和中序序列递归地实施同样方法,直到所得左,右子树为空 。
67
BTNode *CreateBT1(char *pre,char *in,int n)
{ //根据先序和中序序列构造 n个结点的二叉树
BTNode *s; char *p; int k;
if (n<=0) return NULL;
s=(BTNode *)malloc(sizeof(BTNode)); //创建结点 *s
s->data=*pre;
for (p=in;p<in+n;p++) //在中序中找为 *ppos的位置 k
if (*p==*pre)
break;
k=p-in;
s->lchild=CreateBT1(pre+1,in,k) ;//递归构造左子树
s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);
//构造右子树
return s;
}
68
定理 7.2：任何 n(n＞ 0)个不同结点的二又树,
都可由它的中序序列和后序序列惟一地确定。
任何 n(n＞ 0)个不同结点的二又树,都可由它的先序序列和后序序列惟一地确定？
69
7.7 线索二叉树
1.问题的提出,通过遍历二叉树可得到结点的一个线性序列，在线性序列中，就存在前驱和后继。
但是以二叉链表作存储结构时，只能找到结点的左、右孩子，不能直接得到结点在任一序列中的前驱和后继。因为结点的前驱和后继只有在遍历过程中才能得到，那么能否通过结点的两个链域查找结点的前驱和后继呢？
70
7.7 线索二叉树
2.分析：
n个结点二叉链式存储中共有 2n个链域，其中,n+1个空链域,n-1个指针域；
n个结点的遍历序列中有 n-1个前驱和 n-1个后继；
因此，我们考虑用空链域来存放结点的前驱和后继。线索化二叉树就是利用 n+1个空链域来存放结点的前驱和后继结点的信息。
71
7.7 线索二叉树
3,线索化二叉树：
lchild ltag data rtag rchild
其中：
ltag=
1 lchild域指向结点的前驱,为 线索
0 lchild域指向结点的左孩子
rtag=
1 rchild域指向结点的后继，为 线索
0 rchild域指向结点的右孩子
(1)结点结构在二叉链表中增加 ltag和 rtag两个标志域
72
二叉树的二叉线索存储表示
typedef int elemtype;
typedef struct node{
elemtype data;
int ltag,rtag;
struct node *lchild,*rchild;
}TBTNode;
以上述结点结构构成的二叉链表叫 线索链表 。
线索二叉树,加上线索的二叉树
线索化,对二叉树以 某种次序遍历 使其变为线索二叉树的过程，即将二叉链表中空的指针域修改为线索。
73
/
b
—
+
a * e f
—
c d
NULLNULL
中序线索化,a + b * c – d –e / f
下面主要以中序序列来介绍其线索化过程及其相应的操作先序遍历序列,- + a * b - c d / e f
后序遍历序列,-+a *b -c d /e f
74
7.7 线索二叉树
3,线索化二叉树：
(2) 整体结构增设一个头结点，令其 lchild指向二叉树的根结点,ltag=0,rtag=1;
并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；
最后用头指针 root指示该头结点。
中序线索化
/
b
—
+
a * e f
—
c d
a + b * c – d –e / f
10
0—0
0+0 0/0
1a1 0*0 1e1 1f1
1b1 0—0
1c1 1d1
root
76
线索化的实质 是将二叉链表中的空指针改为指向其前驱或后继的线索,而前驱和后继的信息只有在遍历时才能得到,
故线索化即为在遍历的过程中修改空指针的操作。
中序线索化：
结点 b,
(1)不存在左孩子即,p->lchild==NULL，需将其左链域改为线索，标志域也置为 1
p->lchild=pre; p->ltag=1;
二叉树线索化的实现
pre
p a
b c
(2)存在左孩子，仅需将标识域置 0即可
p->ltag=0;
所以对当前结点 p，线索化时需完成两个操作：
p的前驱结点 pre的后继线索化（根据前驱结点的 rtag或
rchild来判断是否需要）
p结点的前驱线索化（根据其有无空链域来判断）
结点 pre,
(1)不存在右孩子即,pre->lchild==NULL，需将其右链域改为线索，
标志域也置为 1
pre->rchild=p; pre->rtag=1;
(2)存在右孩子，仅需将标识域置 0即可
pre->rtag=0;
pre
a
b c
p
TBTNode *pre; /*全局变量 */
void Thread(TBTNode *&p) /*对二叉树 b进行中序线索化 */
{ if (p!=NULL)
{ Thread(p->lchild); /*左子树线索化 */
if (p->lchild==NULL) /*前驱线索 */
{ p->lchild=pre; p->ltag=1;}/*建立当前结点的前驱线索 */
else p->ltag=0;
if (pre->rchild==NULL) /*后继线索 */
{ pre->rchild=p;pre->rtag=1;}/*建立前驱结点的后继线索 */
else pre->rtag=0;
pre=p;
Thread(p->rchild); /*右子树线索化 */
}
}
a
b c
执行完上述程序后,pre和 p分别指向哪？
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树 */
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=root;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b;
pre=root;
Thread(b); /*中序遍历线索化二叉树 */
pre->rchild=root; /*最后处理,加入指向头结点的线索 */
pre->rtag=1;
root->rchild=pre; /*头结点右线索化 */
}
return root;
}
10
root
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树 */
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=root;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b;
pre=root;
Thread(b);
pre->rchild=root;
pre->rtag=1;
root->rchild=pre;
}
return root;
}
10
root
b
TBTNode *CreaThread(TBTNode *b) //中序线索化二叉树
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=root;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b; pre=root;
Thread(b); pre->rchild=root;
pre->rtag=1;root->rchild=pre;
}
return root;
}
10
root
b
中序次序的最后节点
pre
线索二叉链表的应用举例
查找某结点 *p在指定次序下的前驱和后继例：在中序线索二叉树中查找结点 *p的中序后继结点。
当 rtag=1时,rchild直接给出后继；当 rtag=0时，后继为遍历右子树时访问的第一个结点，也就是从 *p的右孩子开始，沿左指针链往下找，直到找到一个没有左孩子的结点为止。
p
R
bithptr *InOrderNext( bithptr * p)
//在中序线索二叉链表中找结点 p的中序后继
{if(p->rtag= =1) return (p->rchild);
else {q=p->rchild;
while(q->ltag= =0) q=q->lchild;
return (q);
} }
例：在中序线索二叉树中查找结点 *p的中序前驱结点。
(1) 当 ltag=1时,lchild直接给出前驱；
(2)当 ltag=0时，左链为指针，没直接给出其前驱的信息，但根据中序遍历规律可知，结点的前驱是遍历其左子树时最后访问的结点。
R1
R2
Rn
最右下结点
bithptr *InOrderPre( bithptr *p)
//在中序线索二叉链表中找结点 p的中序前驱
{if(p->ltag= =1) return (p->lchild);
else {q=p->lchild;
while(q->rtag= =0) q=q->rchild;
return (q);
} }
p
84
两结点间的路径,从一结点到另一结点所经过的结点序列
路径长度,路径上的 分支数目 称作路径长度。
结点的带权路径长度,从该结点到树根之间的路径长度与结点上权值的乘积
树的带权路径长度,树中所有 叶子 结点的带权路径长度之和,通常记作
7.8 哈夫曼树及其应用
n
k
kk lwW PL
1
哈夫曼 (Huffman)树是一类带权路径长度最短的二叉树一,Huffman树 (最优二叉树）
1、概念
85
c
d
a b
4
2
57结点 d的路径长度为 2
结点 a,b的路径长度为 3
结点 c的路径长度为 1
结点 d的带权路径长度为 2× 4＝ 8
结点 a的带权路径长度为 7× 3＝ 21
结点 b的带权路径长度为 5× 3＝ 15
结点 c的带权路径长度为 1× 2＝ 2
WPL=(7+5)× 3+4× 2+2=46
树的带权路径长度
86
n个叶子的带权路径长度 WPL最小的二叉树成为 最优二叉树 (Huffman树 )。
哈夫曼树
a b c d
7 5 2 4
a
d
b
c
c
d
a b
4
4
2
25
5
7
7
WPLa=2× (7+5+4+2) =36
WPLb=(7+5)× 3+4× 2+2=46
WPLc=(2+4)× 3+5× 2+7=35
ca b
1.完全二叉树并不一定是 Huffman树；
2,HT权值越大的越靠近根结点；
3,HT不唯一，但 WPL
一定相等。
87
哈夫曼树构造算法,
（ 1） 根据给定的 n个权值 {w1,w2,…,w n}构成 n颗二叉树的集合 F={T1,T2,…,T n}，其中每颗二叉树 Ti只有一个权为 wi的根结点，其左右子树均空。
（ 2） 在 F中选取两颗根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
（ 3） 在 F中删除这两棵树，同时将新得到的二叉树加入 F中。
（ 4） 重复（ 2）和（ 3），直至 F只含一棵树为止，
最后得到的二叉树便是哈夫曼树。
88
哈夫曼树的构造过程
3 7 35 55
100
45
3510
3 7
55
10 45 100森林 T
4
wi li?
i=1
=3× 3+7× 3 +35× 2+55× 1 =155WPL=
89
哈夫曼树的特点
在哈夫曼树中,权值越大的结点离根越近 。
没有度为 1的结点（正则二叉树）
一颗有 n个叶子结点的哈夫曼树共有 2n-1个结点。
由二叉树的性质 1可知,n0=n2+1
n=n0+n2=n0+(n0-1)=2n0-1
哈夫曼树的存储结构（ 顺序存储 ）
#define n 7 //叶子数目
#define m 2*n-1 //结点总数
typedef struct
{ char data;
double weight;
int lchild,rchild,parent;
}HTNode;
HTNode ht[m];
说明,1.哈夫曼树所有的结点存储在数组 ht[m]中；
2,lchild,rchild,parent分别存放结点的左右孩子、
双亲结点的下标建立哈夫曼树的算法描述：
1,将哈夫曼树数组 ht[m]初始化；
for(i=0;i<m;i++)
{ht[i].parent=-1;
ht[i].lchild =-1；
ht[i].rchild =-1;
ht[i].weight=0;
}
0000000000000
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
data
2.将已知的 n个权值读入到 ht[m]中的前 n个分量中，构成森林中 n个孤立的根节点的权值；
for(i=0;i<n;i++)
{scanf(―%lf‖,&w); ht[i].weight=w;
scanf(―%c‖,&c); ht[i].data=c;
}
设已知的 7个权值为 7,5,2,3,8,10,20,分别对应于 a,b,c,d,e,f,g
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
3,对森林进行 n-1次合并，共产生 n-1个新结点，依次放入 ht[t](n≤t<m)
合并的步骤：
a.在当前森林的所有结点中，选取具有最小权值和次小权值的两个根结点，并用 lnode和 rnode记下它们的下标。 for(i=n;i<m;i++)
{ min1=min2=32767; lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1)
{ if (ht[k].weight<min1)
{ min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k; }
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k; }
} /*if*/
}
符号位 阶码 尾数
0 6416 17
浮点数在机器中的表示一般分为三部分：
符号位、阶码、尾数 。对于 double型的浮点数存储格式为：
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
lnode rnode
for(i=n;i<m;i++)
{ min1=min2=32767; lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1)
{ if (ht[k].weight<min1)
{ min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k; }
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k; }
}
}
i
b.将根为 ht[lnode]和 ht[rnode]的两棵树进行合并得到一颗新的树，此树记为 ht[i]，其左右孩子为 ht[lnode]和
ht[rnode];
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
lnode rnode i
77
5
3
2
C.重复上述两个过程直到 i=m为止
for(i=n;i<m;i++)
{/*选择最小值程序段 */
/*合并程序段 */
}
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
lnode rnode
777
5
3
2
i ilnode
rnode
88
10
7
1
程序运行的结果,
55352015105201083257
1168573-1-1-1-1-1-1-1
1095012-1-1-1-1-1-1-1
-1121211108111097789
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
ht[m]数组中哪些是叶子结点，哪是根结点？
98
哈夫曼编码具体构造方法如下,设需要编码的字符集合为
{d1,d2,…,dn},各个字符在电文中出现的次数集合为
{w1,w2,…,wn},以 d1,d2,…,dn 作为叶结点,以
w1,w2,…,wn作为各根结点到每个叶结点的权值构造一棵二叉树,规定 哈夫曼树中的左分支为 0,右分支为
1,则从根结点到每个叶结点所经过的分支对应的 0
和 1组成的序列便为该结点对应字符的编码 。 这样的编码称为哈夫曼编码 。
99
报文‘ ABACCDA’中个字符的频率为,A(3),B(1),
C(2),D(1),可设计出一颗哈夫曼树：
A
C
B D
0
0
0
1
1
1
由图可得字符 A,B,C,D的哈夫曼编码分别为：
A:0 B:110 C:10 D:111
100
为了实现构造哈夫曼编码的算法,设计存放每个结点哈夫曼编码的类型如下：
typedef struct
{
char cd[N]; /*存放当前结点的哈夫曼码 */
int start; /*存放哈夫曼码在 cd中的起始位置 */
} HCode;
HCode hcd[N];
HCode
001
0 1 2 3 4 5 6
start
101
哈夫曼编码过程方法,以所构造的哈夫曼树为基础，使用回溯法。
过程,从哈夫曼树的叶子 ht[i](0≤i<n)出发，利用双亲指针 parent找出双亲结点 ht[parent]，并判断其是双亲左孩子 /右孩子？如是左孩子，则编码 0；是右孩子则编码 1。
如此循环，直到 ht[parent]是根结点为止。
0
0
1001
1 0 0
32
55
1010
7 8
15 20
3520
55
b a
c d
e
f g
根据哈夫曼树求对应的哈夫曼编码的算法如下：
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{ int i,f,c; HCode hc;
for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码 */
{ hc.start=n-1;c=i; f=ht[i].parent;
while (f!=-1) /*循环直到无双亲结点即到达树根结点 */
{ if (ht[f].lchild==c) /*当前结点是左孩子结点 */
hc.cd[hc.start--]='0';
else /*当前结点是双亲结点的右孩子结点 */
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent; /*再对双亲结点进行同样的操作 */
}
hc.start++;/*start指向哈夫曼编码最开始字符 */
hcd[i]=hc;
}
}
103
55352015105201083257
1168573-1-1-1-1-1-1-1
1095012-1-1-1-1-1-1-1
-1121211108111097789
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
HCode hcd[N];
hc
HCode hc
0 1 2 3 4 5 6start
0cd[N]
hcd[0]
hcd[1]
hcd[N-1]
C=0 f=9
start
C=9 f=11
0
C=11 f=12
start
1
star
C=12 f=-1
4001
4010
30110
31110
4101
500
511
32
55
1010
7 8
15 20
3520
55
ab
c d
e
gf
55352015105201083257
1168573-1-1-1-1-1-1-1
1095012-1-1-1-1-1-1-1
-1121211108111097789
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
hcd[0]
hcd[1]
hcd[N-1]
4001
4010
30110
31110
4101
500
511
哈夫曼译码过程：从根结点出发，逐个读入电文中的二进制编码，如读入 0，则走向左孩子，否则走向右孩子，一直到叶子结点位置，此叶子结点便是对应的字符。如电文中的二进制未结束，则重新从根结点出发继续译码。
32
55
1010
7 8
15 20
3520
55
ab
c d
e
gf
c a deeg
0110100011110110111
106
第六章 小 结
树的概念及相关名词，树是一种层次结构
二叉树
性质（ 5个）
存储：顺序与二叉链表
树、森林与二叉树之间的转换
二叉树的遍历：遍历序列、编程方法及应用
二叉树的基本运算及实现
二叉树的构造
线索二叉树：结点结构、二叉树线索化
哈夫曼树的定义，构造及应用 End
第七章 树和二叉树数据结构
线性结构（线性表，栈，队列，串等）
非线性结构：至少存在一个数据元素有不止一个直接前驱或后继（ 树,图等）
2
7.1.1 树的定义 (形式化定义 )：
树,T＝ {K,R}。 K是包含 n个结点的有穷集合
(n>0),关系 R满足以下条件,
(1)有且仅有一个结点 k0∈ K,它对于关系 R来说没有前驱结点,结点 k0称作树的 根 。
(2)除结点 k0外,K中的每个结点对于关系 R来说都有且仅有一个前驱结点 。
(3)K中每个结点对于关系 R来说可以有多个后继结点 。
7.1 树的概念
3
7.1 树的概念
7.1.1 树的定义 (递归定义）
树 (Tree)是由 n(n>=0)个结点组成的有限集
（记为 T），对任意一颗树 T有：
（ 1）存在唯一一个称为 根 (Root)的结点；
（ 2）当 n>1时，其余的结点可分为 m(m>0)个互不相交的子集 T1,T2,T3… Tm，其中每个子集又是一棵树，并称其为根的 子树 (Subtree)。
4
A
n=1,只有根结点的树
A
B C D
E F G H I J
K L M
n>1有子树的树 根子树
N=0,空树
7.1.2 树的逻辑表示方法
1
2 3
4 5
6 7
1
2
4
5
6
7
3
凹入表表示法
1
2
4 5 36 7
文氏图表示法
1（ 2（ 4,5（ 6,7））,3）
括号表示法
结点的度,
结点拥有的子树数,
树的度：
树内各结点的度的最大值。 m次树或 m叉树,
叶子（终端结点）,度为 0的结点。
非终端结点（分支结点）,度不为 0的结点。
路径,从树中一个结点自上而下到另一个结点之间的分支构成一条路径。
路径长度,路径上的分支数目称作路径长度。
孩子,结点的子树的根称为该结点的孩子。相应地，
该结点称为孩子的双亲。 兄弟,同一双亲的孩子互为兄弟。
A
B C D
E F G H I J
K L M
7.1.3 树的基本术语
7
结点的祖先,从根到该结点所经分支上的所有结点。
结点的子孙,其子树中的任意结点
结点的层次,从根开始定义起，根为第一层，根的孩子为第二层，以此类推，可得各结点的层次。
层次,1
2
3
4
堂兄弟,其双亲在同一层的非兄弟结点互为堂兄弟。
深度,树中结点的最大层次。
有序树,如果树中结点的各子树看成从左到右是有序的，则称为有序树；否则称为无序树。
A
B C D
E F G H I J
K L M
8
森林,是 m（ m≥0) 颗互不相交的树的集合。
对于树而言，其子树的集合即为森林。
A
B C D
E F G H I J
K L M
故森林和树可以相互递归定义。
9
7.1.4 树的性质性质 1,树中的结点数等于所有结点的度数加 1。
证明：
在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点。也就是说,每个非根结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数 (度数 ),从而可得树中的结点数等于所有结点的度数加 1。
1
2 3
4 5
6 7
10
性质 2 度为 m的树中第 i层上至多有 mi-1个结点（ i≥1）。
证明 (采用数学归纳法 )
当 时,只有一个根结点,显然成立。1?i 101 mm i
假设第 层上至多有 个结点，由于 m叉树的每个结点的度至多为 m，故在第 层上的最大结点数为上一层第 层的最大结点数的 m倍。
故有 成立。
1?i 2?im
i
1?i
12 ii mmm
11
证明：
由树的性质 2可知,第 i层上最多结点数为 mi-1
(i=1,2,…,h),显然当高度为 h的 m次树 (即度为 m的树 )
上每一层都达到最多结点数时,整个 m次树具有最多结点数,因此有：
整个树的最多结点数 = 每一层最多结点数之和性质 3:高度为 h的 m次树至多有 个结点。11mmh
1210?+++mmmm h…
1
1
m
m h
证明,设具有 n个结点的 m次树的高度为 h,若在该树中前 h-1层都是满的,即每一层的结点数都等于 mi-1个
(1≤i≤h -1),第 h层 (即最后一层 )的结点数可能满,也可能不满,则该树具有最小的高度。由此可得如下关系：
性质 4:
具有 n个结点的 m次树的最小高度为)1)1((log +?mnm
1
1
1
11
<
m
mn
m
m hh
因 h只能取整数，故)1)1((log + mnh m
hmnh m?+?<? )1)1((lo g1去分母并取对数后得：
即 1)1)1((log)1)1((log ++?<?+? mnhmn
mm
hmnh m?+?<? )1)1((log1
13
(1) 树状结构中的每个结点都有一个前驱。
(2) 度为 m的树中至少有一个度为 m的结点。
判断题填空题
(1)高度为 h，度为 m的树中至少有 ______个结点，
至多有 ______个结点。
(2) 一颗共有 n个结点的树，其中所有分支结点的度均为 k，则该树中的叶子结点个数为 _____。
(3) 一颗含有 n个结点的 k叉树，可能达到的最大深度为 _____和最小深度为 _____ 。
(F)
(T)
h+m-1
1
1
m
mh
n-k+1
[n(k-1)+1]/k
Logk(n(k-1)+1)
14
7.1.5 树的基本运算树的运算主要分为三大类：
第一类,寻找满足某种特定关系的结点,
如寻找当前结点的双亲结点等；
第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第 i个孩子结点等；
第三类,遍历树中每个结点。
树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次 。 树的遍历运算的算法主要有先根遍历和后根遍历两种 。
1,先根遍历先根遍历过程为：
(1)访问根结点；
(2)按照从左到右的次序先根遍历根结点的每一棵子树。
A B E F C G D H M I J
A
B C D
E F G H I J
M
2,后根遍历后根遍历过程为：
(1)按照从左到右的次序后根遍历根结点的每一棵子树；
(2)访问根结点 。 A
B C D
E F G H I J
ME F B G C M H I J D A
7.1.6 树的存储结构
1,双亲存储结构这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置 。
a
b c
d e
f g 4g
6
4f5
1e4
1d3
0c2
0b1
-1a0
伪指针
18
a
b c
d e
f g
4g6
4f5
1e4
1d3
0c2
0b1
-1a0
伪指针找某节点的双亲,
找某节点的孩子,需扫描整个表格伪指针给出
19
2,孩子链存储结构孩子链存储结构可按树的度 (即树中所有结点度的最大值 )设计结点的孩子结点指针域个数 。
a
b c d
e
a
^^b ^^^c ^^^d
^^^e
较浪费空间特点,难查找结点的双亲
20
3,孩子兄弟链存储结构孩子兄弟链存储结构是为每个结点设计三个域：
一个数据元素域,一个指向其第一个孩子结点指针域,一个指向其下一个兄弟结点指针域。
^a
b c^
^e^
^d^
a
b c d
e
优点,有利于将一般的树转化为二叉树 (后面将详细讨论 )
不足,查找双亲结点难,
7.2.1 二叉树的概念二叉树,二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
特点,每个结点至多只有两颗子树，且子树有左右之分，
其次序不能颠倒。
7.2 二叉树概念和性质
(a)
空二叉树
A
(b)单结点的二叉树
A
L_T
(c)根和左子树
A
R_T
(d)根和右子树
A
R_TL_T
(e)根和左右子树二叉树的五种基本形态：
二叉树是度为 2的有序树？
22
满二叉树：
深度为 4的满二叉树。
层次,1 结点数,1
2 2
3 4
4 8
特点,每一层上的结点数都是最大结点数，即 2i-1。
深度为 k且有 2k-1个结点的二叉树。
该二叉数中所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层。
两类 特殊 的二叉树
1
2
4
8 9
5
10
3
6 7
11 12 13 14 15
满二叉树结点的编号方法,
根为 1,按照层数从小到大,
同一层从左到右的次序连续编号
1
2
4
8 9
5
10
3
6 7
11 12 13 14
还是满二叉树吗？
不是，因为编号为 7的结点是分支结点,但无右孩子结点,所以此二叉树不是满二叉树！
24
1
2
4
8 9
5
10
3
6 7
11 12 13
是满二叉树吗？
不是，因为编号为 7
的结点是叶子结点,
但没有位于最下一层,所以此二叉树不是满二叉树！
25
完全二叉树：
深度为 k有 n个结点的二叉树，当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至 n
的结点一一对应 (位置对应 ）时，称之为完全二叉树。
1
2
4
8 9
5
10
3
6 7
11 12
1
2
4
8
5
9
3
6 7
10 11 12
26
完全二叉树的特点：
（ 1）叶子结点只可能在层次最大的两层上出现。
（ 2）对任一结点，若其右分支下的子孙的最大层次为 k,则其左分支下的子孙的最大层次必为 k或 k+1。
（ 3）深度为 k的完全二叉树，前 k-1层结点构成的二叉树必为满二叉树。
完全二叉树又定义为：
若一颗二叉树至多只有最下面的两层上结点的度数可以小于 2，并且最下一层的结点都集中在该层最左边的若干位置上，则称此二叉树为 完全二叉树 。
1
2
4
8 9
5
10
3
6 7
11 12
7.2.2 二叉树的性质性质 1,非空二叉树上叶子结点数等于双分支结点数加 1。
设其终端结点数为 n0，度为 2的结点数为 n2，则 n0=n2+1。
证明：
210 nnnn ++?
在二叉树中，除了根结点，其余结点都有一个分支指向它，设 B为分支总数，
则 n=B+1。由于这些分支是由度为 1或为 2的结点发出的，所以有,21 2nnB +?
故,)1(12 21210 +?++?++? Bnnnnnn 120 +?n
设 n1为二叉树 T中度为 1的结点数。因为二叉树中所有结点的度均小于或等于 2，所以其结点总数为,1
2 3
4 5
6
28
已知二叉树中叶子数为 50,单分支的结点数为 30,则总结点数 。
一棵二叉树有 67个结点,这些结点的度要么是 0,要么是 2。 这棵二叉树中度为 2
的结点有 ( )个
n=n0+n1+n2=n0+n1+n0-1=2n0+n1-1
=2*50+30-1=129
n=n0+n2=n2+1+n2=2n2+1=67
故 n2＝ 33
29
性质 3,深度为 k的二叉树至多有 个结点。12?k
性质 2,在二叉树的第 i层上至多有 2i-1个结点
(i≥1)
30
1
2
4
8 9
5
10
3
6 7
11 12
性质 4 对完全二叉树中编号为 i的结点
(1≤i≤n,n≥1,n为结点数 )有：
(1) 若 i≤?n/2?,即 2i≤n,则编号为 i的结点为分支结点,否则为叶子结点 。
(2) 若 n为奇数,则每个 分支 结点都既有左孩子结点,也有右孩子结点； 若 n为偶数,则编号最大的分支结点 (编号为 n/2)只有左孩子结点,没有右孩子结点,
其余 分支 结点都有左,右孩子结点 。
31
(3) 若编号为 i的结点有左孩子结点,则左孩子结点的编号为 2i；若编号为 i的结点有右孩子结点,则右孩子结点的编号为 (2i+1)。
(4) 除树根结点外,若一个结点的编号为 i,则它的双亲结点的编号为?i/2?,也就是说,当 i为偶数时,其双亲结点的编号为 i/2,它是双亲结点的左孩子结点,当 i
为奇数时,其双亲结点的编号为 (i-1)/2,它是双亲结点的右孩子结点 。 1
2
4
8 9
5
10
3
6 7
11 12
32
性质 5 具有 n个 (n＞ 0)结点的完全二叉树的高度为?log2n+1?或?log2n?+1。
由完全二叉树的定义和树的性质 3可推出 。
参照树的性质 4的证明方法自己证明
33
(1) n(n>2)个结点的二叉树中至少有一个度为 2的结点。
(2) 不存在这样的二叉树：它有 n个度为 0的结点，
n-1个度为 1的结点,n-2个度为 2的结点。
(3) 在任何一棵完全二叉树中，终端结点或者和分支结点一样多，或者只比分支结点多一个。
(4) 完全二叉树中的每个结点或者没有孩子或者有 2个孩子。
判断题
(T)
(F)
(T)
(F)
34
7.2.3 二叉树与树、森林之间的转换
A
B C D
A
B
C
D
1,树与二叉树间的转换
将树转换成二叉树的具体过程
加线,在兄弟之间加一连线
抹线,对每个结点，除了其第一个孩子外，去除其与其余孩子之间的关系
旋转,对于横着的连线，以树的根结点为轴心，将其顺时针转 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
森林转换成二叉树 (方法一）
设森林 F={T1,T2,T3,…,Tn}，将其转化为二叉树 B
（ 1）若森林 F为空，即 n=0,则 B为空树
（ 2）若 F非空，则 B的根 root为森林中第一棵树的根
Root(T1);B的左子树是从 T1中根结点的子树森林 F1转换而成的二叉树，其右子树是从森林 {T2,T3,…,Tn}转换而成的二叉树。
2,森林与二叉树间的转换
38
A
B C D
E
F
G
H I
J
A
B C D E
F
G
H I
JB
C DC
D
B
C
D 左子树
39
A
B
C
D
E
F
G
H I
J
E
F G
H I
J
H
I
J
A
B
C
D
E
F G
H
I
J
40
森林转换成二叉树（方法二）
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
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 GH
I
J
41
二叉树转换成森林
抹线,将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原,将孤立的二叉树还原成树
A
B
C
D
E
F GH
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
42
7.3 二叉树的存储结构
顺序存储结构,把二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中，在这个存储序列中,必须能反映出结点之间的逻辑关系 。
实现的方法,将二叉树的结点元素按 满二叉树 的结点位置自上而下、自左而右存储到一个一维数组中。
顺序存储结构
#define MaxSize 100
typedef char ElemType;
typedef struct { ElemType data[MaxSize];
int n; }SqBTree;
SqBTree bt;
a
b
d
h i
e
j
c
f g
k l
逻辑关系：
结点 i的 lchild的编号为 2i
rchild的编号为 2i+1
parent的编号为?i/2?
11109876543210
lkjihgfedcba
下标 12
1
2
4
8 9
5
10
3
6 7
11 12 13 14 15
编号下标关系：
i的 lchild的下标为 2i-1
rchild的下标为 2i
parent的下标为?(i-1)/2?
1110987654321 12
0
0
0 0
a
b
d
g h
e
i
c
f
j k
编号逻辑关系,结点 i的 lchild的编号为 2i
rchild的编号为 2i+1
parent的编号为?i/2?
最坏的情况下，一个深度为 k且只有 k个结点的单支树却需要长度为 2k-1的一维数组。
1110987654321
kjihgfedcba
14013012060 15111098754321 kjihgfedcba
14
0
13
0
12
0
6
0
15111098754321
k0000f00c0a
45
链式存储结构二叉树 的结点包含结点数据元素和左右分支，所以表示二叉树的链表结点必须有,数据域,左、右指针域 。
有时为了便于查找结点双亲，在结点结构中增加一个指向 双亲的指针域。
lchild data rchild
lchild data parent rchild
二叉链表三叉链表 data
lchild rchild
parent
二叉链表的存储表示：
typedef struct node{
ElemType data;
struct node *lchild,*rchild;
} BTNode;
46
特征,含有 n个结点的二叉链表中有 n+1个空链域。
n个结点共有 2n个链域，除根结点外，其余结点均需一个链域来指出，即 n-1个链域指示 除根结点外 的其他结点，故有 2n-(n-1)=n+1个空链域,
A
B
C D
E F
G
^A
B
^C^ D
E^ ^F^
^G^
二叉链表
47
7.5 二叉树的基本运算及其实现
创建二叉树 CreateBTNode(b,str),根据二叉树括号表示法的字符串建立二叉树的二叉链表
查找结点 FindNode(b,x),在二叉树 b中寻找 data域值为 x的结点,并返回指向该结点的指针。
找孩子结点 LchildNode(p)和 RchildNode(p),分别求二叉树中结点 *p的左孩子结点和右孩子结点。
求高度 BTNodeDepth(b),求二叉树 b的高度。若二叉树为空,则其高度为 0；否则,其高度等于左子树与右子树中的最大高度加 l。
输出二叉树 DispBTNode(b),以括号表示法输出一棵二叉树。
48
说明
void CreateBTNode(BTNode * &b,char *str)
该算法将主函数传给形参 str的字符型数组进行扫描,创建一颗采用链式存储方式的二叉树,通过形参 b将所创建的二叉树根结点的地址,传,回给主函数调用处语句的对应实参。
1.创建二叉树 CreateBTNode(b,str)
char Btree[]={"A(B(D(G)),C(E,F))"};
要求调用前,与 str对应的实参数组存储的是一颗采用括号表示法表示的二叉树,如,
49
创建二叉树 CreateBTNode(b,str)
用 ch扫描采用括号表示法表示二叉树的字符串。分以下几种情况：
① 若 ch='('：则将前面刚创建的结点作为双亲结点进栈,并置 k=1,表示其后创建的结点将作为这个结点的左孩子结点；
② 若 ch=')'：表示栈中结点的左右孩子结点处理完毕,
退栈；
③ 若 ch=‘,’：表示其后创建的结点为右孩子结点；
④ 其他情况,表示要创建一个结点,并根据 k值建立它与栈中结点之间的联系,当 k=1时,表示这个结点作为栈中结点的左孩子结点,当 k=2时,表示这个结点作为栈中结点的右孩子结点。如此循环直到 str处理完毕。
A(B(D(,G)),C(E,F))
50
根据括号表达式 A(B(D(,G)),C(E,F))建立二叉链表的过程如下,建立结点 A
b
∧ ∧A
st
A (k=1)
建立结点 B
∧ ∧B
∧ ∧
B (k=1)
建立结点 D
∧ ∧D
∧ ∧
D (k=1)=2
∧ ∧G
建立结点 G
∧ ∧=2
建立结点 C
∧ ∧C
C =1
建立结点 E
∧ ∧E
∧ ∧
∧ ∧
=2
∧ ∧F
∧ ∧
51
查找结点 FindNode(b,x)
采用递归算法在二叉树 b中查找值为 x的结点。找到后返回其指针,否则返回 NULL。 算法如下：
BTNode *FindNode(BTNode *b,ElemType x)
{ BTNode *p;
if (b==NULL) return NULL;
else if (b->data==x) return b;
else
{ p=FindNode(b->lchild,x);
if (p!=NULL) return p;
else return FindNode(b->rchild,x);
}
}
52
找孩子结点 LchildNode(p)和 RchildNode(p)
直接返回 *p结点的左孩子结点或右孩子结点的指针。 算法如下：
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
A
B
C D
E F
53
求高度 BTNodeDepth(b)
求二叉树的高度的递归模型 f()如下：
int BTNodeDepth(BTNode *b)
{ int lchildh,rchildh;
if (b==NULL) return(0); /*空树的高度为 0*/
else
{ lchildh=BTNodeDepth(b->lchild);
rchildh=BTNodeDepth(b->rchild);
return(lchildh>rchildh)?
(lchildh+1):(rchildh+1);
}
}
A
B
C D
E F
+>?>?
其它若
1)}((),(max{
NULLb0)(
rchildbflchildbfbf
54
7.5 二叉树的遍历遍历二叉树,按一定的次序访问二叉树中所有结点，且每个结点仅被访问一次。它是最基本的运算，
是二叉树中所有其他运算的基础。
“遍历,是任何类型均有的操作，对线性结构而言，
只有一条搜索路径（因为每个结点只有一个后继），
故不需要另加讨论。而二叉树是非线性结构，有些结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。
55
7.5.1二叉树遍历概念与 7.1.5(p170)所介绍过的一般树的遍历相似，
二叉树遍历也是按照一定的次序访问二叉树中所有的结点,且每个结点仅访问一次的过程。但二叉树有自身的特点,共有三种遍历方法：
.先序遍历
.中序遍历
.后序遍历
56
1,先序遍历先序遍历二叉树的过程是：
(1)访问根结点；
(2)先序遍历 左子树；
(3)先序遍历 右子树 。
A
B C
FED
G
A B D GC E F
所有结点都访问过一遍，遍历结束。
先序遍历序列,
(设访问根结点的操作为输出该结点 )
57
void PreOrder(BTNode *b) /*先序遍历的递归算法 */
{
if (b!=NULL)
{ printf("%c ",b->data); /*访问根结点 */
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
58
2,中序遍历中序遍历二叉树的过程是：
(1)中序遍历 左子树；
(2)访问根结点 ；
(3)中序遍历 右子树 。
A
B C
FED
G
G B A E C FD
所有结点都访问过一遍，遍历结束。
中序遍历序列,
/*中序遍历的递归算法 */
void InOrder(BTNode *b)
{
if (b!=NULL)
{ InOrder(b->lchild);//中序遍历左子树
printf("%c ",b->data); //访问根结点
InOrder(b->rchild); //中序遍历右子树
}
}
60
A
B C
FED
G
G D B E F C A
3,后序遍历后序遍历二叉树的过程是：
(1)后序遍历 左子树；
(2)后序遍历 右子树；
(3)访问根结点 。
所有结点都访问过一遍，遍历结束。
后序遍历序列,
/*后序遍历递归算法 */
void PostOrder(BTNode *b)
{
if (b!=NULL)
{ PostOrder(b->lchild);//后序遍历左子树
PostOrder(b->rchild);//后序遍历右子树
printf("%c ",b->data); //访问根结点
}
}
62
二叉树遍历算法小结：
A
B C
FED
G
A B D GC E F
G B A E C FD
G D B E F C A
先序序列,
中序序列,
后序序列,
先序遍历中序遍历后序遍历由此可见,不论使用何种方式，遍历结果都是一个线性表,因而遍历一颗二叉树实质上是对其进行线性化的操作。
63
层次遍历从 上到下、从左到右 的次序遍历二叉树右图的二叉树的层次遍历次序为：
A B C D E F G
A
B
C D
E F
G遍历二叉树的算法分析：
时间复杂度,遍历的基本操作是访问结点，则不论按何种次序遍历，对含有 n个结点的二叉树，其时间复杂度为 O(n)
64
7.6 二叉树的构造
定理 7.1：任何 n(n≥0) 个不同结点的二又树,都可由它的中序序列和先序序列惟一地确定。
a
b c b
c
a c
a
b
a
b c
先序序列 中序序列例 已知结点的先序序列和中序序列分别为：
先序序列,A B C D E F G
中序序列,C B E D A F G。求此二叉树
A
C
B
E
D
F
G
先序,BCDE
中序,CBED
先序,FG
中序,FG
A
B
C E
D
F
G
先序,DE
中序,ED
A
B
C
F
GD
E
前题：确定树的根及其左右子树
66
1.用先序序列的第一个结点作为根结点 ;
2.在中序序列中查找根结点的位置,并以此为界将中序序列划分为左,右两个序列 (左,右子树 );
3.根据左,右子树的中序序列中的结点个数,将前序序列去掉根结点后的序列划分为左,右两个序列,
它们分别是左,右子树的前序序列 ;
4.对左,右子树的前序序列和中序序列递归地实施同样方法,直到所得左,右子树为空 。
67
BTNode *CreateBT1(char *pre,char *in,int n)
{ //根据先序和中序序列构造 n个结点的二叉树
BTNode *s; char *p; int k;
if (n<=0) return NULL;
s=(BTNode *)malloc(sizeof(BTNode)); //创建结点 *s
s->data=*pre;
for (p=in;p<in+n;p++) //在中序中找为 *ppos的位置 k
if (*p==*pre)
break;
k=p-in;
s->lchild=CreateBT1(pre+1,in,k) ;//递归构造左子树
s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);
//构造右子树
return s;
}
68
定理 7.2：任何 n(n＞ 0)个不同结点的二又树,
都可由它的中序序列和后序序列惟一地确定。
任何 n(n＞ 0)个不同结点的二又树,都可由它的先序序列和后序序列惟一地确定？
69
7.7 线索二叉树
1.问题的提出,通过遍历二叉树可得到结点的一个线性序列，在线性序列中，就存在前驱和后继。
但是以二叉链表作存储结构时，只能找到结点的左、右孩子，不能直接得到结点在任一序列中的前驱和后继。因为结点的前驱和后继只有在遍历过程中才能得到，那么能否通过结点的两个链域查找结点的前驱和后继呢？
70
7.7 线索二叉树
2.分析：
n个结点二叉链式存储中共有 2n个链域，其中,n+1个空链域,n-1个指针域；
n个结点的遍历序列中有 n-1个前驱和 n-1个后继；
因此，我们考虑用空链域来存放结点的前驱和后继。线索化二叉树就是利用 n+1个空链域来存放结点的前驱和后继结点的信息。
71
7.7 线索二叉树
3,线索化二叉树：
lchild ltag data rtag rchild
其中：
ltag=
1 lchild域指向结点的前驱,为 线索
0 lchild域指向结点的左孩子
rtag=
1 rchild域指向结点的后继，为 线索
0 rchild域指向结点的右孩子
(1)结点结构在二叉链表中增加 ltag和 rtag两个标志域
72
二叉树的二叉线索存储表示
typedef int elemtype;
typedef struct node{
elemtype data;
int ltag,rtag;
struct node *lchild,*rchild;
}TBTNode;
以上述结点结构构成的二叉链表叫 线索链表 。
线索二叉树,加上线索的二叉树
线索化,对二叉树以 某种次序遍历 使其变为线索二叉树的过程，即将二叉链表中空的指针域修改为线索。
73
/
b
—
+
a * e f
—
c d
NULLNULL
中序线索化,a + b * c – d –e / f
下面主要以中序序列来介绍其线索化过程及其相应的操作先序遍历序列,- + a * b - c d / e f
后序遍历序列,-+a *b -c d /e f
74
7.7 线索二叉树
3,线索化二叉树：
(2) 整体结构增设一个头结点，令其 lchild指向二叉树的根结点,ltag=0,rtag=1;
并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；
最后用头指针 root指示该头结点。
中序线索化
/
b
—
+
a * e f
—
c d
a + b * c – d –e / f
10
0—0
0+0 0/0
1a1 0*0 1e1 1f1
1b1 0—0
1c1 1d1
root
76
线索化的实质 是将二叉链表中的空指针改为指向其前驱或后继的线索,而前驱和后继的信息只有在遍历时才能得到,
故线索化即为在遍历的过程中修改空指针的操作。
中序线索化：
结点 b,
(1)不存在左孩子即,p->lchild==NULL，需将其左链域改为线索，标志域也置为 1
p->lchild=pre; p->ltag=1;
二叉树线索化的实现
pre
p a
b c
(2)存在左孩子，仅需将标识域置 0即可
p->ltag=0;
所以对当前结点 p，线索化时需完成两个操作：
p的前驱结点 pre的后继线索化（根据前驱结点的 rtag或
rchild来判断是否需要）
p结点的前驱线索化（根据其有无空链域来判断）
结点 pre,
(1)不存在右孩子即,pre->lchild==NULL，需将其右链域改为线索，
标志域也置为 1
pre->rchild=p; pre->rtag=1;
(2)存在右孩子，仅需将标识域置 0即可
pre->rtag=0;
pre
a
b c
p
TBTNode *pre; /*全局变量 */
void Thread(TBTNode *&p) /*对二叉树 b进行中序线索化 */
{ if (p!=NULL)
{ Thread(p->lchild); /*左子树线索化 */
if (p->lchild==NULL) /*前驱线索 */
{ p->lchild=pre; p->ltag=1;}/*建立当前结点的前驱线索 */
else p->ltag=0;
if (pre->rchild==NULL) /*后继线索 */
{ pre->rchild=p;pre->rtag=1;}/*建立前驱结点的后继线索 */
else pre->rtag=0;
pre=p;
Thread(p->rchild); /*右子树线索化 */
}
}
a
b c
执行完上述程序后,pre和 p分别指向哪？
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树 */
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=root;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b;
pre=root;
Thread(b); /*中序遍历线索化二叉树 */
pre->rchild=root; /*最后处理,加入指向头结点的线索 */
pre->rtag=1;
root->rchild=pre; /*头结点右线索化 */
}
return root;
}
10
root
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树 */
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=root;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b;
pre=root;
Thread(b);
pre->rchild=root;
pre->rtag=1;
root->rchild=pre;
}
return root;
}
10
root
b
TBTNode *CreaThread(TBTNode *b) //中序线索化二叉树
{ TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点 */
root->ltag=0;root->rtag=1; root->rchild=root;
if (b==NULL) root->lchild=root; /*空二叉树 */
else
{ root->lchild=b; pre=root;
Thread(b); pre->rchild=root;
pre->rtag=1;root->rchild=pre;
}
return root;
}
10
root
b
中序次序的最后节点
pre
线索二叉链表的应用举例
查找某结点 *p在指定次序下的前驱和后继例：在中序线索二叉树中查找结点 *p的中序后继结点。
当 rtag=1时,rchild直接给出后继；当 rtag=0时，后继为遍历右子树时访问的第一个结点，也就是从 *p的右孩子开始，沿左指针链往下找，直到找到一个没有左孩子的结点为止。
p
R
bithptr *InOrderNext( bithptr * p)
//在中序线索二叉链表中找结点 p的中序后继
{if(p->rtag= =1) return (p->rchild);
else {q=p->rchild;
while(q->ltag= =0) q=q->lchild;
return (q);
} }
例：在中序线索二叉树中查找结点 *p的中序前驱结点。
(1) 当 ltag=1时,lchild直接给出前驱；
(2)当 ltag=0时，左链为指针，没直接给出其前驱的信息，但根据中序遍历规律可知，结点的前驱是遍历其左子树时最后访问的结点。
R1
R2
Rn
最右下结点
bithptr *InOrderPre( bithptr *p)
//在中序线索二叉链表中找结点 p的中序前驱
{if(p->ltag= =1) return (p->lchild);
else {q=p->lchild;
while(q->rtag= =0) q=q->rchild;
return (q);
} }
p
84
两结点间的路径,从一结点到另一结点所经过的结点序列
路径长度,路径上的 分支数目 称作路径长度。
结点的带权路径长度,从该结点到树根之间的路径长度与结点上权值的乘积
树的带权路径长度,树中所有 叶子 结点的带权路径长度之和,通常记作
7.8 哈夫曼树及其应用
n
k
kk lwW PL
1
哈夫曼 (Huffman)树是一类带权路径长度最短的二叉树一,Huffman树 (最优二叉树）
1、概念
85
c
d
a b
4
2
57结点 d的路径长度为 2
结点 a,b的路径长度为 3
结点 c的路径长度为 1
结点 d的带权路径长度为 2× 4＝ 8
结点 a的带权路径长度为 7× 3＝ 21
结点 b的带权路径长度为 5× 3＝ 15
结点 c的带权路径长度为 1× 2＝ 2
WPL=(7+5)× 3+4× 2+2=46
树的带权路径长度
86
n个叶子的带权路径长度 WPL最小的二叉树成为 最优二叉树 (Huffman树 )。
哈夫曼树
a b c d
7 5 2 4
a
d
b
c
c
d
a b
4
4
2
25
5
7
7
WPLa=2× (7+5+4+2) =36
WPLb=(7+5)× 3+4× 2+2=46
WPLc=(2+4)× 3+5× 2+7=35
ca b
1.完全二叉树并不一定是 Huffman树；
2,HT权值越大的越靠近根结点；
3,HT不唯一，但 WPL
一定相等。
87
哈夫曼树构造算法,
（ 1） 根据给定的 n个权值 {w1,w2,…,w n}构成 n颗二叉树的集合 F={T1,T2,…,T n}，其中每颗二叉树 Ti只有一个权为 wi的根结点，其左右子树均空。
（ 2） 在 F中选取两颗根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
（ 3） 在 F中删除这两棵树，同时将新得到的二叉树加入 F中。
（ 4） 重复（ 2）和（ 3），直至 F只含一棵树为止，
最后得到的二叉树便是哈夫曼树。
88
哈夫曼树的构造过程
3 7 35 55
100
45
3510
3 7
55
10 45 100森林 T
4
wi li?
i=1
=3× 3+7× 3 +35× 2+55× 1 =155WPL=
89
哈夫曼树的特点
在哈夫曼树中,权值越大的结点离根越近 。
没有度为 1的结点（正则二叉树）
一颗有 n个叶子结点的哈夫曼树共有 2n-1个结点。
由二叉树的性质 1可知,n0=n2+1
n=n0+n2=n0+(n0-1)=2n0-1
哈夫曼树的存储结构（ 顺序存储 ）
#define n 7 //叶子数目
#define m 2*n-1 //结点总数
typedef struct
{ char data;
double weight;
int lchild,rchild,parent;
}HTNode;
HTNode ht[m];
说明,1.哈夫曼树所有的结点存储在数组 ht[m]中；
2,lchild,rchild,parent分别存放结点的左右孩子、
双亲结点的下标建立哈夫曼树的算法描述：
1,将哈夫曼树数组 ht[m]初始化；
for(i=0;i<m;i++)
{ht[i].parent=-1;
ht[i].lchild =-1；
ht[i].rchild =-1;
ht[i].weight=0;
}
0000000000000
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
data
2.将已知的 n个权值读入到 ht[m]中的前 n个分量中，构成森林中 n个孤立的根节点的权值；
for(i=0;i<n;i++)
{scanf(―%lf‖,&w); ht[i].weight=w;
scanf(―%c‖,&c); ht[i].data=c;
}
设已知的 7个权值为 7,5,2,3,8,10,20,分别对应于 a,b,c,d,e,f,g
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
3,对森林进行 n-1次合并，共产生 n-1个新结点，依次放入 ht[t](n≤t<m)
合并的步骤：
a.在当前森林的所有结点中，选取具有最小权值和次小权值的两个根结点，并用 lnode和 rnode记下它们的下标。 for(i=n;i<m;i++)
{ min1=min2=32767; lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1)
{ if (ht[k].weight<min1)
{ min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k; }
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k; }
} /*if*/
}
符号位 阶码 尾数
0 6416 17
浮点数在机器中的表示一般分为三部分：
符号位、阶码、尾数 。对于 double型的浮点数存储格式为：
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
lnode rnode
for(i=n;i<m;i++)
{ min1=min2=32767; lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1)
{ if (ht[k].weight<min1)
{ min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k; }
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k; }
}
}
i
b.将根为 ht[lnode]和 ht[rnode]的两棵树进行合并得到一颗新的树，此树记为 ht[i]，其左右孩子为 ht[lnode]和
ht[rnode];
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
lnode rnode i
77
5
3
2
C.重复上述两个过程直到 i=m为止
for(i=n;i<m;i++)
{/*选择最小值程序段 */
/*合并程序段 */
}
000000201083257
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
-1-1-1-1-1-1-1-1-1-1-1-1-1
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
lnode rnode
777
5
3
2
i ilnode
rnode
88
10
7
1
程序运行的结果,
55352015105201083257
1168573-1-1-1-1-1-1-1
1095012-1-1-1-1-1-1-1
-1121211108111097789
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
ht[m]数组中哪些是叶子结点，哪是根结点？
98
哈夫曼编码具体构造方法如下,设需要编码的字符集合为
{d1,d2,…,dn},各个字符在电文中出现的次数集合为
{w1,w2,…,wn},以 d1,d2,…,dn 作为叶结点,以
w1,w2,…,wn作为各根结点到每个叶结点的权值构造一棵二叉树,规定 哈夫曼树中的左分支为 0,右分支为
1,则从根结点到每个叶结点所经过的分支对应的 0
和 1组成的序列便为该结点对应字符的编码 。 这样的编码称为哈夫曼编码 。
99
报文‘ ABACCDA’中个字符的频率为,A(3),B(1),
C(2),D(1),可设计出一颗哈夫曼树：
A
C
B D
0
0
0
1
1
1
由图可得字符 A,B,C,D的哈夫曼编码分别为：
A:0 B:110 C:10 D:111
100
为了实现构造哈夫曼编码的算法,设计存放每个结点哈夫曼编码的类型如下：
typedef struct
{
char cd[N]; /*存放当前结点的哈夫曼码 */
int start; /*存放哈夫曼码在 cd中的起始位置 */
} HCode;
HCode hcd[N];
HCode
001
0 1 2 3 4 5 6
start
101
哈夫曼编码过程方法,以所构造的哈夫曼树为基础，使用回溯法。
过程,从哈夫曼树的叶子 ht[i](0≤i<n)出发，利用双亲指针 parent找出双亲结点 ht[parent]，并判断其是双亲左孩子 /右孩子？如是左孩子，则编码 0；是右孩子则编码 1。
如此循环，直到 ht[parent]是根结点为止。
0
0
1001
1 0 0
32
55
1010
7 8
15 20
3520
55
b a
c d
e
f g
根据哈夫曼树求对应的哈夫曼编码的算法如下：
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{ int i,f,c; HCode hc;
for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码 */
{ hc.start=n-1;c=i; f=ht[i].parent;
while (f!=-1) /*循环直到无双亲结点即到达树根结点 */
{ if (ht[f].lchild==c) /*当前结点是左孩子结点 */
hc.cd[hc.start--]='0';
else /*当前结点是双亲结点的右孩子结点 */
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent; /*再对双亲结点进行同样的操作 */
}
hc.start++;/*start指向哈夫曼编码最开始字符 */
hcd[i]=hc;
}
}
103
55352015105201083257
1168573-1-1-1-1-1-1-1
1095012-1-1-1-1-1-1-1
-1121211108111097789
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
HCode hcd[N];
hc
HCode hc
0 1 2 3 4 5 6start
0cd[N]
hcd[0]
hcd[1]
hcd[N-1]
C=0 f=9
start
C=9 f=11
0
C=11 f=12
start
1
star
C=12 f=-1
4001
4010
30110
31110
4101
500
511
32
55
1010
7 8
15 20
3520
55
ab
c d
e
gf
55352015105201083257
1168573-1-1-1-1-1-1-1
1095012-1-1-1-1-1-1-1
-1121211108111097789
0 1 2 3 4 5 6 7 8 9 10 11 12
lchild
parent
rchild
weight
gfedcbadata
hcd[0]
hcd[1]
hcd[N-1]
4001
4010
30110
31110
4101
500
511
哈夫曼译码过程：从根结点出发，逐个读入电文中的二进制编码，如读入 0，则走向左孩子，否则走向右孩子，一直到叶子结点位置，此叶子结点便是对应的字符。如电文中的二进制未结束，则重新从根结点出发继续译码。
32
55
1010
7 8
15 20
3520
55
ab
c d
e
gf
c a deeg
0110100011110110111
106
第六章 小 结
树的概念及相关名词，树是一种层次结构
二叉树
性质（ 5个）
存储：顺序与二叉链表
树、森林与二叉树之间的转换
二叉树的遍历：遍历序列、编程方法及应用
二叉树的基本运算及实现
二叉树的构造
线索二叉树：结点结构、二叉树线索化
哈夫曼树的定义，构造及应用 End
