2001 -- 12 --27
华中科技大学计算机学院 (8)数据结构
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树
6.3.2 建立 (生成 )二叉树
6.3.3 线索二叉树
6.3.4 表达式二叉树表达式二叉树 T = (第一操作数 ) (运算符 ) (第二操作数 )
其中：第一操作数、第二操作数也是表达式二叉树，
分别为表达式二叉树 T的左子树和左子树运算符第一操作数左二叉树第二操作数右二叉树表达式二叉树例 表达式,A + B * C - D /（ E - F）
-
+ /
A * D -
B C E F
● 前序遍历,- + A * B C / D - E F
前缀表示,前缀表达式,波兰式
● 中序遍历,A + B * C - D /( E - F )
中缀表示,中缀表达式
● 后序遍历,A B C * + D E F - / -
后缀表示,后缀表达式，逆波兰式表达式二叉树
6.3.5 中序遍历序列和前 (或后 )序序列确定唯一棵二叉树
B
A
C
D
E
T1
B
A
C
D
E
T2例 1,给定二叉树 T的中序序列,B A C D E G F
前序序列,E A B C D F G
如何求二叉树 T？
由前序序列,A D E B C
和 (或 )后序序列,E D C B A
不能确定唯一棵二叉树
E
B,A,C,D G,F
E
A F
B C G
D
6.3.5 中序遍历序列和前 (或后 )序序列确定唯一棵二叉树例 2,给定二叉树 T的后序序列,B G H E C A J I F D
中序序列,B A C G E H D I J F
如何求二叉树 T？
D
B,A,C
G,E,H I,J,F
6.3.5 中序遍历序列和前 (或后 )序序列确定唯一棵二叉树例 2,给定二叉树 T的后序序列,B G H E C A J I F D
中序序列,B A C G E H D I J F
如何求二叉树 T？
D
B,A,C
G,E,H I,J,F
D
A F
B C I
E
G H
J
二叉树 T
6.3.6 中序遍历 非递归算法
递归算法简明精炼,但效率较低,实际应用中常使用非递归；
某些高级语言不支持递归；
非递归算法思想：
（ 1） 设置一个栈 S存放所经过的根结点 （ 指针 ） 信息；
初始化 S；
（ 2） 第一次访问到根结点并不访问,而是入栈；
（ 3） 中序遍历它的左子树,左子树遍历结束后,第二次遇到根结点,就将根结点 （ 指针 ） 退栈,并且访问根结点；然后中序遍历它的右子树 。
（ 4） 当需要退栈时,如果栈为空则结束 。
A
B C
D E
t
A
A
B C
D E
t
B
A
A
B C
D E
t
D
B
A
A
B C
D E
t=NULL,表示 D的左子树遍历结束根进栈根进栈 根进栈
D
B
A
A
B C
D E
退栈?t,访问 D，
t->rchild?t B
A
A
B C
D E
t=NULL,表示 B的左子树遍历结束退栈?t,访问 B，
t->rchild?t
E
A
A
B C
D E
A
B C
D E tA
根进栈
t=NULL,表示 E的左子树遍历结束
D
D B
t=NULL,表示 D的左子树遍历结束
E
A
A
B C
D E
退栈?t,访问 E，
t->rchild?t
A
A
B C
D E
t=NULL,表示 A的左子树遍历结束退栈?t,访问 A，
t->rchild?t
C
A
B C
D E
A
B C
D E t
根进栈
t=NULL,表示 C的左子树遍历结束
D B E
D B E A
t=NULL,表示 E的左子树遍历结束退栈?t,访问 C，
t->rchild?t
A
B C
D E
t=NULL,并且栈 S
为空，遍历结束
C
A
B C
D E
t=NULL,表示 C的左子树遍历结束 D B E A C
void Midorder(struct BiTNode *t) //t为根指针
{ struct BiTNode *st[maxleng+1];//定义指针栈 st[0..maxleng]
int top=0； //置空栈
do
{ while(t) //根指针 t表示的为非空二叉树
{ if (top==maxleng) exit(OVERFLOW)； //栈已满,退出
st[++top]=t； //根指针进栈
t=t->lchild； //t移向左子树
} //循环结束表示以栈顶元素的指向为
//根结点的二叉树的左子树遍历结束
if (top) //为非空栈
{ t=st[top--]； //弹出根指针
printf("%c",t->data)； //访问根结点
t=t->rchild； //遍历右子树
}
} while(top||t)； //父结点未访问,或右子树未遍历
}
6.3.7 遍历二叉树的 应用例,求二叉树中结点的个数
int preorder(struct BiTNode *root)
//求二叉树中结点的个数
{ int n=0 ;
if (root)
{ n=1； //根结点计数
n+=preorder(root->lchild)； //递归计算左子树
n+=preorder(root->rchild)； //递归计算右子树
}
return n;
}
main()
{ int n； //n为计数器,假定二叉树已生成
n=preorder(root)； //root为指针,执行 preorder(root,&n)
printf("%d",n)； //输出 n
}
例：将二叉数线索化 （ 中序 ） 。
T的中序序列,B,D,C,E,A,F,G F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的中序线索二叉树
NULL
NULL
0 A 0
root
中序线索二叉树链表
1 F 01 B 0
1 G 10 C 0
1 D 1 1 E 1
NULL
NULL
结点结构：
void creat_thread(struct BiTNode *t) //t为根指针
{ struct BiTNode *st[maxleng+1],pre=NULL; //前驱结点指针
int top=0； //置空栈
do
{ while(t) //根指针 t表示的为非空二叉树
{ if (top==maxleng) exit(OVERFLOW)； //栈已满,退出
st[++top]=t； //根指针进栈
t=t->lchild； //t移向左子树
}
0/1 0/1
lchild ltag data rtag rchild
左小孩 左标志 结点值 右标志 右小孩或前趋 或后继
if (top) //为非空栈
{ t=st[top--]； //弹出根指针
printf(“%c”,t->data)； //访问根结点
if (t->lchild!=NULL) t->ltag=0; //左指针为孩子
else {
t->ltag=1;t->lchild=pre; } //左指针为线索
if (pre!=NULL)
if (pre->rchild!=NULL)
pre->rtag=0; //右指针为孩子
else {
pre->rtag=1; //右指针为线索
pre->rchild=t;
}
pre=t; //pre与 t保持前后
t=t->rchild； //遍历右子树
}
} while(top||t)；
}
先序线索二叉树的遍历,
void (struct BiTNode *t) //t为根指针
{ p=t;
while (p)
{
printf(“%6c”,p->data);
if (p->ltag==0) //有左孩子时,p移向左孩子结点
p=p->lchild;
else //p移向右孩子或右线索指向的结点
p=p->rchild;
}
}
中序线索二叉树的遍历,
void (struct BiTNode *t) //t为根指针
{ p=t;
if (p!=NULL) while (p->lchild!=NULL)
p=p->lchild; //查找二叉树的最左结点 (第 1个结点 )
printf(“%6c”,p->data);
while (p->rchild!=NULL) // p有后继结点
{if (p->rtag==1) p=p->rchild; //p无右孩子时为线索
else{p=p->rchild; //p有右孩子时，取右子树最左结点
while (p->ltag!=1) p=p->lchild;}
printf(“%6c”,p->data);
}
}
6.4 树和森林
6.4.1 树的存储结构
1.双亲表示法 /数组表示法 /顺序表示法
A
B C
ED F
树
G
A 0
B 1
C 1
D 3
E 3
F 3
G 4
data parent
1
2
3
4
5
6
7
struct snode
{ char data；
int parent；
}t[maxleng+1}；
t[1..7}
2.孩子表示法 /链接表表示法
(1)固定大小的结点格式,设树 T的度为 n
A
B C
ED F
树 T
G
A ∧
B ∧ ∧ ∧ C
D ∧ ∧ E ∧ ∧ ∧ F ∧ ∧ ∧
G ∧ ∧ ∧
root
T的链接表结点值
...
data child1
childn
2.孩子表示法 /链接表表示法
(2)非固定大小的结点格式
A
B C
ED F
树
G
A 2
B 0 C 3
D 1
root
链接表
E 0 F 0
G 0
结点 值 结点的度 n,..
data degree child1
childn
3.孩子兄弟表示法 /二叉树表示法 /二叉链表
A
B C
ED F
树
J
root
二叉链表结点值
firstchild data nextbrother
G
IH K
左 孩子右兄弟
A ∧
B
∧ F ∧E∧ D
∧ K ∧∧ J∧ I ∧∧ H
C ∧
G ∧
3.孩子兄弟表示法 /二叉树表示法 /二叉链表
A
B C
ED F
树
J
root
二叉链表结点值
firstchild data nextbrother
G
IH K
左 孩子 右兄弟
A ∧
B
∧ F ∧
E
∧ D
∧ K ∧
∧ J
∧ I ∧
∧ H
C ∧G ∧
4.孩子链表表示法 /单链表表示法
A
B C
ED F
树
J
结点 值
data first
G
IH K
表头结点第一个孩子 序号 值孩子结点 /表结点下一个孩子
child next
A
B
C
D ∧
E
F ∧
G
H ∧
I ∧
J ∧
K ∧
6 ∧4
7 ∧
2
5
10
8
1
2
3
4
5
6
7
8
9
10
11
3 ∧
11 ∧
9 ∧
表头结点数组
5.带双亲的孩子链表表示法
A
B C
ED F
树
J
结点 值
data parent first
G
IH K
表头结点第一个孩子 序号 值孩子结点 /表结点下一个孩子
child next
A 0
B 1
C 1
D 3 ∧
E 3
F 3 ∧
G 2
H 7 ∧
I 7 ∧
J 5 ∧
K 5 ∧
6 ∧4
7 ∧
2
5
10
8
1
2
3
4
5
6
7
8
9
10
11
3 ∧
11 ∧
9 ∧
表头结点数组
6.4.2 树与二叉树的转换
1.树 二叉树
A
B C
GF H
L
D
JI M
E
K
A
B C
GF H
树
L
D
JI M
E
K
1.在兄弟之间加连线A
B C
GF H
L
D
JI M
E
K
2.保留根与最左孩之间的连线删除与其它孩子 之间的连线
1.树 二叉树
A
B C
GF H
L
D
JI M
E
K
A
B
K G
E
H
L
D C
I
M
J
F
3.以根为轴心顺时针方向旋转 45度二叉树
2.保留根与最左孩之间的连线删除与其它孩子 之间的连线
2.森林 二叉树
A J
E
CB D
L
G
IH
M
K
F
T1 T2 T3 T4
A J
E
CB D
L
G
IH
M
K
F
A J
E
C
B
D
L
G
I
H
M
K
F
B1 B2 B3 BT4
A J
E
C
B
D
L
G
I
H
M
K
F
B1 B2 B3 BT4
加线 拆线之后旋转后 变为多棵二叉树 连成一棵二叉树
A
JE
C
B
D
L
G
I
H
M
K
F
2.森林 二叉树
A J
E
CB D
L
G
IH
M
K
F
T1 T2 T3 T4
森林 F={T1,T2,T3,T4}
旋转后,变为一棵二叉树
A
F
D
B
G
3,二叉树 树
A
DB G
树 T
二叉树 B
I
C
E
H
E
C
H
F I
J
A
F
D
B
G
I
C
E
H J
A
F
D
B
G
I
C
E
H J
J
例 1
A
F
D
B
G
3,二叉树 森林
A
DB G
二叉树 B
C
E
E
C F
H
I
J K
A
F
D
B
G
C
E
H
I
J K
A
F
D
B
G
C
E
H
I
J K
H
J
I K
T2 T4T3T1
例 2
6.4.3 树和森林的遍历
1.树的遍历
A
B C
ED F
J
G
IH K
前根遍历,A B G H I C D E J K F
后根遍历,H I G B D J K E F C A
2.森林的遍历
D
G
IH L
J
A
CB
K
F
E 前序遍历,A B C D E F G H I J K L
后序遍历,B D C A F E H J K I L G
（ 依次对每一棵树后序遍历）
6.6 哈夫曼（ Huffman)树及其应用
1.路径长度 ----路径上分枝的数目 (连线的数目 )
2.树 T的路径长度 ----从树 T的根到其余每个结点的路径长度之和记作 PL(T)
T1 T2 T3
PL(T1)=1+1+2+2+2=8
PL(T2)=1+2+3+4+5=15
PL(T1)=1+1+2+3+3=10
● 当 n个结点的二叉树为完全二叉树时,PL(T)具有 最小值：
∵ 结点 i的层 =?log2i? + 1
树 T的根到 结点 i的路径长度 = 结点 i的层 -1 =?log2i?
n
∴ PL(T)=?log21?+?log22?+...+?log2n? = ∑?log2i?i=1
● 当 n个结点的二叉树为单枝树时,PL(T)具有最大值：
PL(T)=0+1+2+...+(n-1) = n(n-1)/2
3,树 T的带权路径长度 ----每个叶子的权与根到该叶子的路径长度的乘积之和，记作 WPL(T)
n
WPL(T) = ∑ wklk
i=1
其中,n --- 树 T的 叶子数目 wk--- 叶子 i的权
lk--- 树 T的根到叶子 i的路径长度
T1
4
8
5
9
7
6 WPL(T)=6*1+3*2+4*3+9*3=51
3
4.哈夫曼树 /最佳树 /最优树 ----
在具有 n个相同叶子的各二叉树中,WPL(T)最小的二叉树。
T1
5
3
14
6
28
14
● PL(T1)=1+1+2+2+2+2+3+3=16
● WPL(T1)=5*3+6*3+3*2+4*2+10*2=67
● PL(T2)=1+1+2+2+3+3+4+4=20
● WPL(T2)=10*1+6*2+5*3+4*4+3*4=65
● PL(T3)=1+1+2+2++2+2+3+3=16
● WPL(T3)=5*3+6*3+3*2+4*2+10*2=63
4 1011
T2 3
7
10
4
28
18
6 12
5 3
6
11
4
28
17
7 105
T3
5.哈夫曼算法例 给定权集合 {4,5,3,6,10}，构造 哈夫曼树
1.按权值大小排序,3,4,5,6,10
2.生成森林：
53 64 10
T1 T2 T3 T4 T5
3.合并两棵权最小的二叉树,并排序,直到为一棵二叉树：
5
3
6
4
107
5 6
11
3 4
107
3 4
107
17
5 6
11
3 4
107
17
5 6
11
28
6.最小冗余码 /哈夫曼码
● ASCII码 /定长码
ab12,01100001 01100010 00110001 00110010
97 98 49 50
● 哈夫曼码 /不定长码能按字符的使用频度,使文本代码的总长度具有最小值。
例,给定有 18个字符组成的文本：
A A D A T A R A E F R T A A F T E R
求各字符的 哈夫曼码。
(1) 统计：
字 符 A D E F T R
频 度 7 1 2 2 3 3
(2) 构造 Huffman树：
21 32 3 7
(2) 构造 Huffman树：
21 32 3 7
3 2
1
3
2
3 73
合并 1和 2 排序排序
5
2
1
3
2
3 73
合并 2和 3
5
2
1
3
2
3 7
3
(2) 构造 Huffman树：
排序
5
2
1
3
2
3 7
3
6
合并 3和 3
3 3
65
2
1 2
3
7
排序
3 3
65
2
1 2
3
7
11
合并 5和 6
3 3
65
2
1 2
3
117
(2) 构造 Huffman树,(3) 在左分枝标 0,右分枝标 1,
合并 7和 11
3 3
65
2
1 2
3
117
18
Huffman树字 符 A D E F T R
频 度 7 1 2 2 3 3
编 码 0 1010 1011 100 110 111
(4) 确定 Huffman编码：
特点,任一编码不是其它编码的 前缀
3 3
65
2
1 2
3
117
18
0
0
0
0
0
1
1
1
1
1
RTF
ED
A
如何译码？
Huffman树例,给定代码序列：
0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 10
文本为,A A F A R A D E T
3 3
65
2
1 2
3
117
18
0
0
0
0
0
1
1
1
1
1
RTF
ED
A
7 0 5 0 2 0 4 0 3 0
0 0 0 0 0 0 0 0 0 0
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
7 0 5 0 2 6 4 0 3 6 5 0
0 0 0 0 0 0 0 0 0 0 3 5
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
7 0 5 7 2 6 4 7 3 6 5 0 9 0
0 0 0 0 0 0 0 0 0 0 3 5 4 2
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
data parent
lchild rchild
算法处理,结点说明：
7 8 5 7 2 6 4 7 3 6 5 8 9 0 12 0
0 0 0 0 0 0 0 0 0 0 3 5 4 2 6 1
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
7 8 5 7 2 6 4 7 3 6 5 8 9 9 12 9 21 0
0 0 0 0 0 0 0 0 0 0 3 5 4 2 6 1 7 8
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
HT[1]的编码反序列为,11 则编码为,11
HT[2]的编码反序列为,10 则编码为,01
同理得,HT[3],100 HT[4],00
HT[5],101
家庭作业一,填空
1.假设含有 20个元素的线性表顺序存储,欲在它的第 11和第 12个元素之 间插入一个新元素,共需移动 ______元素 。
2.设数组 A[1..6,1..8 ]的基地址为 1000,每个元素占 2
个存储单 元,若以行序为主序顺序存储,则元素 A[4,5]的存储地址为 _________ 。
3,一棵深度为 5的二叉树最多有 ___________ 个结点 。
4.具有 n个结点的二叉树的二叉链表共有 ________ 个空链域和 ______个非空链域 。
5.具有 n个结点的满二叉树共有 _____________个叶结点和 ___________个非叶结点 。
6.若一棵二叉树中有 10个度为 2的结点,则它有 _______
个叶子 。
二,回答问题：二叉树有哪几种基本形态? 画图说明之 。
家庭作业三,给定 21个字符组成的 文本 (电文 ):
A A A B B B A A A A B B B C C A C C D D E,
试为字符 A,B,C,D,E 设计哈夫曼 （ Huffman） 编码 。
1.画出相应的哈夫曼树；
2.分别列出 A,B,C,D,E 的哈夫曼码
A
F
D
B
G
二叉树
C
E
H
I
J K
四、画图
1.画出数组 A[2][3] 的以行序为主序的顺序存储结构。
2.依次将元素 D,C,A,B,E插入一个初始状态为空的链式栈中,试画出插入完成之后的链式栈。
3.画出 右 面二叉树的 顺序存储结构图，以及 先序线索二叉树、中序线索二叉树、后序线索二叉树 的存储结构图 。
华中科技大学计算机学院 (8)数据结构
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树
6.3.2 建立 (生成 )二叉树
6.3.3 线索二叉树
6.3.4 表达式二叉树表达式二叉树 T = (第一操作数 ) (运算符 ) (第二操作数 )
其中：第一操作数、第二操作数也是表达式二叉树，
分别为表达式二叉树 T的左子树和左子树运算符第一操作数左二叉树第二操作数右二叉树表达式二叉树例 表达式,A + B * C - D /（ E - F）
-
+ /
A * D -
B C E F
● 前序遍历,- + A * B C / D - E F
前缀表示,前缀表达式,波兰式
● 中序遍历,A + B * C - D /( E - F )
中缀表示,中缀表达式
● 后序遍历,A B C * + D E F - / -
后缀表示,后缀表达式，逆波兰式表达式二叉树
6.3.5 中序遍历序列和前 (或后 )序序列确定唯一棵二叉树
B
A
C
D
E
T1
B
A
C
D
E
T2例 1,给定二叉树 T的中序序列,B A C D E G F
前序序列,E A B C D F G
如何求二叉树 T？
由前序序列,A D E B C
和 (或 )后序序列,E D C B A
不能确定唯一棵二叉树
E
B,A,C,D G,F
E
A F
B C G
D
6.3.5 中序遍历序列和前 (或后 )序序列确定唯一棵二叉树例 2,给定二叉树 T的后序序列,B G H E C A J I F D
中序序列,B A C G E H D I J F
如何求二叉树 T？
D
B,A,C
G,E,H I,J,F
6.3.5 中序遍历序列和前 (或后 )序序列确定唯一棵二叉树例 2,给定二叉树 T的后序序列,B G H E C A J I F D
中序序列,B A C G E H D I J F
如何求二叉树 T？
D
B,A,C
G,E,H I,J,F
D
A F
B C I
E
G H
J
二叉树 T
6.3.6 中序遍历 非递归算法
递归算法简明精炼,但效率较低,实际应用中常使用非递归；
某些高级语言不支持递归；
非递归算法思想：
（ 1） 设置一个栈 S存放所经过的根结点 （ 指针 ） 信息；
初始化 S；
（ 2） 第一次访问到根结点并不访问,而是入栈；
（ 3） 中序遍历它的左子树,左子树遍历结束后,第二次遇到根结点,就将根结点 （ 指针 ） 退栈,并且访问根结点；然后中序遍历它的右子树 。
（ 4） 当需要退栈时,如果栈为空则结束 。
A
B C
D E
t
A
A
B C
D E
t
B
A
A
B C
D E
t
D
B
A
A
B C
D E
t=NULL,表示 D的左子树遍历结束根进栈根进栈 根进栈
D
B
A
A
B C
D E
退栈?t,访问 D，
t->rchild?t B
A
A
B C
D E
t=NULL,表示 B的左子树遍历结束退栈?t,访问 B，
t->rchild?t
E
A
A
B C
D E
A
B C
D E tA
根进栈
t=NULL,表示 E的左子树遍历结束
D
D B
t=NULL,表示 D的左子树遍历结束
E
A
A
B C
D E
退栈?t,访问 E，
t->rchild?t
A
A
B C
D E
t=NULL,表示 A的左子树遍历结束退栈?t,访问 A，
t->rchild?t
C
A
B C
D E
A
B C
D E t
根进栈
t=NULL,表示 C的左子树遍历结束
D B E
D B E A
t=NULL,表示 E的左子树遍历结束退栈?t,访问 C，
t->rchild?t
A
B C
D E
t=NULL,并且栈 S
为空，遍历结束
C
A
B C
D E
t=NULL,表示 C的左子树遍历结束 D B E A C
void Midorder(struct BiTNode *t) //t为根指针
{ struct BiTNode *st[maxleng+1];//定义指针栈 st[0..maxleng]
int top=0； //置空栈
do
{ while(t) //根指针 t表示的为非空二叉树
{ if (top==maxleng) exit(OVERFLOW)； //栈已满,退出
st[++top]=t； //根指针进栈
t=t->lchild； //t移向左子树
} //循环结束表示以栈顶元素的指向为
//根结点的二叉树的左子树遍历结束
if (top) //为非空栈
{ t=st[top--]； //弹出根指针
printf("%c",t->data)； //访问根结点
t=t->rchild； //遍历右子树
}
} while(top||t)； //父结点未访问,或右子树未遍历
}
6.3.7 遍历二叉树的 应用例,求二叉树中结点的个数
int preorder(struct BiTNode *root)
//求二叉树中结点的个数
{ int n=0 ;
if (root)
{ n=1； //根结点计数
n+=preorder(root->lchild)； //递归计算左子树
n+=preorder(root->rchild)； //递归计算右子树
}
return n;
}
main()
{ int n； //n为计数器,假定二叉树已生成
n=preorder(root)； //root为指针,执行 preorder(root,&n)
printf("%d",n)； //输出 n
}
例：将二叉数线索化 （ 中序 ） 。
T的中序序列,B,D,C,E,A,F,G F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的中序线索二叉树
NULL
NULL
0 A 0
root
中序线索二叉树链表
1 F 01 B 0
1 G 10 C 0
1 D 1 1 E 1
NULL
NULL
结点结构：
void creat_thread(struct BiTNode *t) //t为根指针
{ struct BiTNode *st[maxleng+1],pre=NULL; //前驱结点指针
int top=0； //置空栈
do
{ while(t) //根指针 t表示的为非空二叉树
{ if (top==maxleng) exit(OVERFLOW)； //栈已满,退出
st[++top]=t； //根指针进栈
t=t->lchild； //t移向左子树
}
0/1 0/1
lchild ltag data rtag rchild
左小孩 左标志 结点值 右标志 右小孩或前趋 或后继
if (top) //为非空栈
{ t=st[top--]； //弹出根指针
printf(“%c”,t->data)； //访问根结点
if (t->lchild!=NULL) t->ltag=0; //左指针为孩子
else {
t->ltag=1;t->lchild=pre; } //左指针为线索
if (pre!=NULL)
if (pre->rchild!=NULL)
pre->rtag=0; //右指针为孩子
else {
pre->rtag=1; //右指针为线索
pre->rchild=t;
}
pre=t; //pre与 t保持前后
t=t->rchild； //遍历右子树
}
} while(top||t)；
}
先序线索二叉树的遍历,
void (struct BiTNode *t) //t为根指针
{ p=t;
while (p)
{
printf(“%6c”,p->data);
if (p->ltag==0) //有左孩子时,p移向左孩子结点
p=p->lchild;
else //p移向右孩子或右线索指向的结点
p=p->rchild;
}
}
中序线索二叉树的遍历,
void (struct BiTNode *t) //t为根指针
{ p=t;
if (p!=NULL) while (p->lchild!=NULL)
p=p->lchild; //查找二叉树的最左结点 (第 1个结点 )
printf(“%6c”,p->data);
while (p->rchild!=NULL) // p有后继结点
{if (p->rtag==1) p=p->rchild; //p无右孩子时为线索
else{p=p->rchild; //p有右孩子时，取右子树最左结点
while (p->ltag!=1) p=p->lchild;}
printf(“%6c”,p->data);
}
}
6.4 树和森林
6.4.1 树的存储结构
1.双亲表示法 /数组表示法 /顺序表示法
A
B C
ED F
树
G
A 0
B 1
C 1
D 3
E 3
F 3
G 4
data parent
1
2
3
4
5
6
7
struct snode
{ char data；
int parent；
}t[maxleng+1}；
t[1..7}
2.孩子表示法 /链接表表示法
(1)固定大小的结点格式,设树 T的度为 n
A
B C
ED F
树 T
G
A ∧
B ∧ ∧ ∧ C
D ∧ ∧ E ∧ ∧ ∧ F ∧ ∧ ∧
G ∧ ∧ ∧
root
T的链接表结点值
...
data child1
childn
2.孩子表示法 /链接表表示法
(2)非固定大小的结点格式
A
B C
ED F
树
G
A 2
B 0 C 3
D 1
root
链接表
E 0 F 0
G 0
结点 值 结点的度 n,..
data degree child1
childn
3.孩子兄弟表示法 /二叉树表示法 /二叉链表
A
B C
ED F
树
J
root
二叉链表结点值
firstchild data nextbrother
G
IH K
左 孩子右兄弟
A ∧
B
∧ F ∧E∧ D
∧ K ∧∧ J∧ I ∧∧ H
C ∧
G ∧
3.孩子兄弟表示法 /二叉树表示法 /二叉链表
A
B C
ED F
树
J
root
二叉链表结点值
firstchild data nextbrother
G
IH K
左 孩子 右兄弟
A ∧
B
∧ F ∧
E
∧ D
∧ K ∧
∧ J
∧ I ∧
∧ H
C ∧G ∧
4.孩子链表表示法 /单链表表示法
A
B C
ED F
树
J
结点 值
data first
G
IH K
表头结点第一个孩子 序号 值孩子结点 /表结点下一个孩子
child next
A
B
C
D ∧
E
F ∧
G
H ∧
I ∧
J ∧
K ∧
6 ∧4
7 ∧
2
5
10
8
1
2
3
4
5
6
7
8
9
10
11
3 ∧
11 ∧
9 ∧
表头结点数组
5.带双亲的孩子链表表示法
A
B C
ED F
树
J
结点 值
data parent first
G
IH K
表头结点第一个孩子 序号 值孩子结点 /表结点下一个孩子
child next
A 0
B 1
C 1
D 3 ∧
E 3
F 3 ∧
G 2
H 7 ∧
I 7 ∧
J 5 ∧
K 5 ∧
6 ∧4
7 ∧
2
5
10
8
1
2
3
4
5
6
7
8
9
10
11
3 ∧
11 ∧
9 ∧
表头结点数组
6.4.2 树与二叉树的转换
1.树 二叉树
A
B C
GF H
L
D
JI M
E
K
A
B C
GF H
树
L
D
JI M
E
K
1.在兄弟之间加连线A
B C
GF H
L
D
JI M
E
K
2.保留根与最左孩之间的连线删除与其它孩子 之间的连线
1.树 二叉树
A
B C
GF H
L
D
JI M
E
K
A
B
K G
E
H
L
D C
I
M
J
F
3.以根为轴心顺时针方向旋转 45度二叉树
2.保留根与最左孩之间的连线删除与其它孩子 之间的连线
2.森林 二叉树
A J
E
CB D
L
G
IH
M
K
F
T1 T2 T3 T4
A J
E
CB D
L
G
IH
M
K
F
A J
E
C
B
D
L
G
I
H
M
K
F
B1 B2 B3 BT4
A J
E
C
B
D
L
G
I
H
M
K
F
B1 B2 B3 BT4
加线 拆线之后旋转后 变为多棵二叉树 连成一棵二叉树
A
JE
C
B
D
L
G
I
H
M
K
F
2.森林 二叉树
A J
E
CB D
L
G
IH
M
K
F
T1 T2 T3 T4
森林 F={T1,T2,T3,T4}
旋转后,变为一棵二叉树
A
F
D
B
G
3,二叉树 树
A
DB G
树 T
二叉树 B
I
C
E
H
E
C
H
F I
J
A
F
D
B
G
I
C
E
H J
A
F
D
B
G
I
C
E
H J
J
例 1
A
F
D
B
G
3,二叉树 森林
A
DB G
二叉树 B
C
E
E
C F
H
I
J K
A
F
D
B
G
C
E
H
I
J K
A
F
D
B
G
C
E
H
I
J K
H
J
I K
T2 T4T3T1
例 2
6.4.3 树和森林的遍历
1.树的遍历
A
B C
ED F
J
G
IH K
前根遍历,A B G H I C D E J K F
后根遍历,H I G B D J K E F C A
2.森林的遍历
D
G
IH L
J
A
CB
K
F
E 前序遍历,A B C D E F G H I J K L
后序遍历,B D C A F E H J K I L G
（ 依次对每一棵树后序遍历）
6.6 哈夫曼（ Huffman)树及其应用
1.路径长度 ----路径上分枝的数目 (连线的数目 )
2.树 T的路径长度 ----从树 T的根到其余每个结点的路径长度之和记作 PL(T)
T1 T2 T3
PL(T1)=1+1+2+2+2=8
PL(T2)=1+2+3+4+5=15
PL(T1)=1+1+2+3+3=10
● 当 n个结点的二叉树为完全二叉树时,PL(T)具有 最小值：
∵ 结点 i的层 =?log2i? + 1
树 T的根到 结点 i的路径长度 = 结点 i的层 -1 =?log2i?
n
∴ PL(T)=?log21?+?log22?+...+?log2n? = ∑?log2i?i=1
● 当 n个结点的二叉树为单枝树时,PL(T)具有最大值：
PL(T)=0+1+2+...+(n-1) = n(n-1)/2
3,树 T的带权路径长度 ----每个叶子的权与根到该叶子的路径长度的乘积之和，记作 WPL(T)
n
WPL(T) = ∑ wklk
i=1
其中,n --- 树 T的 叶子数目 wk--- 叶子 i的权
lk--- 树 T的根到叶子 i的路径长度
T1
4
8
5
9
7
6 WPL(T)=6*1+3*2+4*3+9*3=51
3
4.哈夫曼树 /最佳树 /最优树 ----
在具有 n个相同叶子的各二叉树中,WPL(T)最小的二叉树。
T1
5
3
14
6
28
14
● PL(T1)=1+1+2+2+2+2+3+3=16
● WPL(T1)=5*3+6*3+3*2+4*2+10*2=67
● PL(T2)=1+1+2+2+3+3+4+4=20
● WPL(T2)=10*1+6*2+5*3+4*4+3*4=65
● PL(T3)=1+1+2+2++2+2+3+3=16
● WPL(T3)=5*3+6*3+3*2+4*2+10*2=63
4 1011
T2 3
7
10
4
28
18
6 12
5 3
6
11
4
28
17
7 105
T3
5.哈夫曼算法例 给定权集合 {4,5,3,6,10}，构造 哈夫曼树
1.按权值大小排序,3,4,5,6,10
2.生成森林：
53 64 10
T1 T2 T3 T4 T5
3.合并两棵权最小的二叉树,并排序,直到为一棵二叉树：
5
3
6
4
107
5 6
11
3 4
107
3 4
107
17
5 6
11
3 4
107
17
5 6
11
28
6.最小冗余码 /哈夫曼码
● ASCII码 /定长码
ab12,01100001 01100010 00110001 00110010
97 98 49 50
● 哈夫曼码 /不定长码能按字符的使用频度,使文本代码的总长度具有最小值。
例,给定有 18个字符组成的文本：
A A D A T A R A E F R T A A F T E R
求各字符的 哈夫曼码。
(1) 统计：
字 符 A D E F T R
频 度 7 1 2 2 3 3
(2) 构造 Huffman树：
21 32 3 7
(2) 构造 Huffman树：
21 32 3 7
3 2
1
3
2
3 73
合并 1和 2 排序排序
5
2
1
3
2
3 73
合并 2和 3
5
2
1
3
2
3 7
3
(2) 构造 Huffman树：
排序
5
2
1
3
2
3 7
3
6
合并 3和 3
3 3
65
2
1 2
3
7
排序
3 3
65
2
1 2
3
7
11
合并 5和 6
3 3
65
2
1 2
3
117
(2) 构造 Huffman树,(3) 在左分枝标 0,右分枝标 1,
合并 7和 11
3 3
65
2
1 2
3
117
18
Huffman树字 符 A D E F T R
频 度 7 1 2 2 3 3
编 码 0 1010 1011 100 110 111
(4) 确定 Huffman编码：
特点,任一编码不是其它编码的 前缀
3 3
65
2
1 2
3
117
18
0
0
0
0
0
1
1
1
1
1
RTF
ED
A
如何译码？
Huffman树例,给定代码序列：
0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 10
文本为,A A F A R A D E T
3 3
65
2
1 2
3
117
18
0
0
0
0
0
1
1
1
1
1
RTF
ED
A
7 0 5 0 2 0 4 0 3 0
0 0 0 0 0 0 0 0 0 0
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
7 0 5 0 2 6 4 0 3 6 5 0
0 0 0 0 0 0 0 0 0 0 3 5
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
7 0 5 7 2 6 4 7 3 6 5 0 9 0
0 0 0 0 0 0 0 0 0 0 3 5 4 2
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
data parent
lchild rchild
算法处理,结点说明：
7 8 5 7 2 6 4 7 3 6 5 8 9 0 12 0
0 0 0 0 0 0 0 0 0 0 3 5 4 2 6 1
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
7 8 5 7 2 6 4 7 3 6 5 8 9 9 12 9 21 0
0 0 0 0 0 0 0 0 0 0 3 5 4 2 6 1 7 8
HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9]
HT[1]的编码反序列为,11 则编码为,11
HT[2]的编码反序列为,10 则编码为,01
同理得,HT[3],100 HT[4],00
HT[5],101
家庭作业一,填空
1.假设含有 20个元素的线性表顺序存储,欲在它的第 11和第 12个元素之 间插入一个新元素,共需移动 ______元素 。
2.设数组 A[1..6,1..8 ]的基地址为 1000,每个元素占 2
个存储单 元,若以行序为主序顺序存储,则元素 A[4,5]的存储地址为 _________ 。
3,一棵深度为 5的二叉树最多有 ___________ 个结点 。
4.具有 n个结点的二叉树的二叉链表共有 ________ 个空链域和 ______个非空链域 。
5.具有 n个结点的满二叉树共有 _____________个叶结点和 ___________个非叶结点 。
6.若一棵二叉树中有 10个度为 2的结点,则它有 _______
个叶子 。
二,回答问题：二叉树有哪几种基本形态? 画图说明之 。
家庭作业三,给定 21个字符组成的 文本 (电文 ):
A A A B B B A A A A B B B C C A C C D D E,
试为字符 A,B,C,D,E 设计哈夫曼 （ Huffman） 编码 。
1.画出相应的哈夫曼树；
2.分别列出 A,B,C,D,E 的哈夫曼码
A
F
D
B
G
二叉树
C
E
H
I
J K
四、画图
1.画出数组 A[2][3] 的以行序为主序的顺序存储结构。
2.依次将元素 D,C,A,B,E插入一个初始状态为空的链式栈中,试画出插入完成之后的链式栈。
3.画出 右 面二叉树的 顺序存储结构图，以及 先序线索二叉树、中序线索二叉树、后序线索二叉树 的存储结构图 。
