6.4 遍历二叉树和线索二叉树一、遍历二叉树遍历二叉树是指 按一定的规律 对二叉树的每个结点,访问 且仅访问一次的处理过程。
访问 是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。
一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。
遍历的次序,若设二叉树根为 D，左子树为 L，右子树为 R，并限定先左后右，则有以下三种遍历次序：
LDR 中序遍历 ； LRD 后序遍历 ； DLR 先序遍历
6.4 遍历二叉树和线索二叉树
1.前序遍历二叉树算法思想,
若二叉树非空,则：
1） 访问根结点
2） 前序遍历左子树
3） 前序遍历右子树算法描述,
void PreOrderTraverse(BiTree T)
{ /*先序遍历二叉树算法,*/
/*其中 visit()是对数据元素 */
/*的具体应用访问函数 */
if(T) /*如果 T非空 */
{
visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
6.4 遍历二叉树和线索二叉树假定 TElemType是 char型，则可用以下算法建立一个二叉树
BiTree CreateBiTree( )
{ BiTree t; char ch;
scanf(“%c”,&ch); //依次输入前序序列当左 (右 )子树为空时输入空格
if(ch!=’’)
{t=(BiTree)malloc(sizeof(BiTnode));
t->data=ch;
t->lchild= CreateBiTree( );
t->rchild= CreateBiTree( );}
else t=NULL;
return t; }
按前序序列建二叉树
6.4 遍历二叉树和线索二叉树
2.后序遍历二叉树算法思想,
若二叉树非空,则：
1） 后序遍历左子树
2） 后序遍历右子树
3） 访问根结点算法描述,
void PostOrderTraverse(BiTree T)
{ /*后序遍历二叉树算法,*/
/*其中 visit()是对数据元素 */
/*的具体应用访问函数 */
if(T) /*如果 T非空 */
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
visit(T->data);
}
}
6.4 遍历二叉树和线索二叉树
3.中序遍历二叉树算法思想,
若二叉树非空,则：
1） 中序遍历左子树
2) 访问根结点
3） 中序遍历右子树算法描述,
void InOrderTraverse(BiTree T)
{ /*中序遍历二叉树算法,*/
/*其中 visit()是对数据元素 */
/*的具体应用访问函数 */
if(T) /*如果 T非空 */
{
InOrderTraverse(T->lchild);
visit(T->data);
InOrderTraverse(T->rchild);
}
}
6.4 遍历二叉树和线索二叉树例：表达式 a+b × (c-d)-e/f
a
c d
e f
／
－b
×
＋
－
+
遍历结果,
中序,a+b × c － d － e /f
后序,abcd － × +ef / －
先序,－ +a × b－ cd /ef
6.4 遍历二叉树和线索二叉树三种遍历过程示意图例
a
c
b
×
－
a b
* c
-
ba
*
-
c
a b
* c
-
－
×
a b
c
虚线表示执行过程,向下表示更深层的递归调用 ;
向上表示递归调用返回 ;
沿虚线记下各类符号,便得到遍历的结果,
6.4 遍历二叉树和 线索二叉树
void InOrderTraverse(BiTree T)
{中序遍历非递归算法,s为存储二叉树结点指针栈 }
initstack(s)； push(s,T)；
while (!stackempty(s))
{ while (stacktop(s))
push(s,stacktop(s)↑.lchild) ；
p:=pop(s)；
if(!stackempty(s))
{visit(stacktop(s)↑.data) ；
p:=pop(s)；
push(s,p↑.rchild)}}
}
根结点先进栈，
左结点紧跟根后面进栈,右结点在根出栈后入栈
每个结点都要进一次和出一次栈，
并且总是访问栈顶元素,因此,算法正确,时间复杂度为 O(n),空间复杂度为 O(n) 。
6.4 遍历二叉树和线索二叉树二、线索二叉树
⒈ 问题的提出,通过遍历二叉树可得到结点的一个线性序列，在线性序列中，就存在结点和前驱和后继，但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱和后继只有在遍历过程中才能得到，那么，能否通过结点的两个链域查找出任一结点的前驱和后继?
6.4 遍历二叉树和线索二叉树
2,分析,
n个结点有 n-1个前驱和 n-1个后继；
一共有 2n个链域，其中,n+1个空链域，
n-1个指针域；
因此,必须用空链域来存放结点的前驱和后继。线索二叉树就是利用 n+1个空链域来存放结点的前驱和后继结点的信息。
6.4 遍历二叉树和 线索二叉树
3,线索二叉树,
⑴ 结点结构在二叉链表中增加 ltag 和 rtag 两个标志域
lchild ltag data rtag rchild
若结点有左子树，则左链域 lchild指示其左孩子
（ ltag= 0）；否则，令左链域指示其前驱（ ltag=1）；
若结点有右子树，则右链域 rchild指示其右孩子
（ rtag= 0）；否则，令右链域指示其后继（ rtag= 1）；
6.4 遍历二叉树和 线索二叉树二叉树的二叉线索链表存储表示
typedef enum {LINK,THREAD} PointerTag;
/* LINK值为 0,表示指针 ;THREAD值为 0,表示线索 */
typedef struct BiThrNode {
TelemType data;
struct BiThrNode *lchild,*rchild;
PointerTag ltag,rtag;
} BiThrNode,*BiThrTree;
6.4 遍历二叉树和 线索二叉树
称这种结点结构为 线索链表 ；
其中指示前驱和后继的链域称为 线索 ；
加上线索的二叉树称为 线索二叉树 ；
对二叉树以 某种次序 遍历使其变为线索二叉树的过程称为 线索化 。
按中序遍历得到的线索二叉树称为 中序线索二叉树 ；按先序遍历得到的线索二叉树称为 先序线索二叉树 ；按后序遍历得到的线索二叉树称为 后序线索二叉树 ；
6.4 遍历二叉树和 线索二叉树
（ 2）整体结构
增设一个头结点，令其 lchild指向二叉树的根结点,ltag=0,rtag=1；
并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；
最后用头指针指示该头结点。
a
c
b
×
－
0 1
0 － 0
1 c 10 × 0
1 b 11 a 1
6.4 遍历二叉树和 线索二叉树
4,遍历线索二叉树,
有了线索二叉树，就容易遍历二叉树了．
只要
（１）先找要遍历的第一个结点；
（２）然后依次找结点的后继；
（３）重复（２）直到其后继为头结点．
所有问题归为如何在线索二叉树中找结点的后继？
6.4 遍历二叉树和 线索二叉树
1）遍历中序线索二叉树
（ 1）中序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，若 rtag=1，则 rchild
指向该结点的后继；若 rtag=0，则 rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点 s
（ ltag=1）,则 s就是 p的后继，即后继是中序遍历右子树时，访问的第一个结点；
6.4 遍历二叉树和 线索二叉树中序线索二叉树中，找结点的后继 算法
BiThrTree in_next(p,thrt)
BiThrTree p,thrt;
{ /*在以 thrt为头指针的中序线索二叉树上,*/
/*查找指针 p所指结点的后继 */
s=p->rchild；
if (p->rtag==0)
while (s->ltag=0)
s= s->lchild；
return s;
}//in_next
p
1
s
p
0
1
0
s
6.4 遍历二叉树和 线索二叉树
（ 2）遍历中序线索二叉树算法
void thrt_inorder(BiThrTree thrt)
{//遍历以 thrt为头指针的中序线索二叉树
p=thrt->lchild；
while (p->lchild<>thrt) p= p->lchild;
//定位要遍历的第一个结点,
while (p<>thrt) { visit(p->data)；
p=in_next(p,thrt);}
}//thrt_inorder
p-> ltag==0
6.4 遍历二叉树和 线索二叉树
2）遍历后序线索二叉树
（ 1）后序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，
若 p为二叉树的根，则无后继 ;
若 p是双亲的右孩子、或是独生左孩子，则后继为双亲；
若 p是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历时，访问的第一个结点 (叶结点 )；
s
p
s
p
s
p
s
6.4 遍历二叉树和 线索二叉树后序线索二叉树中，找结点的后继 算法
BiThrTree post_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的后序线索二叉树上,
//查找指针 p所指结点的后继
s=parent（ thrt,p）； //在 thrt上查找 p的双亲
if (s==thrt) return thrt；
if (s->rchild==p)||(s->rtag==1)return s；
while (s->rtag==0)
{ s= s->rchild；
while (s->ltag==0) s= s->lchild； }
return s;
}//post_next
6.4 遍历二叉树和 线索二叉树
（ 2）遍历后序线索二叉树算法
void thrt_postorder(BiThrTree thrt)
{//遍历以 thrt为头指针的后序线索二叉树
if (thrt!=thrt->lchild)
{ p=thrt->lchild； search=1；
while (search)
{ while (p->ltag==0) p= p->lchild；
if (p->rtag==0) p= p->rchild;
else search=0； }
while (p!=thrt) { visit(p↑.data) ；
p=post_next(p,thrt)}}
}//thrt_postorder
6.4 遍历二叉树和 线索二叉树
3）遍历先序线索二叉树
（ 1）先序线索二叉树中，找结点的后继算法算法思想,对任意结点 p:
若 p有左孩子，则后继为左孩子 ;
若 p无左孩子,有右孩子，则后继为右孩子；
若 p无左孩子,也无右孩子，则后继为右线索；
6.4 遍历二叉树和 线索二叉树先序线索二叉树中，找结点的后继 算法
BiThrTree pre_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的先序线索二叉树上,
//查找指针 p所指结点的后继
if (p->ltag==0) return(p->lchild)；
else return p->rchild;
}//pre_next
6.4 遍历二叉树和 线索二叉树
（ 2）遍历先序线索二叉树算法
void thrt_preorder(BiThrTree thrt)；
{ //遍历以 thrt为头指针的先序线索二叉树
p=thrt->lchild；
while (p!=thrt)
{ visit(p->data)；
p=pre_next(p,thrt)}
}//thrt_preorder
6.５ 树和森林一．树的存储结构
１．双亲表示法用一组地址连续的存储单元来存放树的结点，
每个结点有两个域：
data域 -----存放结点的信息；
parent域 -----存放该结点双亲结点的位置,
４
３２
６５
１ １２
３
４
５
６
０
１
１
２
２
２
data parent
特点：求结点的双亲很容易，
但求结点的孩子需要遍历整个向量。
6.５ 树和森林
２．孩子表示法每个结点的孩子用单链表存储，称为孩子链表。
n个结点可以有 n个孩子链表（叶结点的孩子链表为空表）。
n个孩子链表的头指针用一个向量表示。
如图,头指针向量 孩子链表
１
２
３
４
５
６
６５４
３２
∧
∧
∧
∧
∧
∧
特点：与１相反，求孩子易，求双亲难。
6.５ 树和森林
３．双亲孩子表示法．
在孩子表示法的头指针向量中，增加一项，用来表示该结点的双亲。
如图,头指针向量 孩子链表
０
１
１
２
２
２
１
２
３
４
５
６
６５４
３２
∧
∧
∧
∧
∧
∧
6.５ 树和森林
４．孩子兄弟表示法．
用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。
如图：
∧
∧
∧ ∧
１
２ ３
４ ５ ６∧ ∧∧
双亲只管长子长子连接兄弟
6.５ 树和森林二、森林、树与二叉树的对应关系
１、树与二叉树的对应关系树与二叉树均可用二叉链表作为存储结构，
因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。
Ｄ
Ｂ
Ａ
ＥＣ
∧ ∧Ｂ Ｃ ∧Ｅ
∧Ａ
∧Ｄ∧
Ｄ Ｅ
Ｃ
ｂ
Ａ
Ｂ
∧Ａ
Ｃ
∧Ｄ ∧Ｅ
∧
∧ ∧
（ ２）顺时针转４５度
（ １）孩子兄弟法树解释,B是 A的第一个孩子,C,E是
B的兄弟,D是 C的第一个孩子 。
解释：Ｂ是Ａ的左孩子，
Ｃ是Ｂ的右孩子。
6.５ 树和森林
树变为二叉树的方法
（１）在兄弟之间加一连线；
（２）对每一个结点，只保留它与第一个孩子的连线，去掉与其他孩子的连线；
（３）以树根为轴心，将整棵树顺时针旋转 45度。
特点,根无右子树
6.５ 树和森林
2.森林与二叉树的对应关系
（ 1）森林转换为二叉树的方法
将森林 F={T1,T2,.,Tm}的各棵树分别转成二叉树
BT1,BT2,.,BTm
将 BTi+1作为 BTi根结点的右子树（ i=1,2,...,m-1）,
得到一棵 BT。
6.５ 树和森林如图,F={T1,T2,T3}
D
B
C
A
BT1
F
E
BT2
B C F
E
J
HA
D
I
GT
1 T3T2
BT3
H
J
I
G
J
I
F
EB
D
A
H
G
C
6.５ 树和森林
(2)二叉树转换森林的方法
将当前根结点和其左子树作为森林的一棵树,并将其右子树作为森林的其他子树；
重复上面直到某结点的右子树为空。
J
I
H
G
F
EB
C
D
A T1
B
C
D
A
F
E
T2 T3
J
I
H
G
6.6 哈夫曼树及其应用哈夫曼树（ Huffman）树是一类带权路径长度最短的树一,Huffman树（最优二叉树）
1,概念
两结点间的路径：从一结点到另一结点所经过的结点序列
路径长度：路径上的分支树
树的路径长度：从根到每一结点的路径长度之和
2
76
3
4
1
5
例
⑴ -⑵ -⑸ 为结点 1到 5之间的路径，其路径长度为 2，
树的路径长度 =l12 +l13+l14 +l15+ l16 +l17
=1+1+2+2+2+2=10
6.6 哈夫曼树及其应用完全二叉树是路径长度最短的二叉树。
考虑带权时：设树中有 m个叶结点，每个叶结点带一个权值 wｉ 且根到叶结点 i的路径长度为 Li (ｉ =1,2，．,m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。
Ｍ
即：ＷＰＬ＝ ∑ Ｗ ｋ Ｌ ｋ
Ｋ＝１
6.6 哈夫曼树及其应用例：
使 WPL最小的二叉树成为最优二叉树 (Huffman 树 )
完全二叉树
dca b
7 5 2 4
c
d
ba
2
4
7 5
WPLa=2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2
=36 =46
6.6 哈夫曼树及其应用
Huffman 树
WPLc=7*1+5*2+2*3+4*3
=35
b
dc
a
7
5
2 4
（ 1）完全二叉树并不一定是 Huffman树；
（ 2） HT是权值越大的越靠近根结点；
（ 3） HT不唯一，但
WPL一定相等。
6.6 哈夫曼树及其应用
2．构造 Huffman树算法
(1) 以权值分别为 W1,W2．．．Ｗ ｎ 的ｎ各结点，构成 n棵二叉树 T1,T2,．．,Tn并组成森林 F={T1,T2,．．,Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点；
(2) 在 F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值 =左右孩子权值之和，
叶结点的权值 = Wi）
(3) 从 F中删除这两棵二叉树，同时将新二叉树加入到 F中 ;
(4) 重复 (2),(3)直到 F中只含一棵二叉树为止，这棵二叉树就是 Huffman 树。
由此可知，有 n个叶子结点的哈夫曼树中结点总数为 2n-1 。
6.6 哈夫曼树及其应用
a b c d
7 5 2 4例,F={ }
a bF={ }
c d
7 5 6
2 4
F={ }a
b
c d
11
6
4
2
5
F={ }a
b
c d
11
6
425
7
18
7
6.6 哈夫曼树及其应用
HT不唯一性,可能出现在,
（ 1）构造新树时，左、右孩子未作规定。
（ 2）当有多个权值相同的树，可作有候选树时，选择谁未作规定。
二、哈夫曼编码（ Huffman 树的应用）
1、问题的提出通讯中常需要将文字转换成二进制字符串电文进行传送。文字 电文，称为 编码 。
反之，收到电文后要将电文转换成原来的文字，
电文 文字，称为 译码 。
6.6 哈夫曼树及其应用例如：需将文字,ABACCDA”转换成电文。文字中 有四种字符，用 2位二进制便可分辨。
A B C D
00 01 10 11
编码方案 1：
则上述文字的电文为,00010010101100 共 14位。
译码时，只需每 2位一译即可。
特点：等长等频率编码，译码容易，但电文不一定最短,
6.6 哈夫曼树及其应用
A B C D
0 00 1 01
编码方案 2：
采用不等长编码，让出现次数多的字符用短码。
则上述文字的电文为,000011010 共 9位。
但无法译码，它即可译为 BBCCACA，也可译为
AAAACCDA等。
6.6 哈夫曼树及其应用
A B C D
0 110 10 111
编码方案 3：
采用不等长编码，让出现次数多的字符用短码，
且任一编码不能是另一编码的前缀,即前缀编码。
则上述文字的电文为,0110010101110 共 13位。
6.6 哈夫曼树及其应用设有 n种字符，每种字符出现的次数为 Wi,
其编码长度为 Li (i=1,2,．．,n)，
则整个电文总长度为 ∑ Wi Li,
要得到最短的电文，即使得 ∑ Wi Li最小。
也就是以字符出现的次数为权值，构造一棵 Huffman树，
并规定左分支编码位 0，右分支编码为 1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。
用构造 Huffman树编出来的码，称为 Huffman编码。
6.6 哈夫曼树及其应用对上例有,
1
A
3 C
B D
1
1
2 0
0
0
1 1
习题
A
B C
GF H
D E
I KJ
ML N
PO
1、对于 3个结点 A,B,C可组成多少种不同的二叉树？请画出。
2、写出图中所示的树的叶子结点，非终端结点的度和树深。
习题
3、写出图中所示的二叉树的先序、中序和后序的遍历结果并画出相应的线索树的逻辑图。
4、有一组数值 14,21,32,15,28，画出哈夫曼树的生成过程。
A
B C
D E
I
GF
JH
访问 是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。
一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。
遍历的次序,若设二叉树根为 D，左子树为 L，右子树为 R，并限定先左后右，则有以下三种遍历次序：
LDR 中序遍历 ； LRD 后序遍历 ； DLR 先序遍历
6.4 遍历二叉树和线索二叉树
1.前序遍历二叉树算法思想,
若二叉树非空,则：
1） 访问根结点
2） 前序遍历左子树
3） 前序遍历右子树算法描述,
void PreOrderTraverse(BiTree T)
{ /*先序遍历二叉树算法,*/
/*其中 visit()是对数据元素 */
/*的具体应用访问函数 */
if(T) /*如果 T非空 */
{
visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
6.4 遍历二叉树和线索二叉树假定 TElemType是 char型，则可用以下算法建立一个二叉树
BiTree CreateBiTree( )
{ BiTree t; char ch;
scanf(“%c”,&ch); //依次输入前序序列当左 (右 )子树为空时输入空格
if(ch!=’’)
{t=(BiTree)malloc(sizeof(BiTnode));
t->data=ch;
t->lchild= CreateBiTree( );
t->rchild= CreateBiTree( );}
else t=NULL;
return t; }
按前序序列建二叉树
6.4 遍历二叉树和线索二叉树
2.后序遍历二叉树算法思想,
若二叉树非空,则：
1） 后序遍历左子树
2） 后序遍历右子树
3） 访问根结点算法描述,
void PostOrderTraverse(BiTree T)
{ /*后序遍历二叉树算法,*/
/*其中 visit()是对数据元素 */
/*的具体应用访问函数 */
if(T) /*如果 T非空 */
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
visit(T->data);
}
}
6.4 遍历二叉树和线索二叉树
3.中序遍历二叉树算法思想,
若二叉树非空,则：
1） 中序遍历左子树
2) 访问根结点
3） 中序遍历右子树算法描述,
void InOrderTraverse(BiTree T)
{ /*中序遍历二叉树算法,*/
/*其中 visit()是对数据元素 */
/*的具体应用访问函数 */
if(T) /*如果 T非空 */
{
InOrderTraverse(T->lchild);
visit(T->data);
InOrderTraverse(T->rchild);
}
}
6.4 遍历二叉树和线索二叉树例：表达式 a+b × (c-d)-e/f
a
c d
e f
／
－b
×
＋
－
+
遍历结果,
中序,a+b × c － d － e /f
后序,abcd － × +ef / －
先序,－ +a × b－ cd /ef
6.4 遍历二叉树和线索二叉树三种遍历过程示意图例
a
c
b
×
－
a b
* c
-
ba
*
-
c
a b
* c
-
－
×
a b
c
虚线表示执行过程,向下表示更深层的递归调用 ;
向上表示递归调用返回 ;
沿虚线记下各类符号,便得到遍历的结果,
6.4 遍历二叉树和 线索二叉树
void InOrderTraverse(BiTree T)
{中序遍历非递归算法,s为存储二叉树结点指针栈 }
initstack(s)； push(s,T)；
while (!stackempty(s))
{ while (stacktop(s))
push(s,stacktop(s)↑.lchild) ；
p:=pop(s)；
if(!stackempty(s))
{visit(stacktop(s)↑.data) ；
p:=pop(s)；
push(s,p↑.rchild)}}
}
根结点先进栈，
左结点紧跟根后面进栈,右结点在根出栈后入栈
每个结点都要进一次和出一次栈，
并且总是访问栈顶元素,因此,算法正确,时间复杂度为 O(n),空间复杂度为 O(n) 。
6.4 遍历二叉树和线索二叉树二、线索二叉树
⒈ 问题的提出,通过遍历二叉树可得到结点的一个线性序列，在线性序列中，就存在结点和前驱和后继，但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱和后继只有在遍历过程中才能得到，那么，能否通过结点的两个链域查找出任一结点的前驱和后继?
6.4 遍历二叉树和线索二叉树
2,分析,
n个结点有 n-1个前驱和 n-1个后继；
一共有 2n个链域，其中,n+1个空链域，
n-1个指针域；
因此,必须用空链域来存放结点的前驱和后继。线索二叉树就是利用 n+1个空链域来存放结点的前驱和后继结点的信息。
6.4 遍历二叉树和 线索二叉树
3,线索二叉树,
⑴ 结点结构在二叉链表中增加 ltag 和 rtag 两个标志域
lchild ltag data rtag rchild
若结点有左子树，则左链域 lchild指示其左孩子
（ ltag= 0）；否则，令左链域指示其前驱（ ltag=1）；
若结点有右子树，则右链域 rchild指示其右孩子
（ rtag= 0）；否则，令右链域指示其后继（ rtag= 1）；
6.4 遍历二叉树和 线索二叉树二叉树的二叉线索链表存储表示
typedef enum {LINK,THREAD} PointerTag;
/* LINK值为 0,表示指针 ;THREAD值为 0,表示线索 */
typedef struct BiThrNode {
TelemType data;
struct BiThrNode *lchild,*rchild;
PointerTag ltag,rtag;
} BiThrNode,*BiThrTree;
6.4 遍历二叉树和 线索二叉树
称这种结点结构为 线索链表 ；
其中指示前驱和后继的链域称为 线索 ；
加上线索的二叉树称为 线索二叉树 ；
对二叉树以 某种次序 遍历使其变为线索二叉树的过程称为 线索化 。
按中序遍历得到的线索二叉树称为 中序线索二叉树 ；按先序遍历得到的线索二叉树称为 先序线索二叉树 ；按后序遍历得到的线索二叉树称为 后序线索二叉树 ；
6.4 遍历二叉树和 线索二叉树
（ 2）整体结构
增设一个头结点，令其 lchild指向二叉树的根结点,ltag=0,rtag=1；
并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；
最后用头指针指示该头结点。
a
c
b
×
－
0 1
0 － 0
1 c 10 × 0
1 b 11 a 1
6.4 遍历二叉树和 线索二叉树
4,遍历线索二叉树,
有了线索二叉树，就容易遍历二叉树了．
只要
（１）先找要遍历的第一个结点；
（２）然后依次找结点的后继；
（３）重复（２）直到其后继为头结点．
所有问题归为如何在线索二叉树中找结点的后继？
6.4 遍历二叉树和 线索二叉树
1）遍历中序线索二叉树
（ 1）中序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，若 rtag=1，则 rchild
指向该结点的后继；若 rtag=0，则 rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点 s
（ ltag=1）,则 s就是 p的后继，即后继是中序遍历右子树时，访问的第一个结点；
6.4 遍历二叉树和 线索二叉树中序线索二叉树中，找结点的后继 算法
BiThrTree in_next(p,thrt)
BiThrTree p,thrt;
{ /*在以 thrt为头指针的中序线索二叉树上,*/
/*查找指针 p所指结点的后继 */
s=p->rchild；
if (p->rtag==0)
while (s->ltag=0)
s= s->lchild；
return s;
}//in_next
p
1
s
p
0
1
0
s
6.4 遍历二叉树和 线索二叉树
（ 2）遍历中序线索二叉树算法
void thrt_inorder(BiThrTree thrt)
{//遍历以 thrt为头指针的中序线索二叉树
p=thrt->lchild；
while (p->lchild<>thrt) p= p->lchild;
//定位要遍历的第一个结点,
while (p<>thrt) { visit(p->data)；
p=in_next(p,thrt);}
}//thrt_inorder
p-> ltag==0
6.4 遍历二叉树和 线索二叉树
2）遍历后序线索二叉树
（ 1）后序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，
若 p为二叉树的根，则无后继 ;
若 p是双亲的右孩子、或是独生左孩子，则后继为双亲；
若 p是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历时，访问的第一个结点 (叶结点 )；
s
p
s
p
s
p
s
6.4 遍历二叉树和 线索二叉树后序线索二叉树中，找结点的后继 算法
BiThrTree post_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的后序线索二叉树上,
//查找指针 p所指结点的后继
s=parent（ thrt,p）； //在 thrt上查找 p的双亲
if (s==thrt) return thrt；
if (s->rchild==p)||(s->rtag==1)return s；
while (s->rtag==0)
{ s= s->rchild；
while (s->ltag==0) s= s->lchild； }
return s;
}//post_next
6.4 遍历二叉树和 线索二叉树
（ 2）遍历后序线索二叉树算法
void thrt_postorder(BiThrTree thrt)
{//遍历以 thrt为头指针的后序线索二叉树
if (thrt!=thrt->lchild)
{ p=thrt->lchild； search=1；
while (search)
{ while (p->ltag==0) p= p->lchild；
if (p->rtag==0) p= p->rchild;
else search=0； }
while (p!=thrt) { visit(p↑.data) ；
p=post_next(p,thrt)}}
}//thrt_postorder
6.4 遍历二叉树和 线索二叉树
3）遍历先序线索二叉树
（ 1）先序线索二叉树中，找结点的后继算法算法思想,对任意结点 p:
若 p有左孩子，则后继为左孩子 ;
若 p无左孩子,有右孩子，则后继为右孩子；
若 p无左孩子,也无右孩子，则后继为右线索；
6.4 遍历二叉树和 线索二叉树先序线索二叉树中，找结点的后继 算法
BiThrTree pre_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的先序线索二叉树上,
//查找指针 p所指结点的后继
if (p->ltag==0) return(p->lchild)；
else return p->rchild;
}//pre_next
6.4 遍历二叉树和 线索二叉树
（ 2）遍历先序线索二叉树算法
void thrt_preorder(BiThrTree thrt)；
{ //遍历以 thrt为头指针的先序线索二叉树
p=thrt->lchild；
while (p!=thrt)
{ visit(p->data)；
p=pre_next(p,thrt)}
}//thrt_preorder
6.５ 树和森林一．树的存储结构
１．双亲表示法用一组地址连续的存储单元来存放树的结点，
每个结点有两个域：
data域 -----存放结点的信息；
parent域 -----存放该结点双亲结点的位置,
４
３２
６５
１ １２
３
４
５
６
０
１
１
２
２
２
data parent
特点：求结点的双亲很容易，
但求结点的孩子需要遍历整个向量。
6.５ 树和森林
２．孩子表示法每个结点的孩子用单链表存储，称为孩子链表。
n个结点可以有 n个孩子链表（叶结点的孩子链表为空表）。
n个孩子链表的头指针用一个向量表示。
如图,头指针向量 孩子链表
１
２
３
４
５
６
６５４
３２
∧
∧
∧
∧
∧
∧
特点：与１相反，求孩子易，求双亲难。
6.５ 树和森林
３．双亲孩子表示法．
在孩子表示法的头指针向量中，增加一项，用来表示该结点的双亲。
如图,头指针向量 孩子链表
０
１
１
２
２
２
１
２
３
４
５
６
６５４
３２
∧
∧
∧
∧
∧
∧
6.５ 树和森林
４．孩子兄弟表示法．
用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。
如图：
∧
∧
∧ ∧
１
２ ３
４ ５ ６∧ ∧∧
双亲只管长子长子连接兄弟
6.５ 树和森林二、森林、树与二叉树的对应关系
１、树与二叉树的对应关系树与二叉树均可用二叉链表作为存储结构，
因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。
Ｄ
Ｂ
Ａ
ＥＣ
∧ ∧Ｂ Ｃ ∧Ｅ
∧Ａ
∧Ｄ∧
Ｄ Ｅ
Ｃ
ｂ
Ａ
Ｂ
∧Ａ
Ｃ
∧Ｄ ∧Ｅ
∧
∧ ∧
（ ２）顺时针转４５度
（ １）孩子兄弟法树解释,B是 A的第一个孩子,C,E是
B的兄弟,D是 C的第一个孩子 。
解释：Ｂ是Ａ的左孩子，
Ｃ是Ｂ的右孩子。
6.５ 树和森林
树变为二叉树的方法
（１）在兄弟之间加一连线；
（２）对每一个结点，只保留它与第一个孩子的连线，去掉与其他孩子的连线；
（３）以树根为轴心，将整棵树顺时针旋转 45度。
特点,根无右子树
6.５ 树和森林
2.森林与二叉树的对应关系
（ 1）森林转换为二叉树的方法
将森林 F={T1,T2,.,Tm}的各棵树分别转成二叉树
BT1,BT2,.,BTm
将 BTi+1作为 BTi根结点的右子树（ i=1,2,...,m-1）,
得到一棵 BT。
6.５ 树和森林如图,F={T1,T2,T3}
D
B
C
A
BT1
F
E
BT2
B C F
E
J
HA
D
I
GT
1 T3T2
BT3
H
J
I
G
J
I
F
EB
D
A
H
G
C
6.５ 树和森林
(2)二叉树转换森林的方法
将当前根结点和其左子树作为森林的一棵树,并将其右子树作为森林的其他子树；
重复上面直到某结点的右子树为空。
J
I
H
G
F
EB
C
D
A T1
B
C
D
A
F
E
T2 T3
J
I
H
G
6.6 哈夫曼树及其应用哈夫曼树（ Huffman）树是一类带权路径长度最短的树一,Huffman树（最优二叉树）
1,概念
两结点间的路径：从一结点到另一结点所经过的结点序列
路径长度：路径上的分支树
树的路径长度：从根到每一结点的路径长度之和
2
76
3
4
1
5
例
⑴ -⑵ -⑸ 为结点 1到 5之间的路径，其路径长度为 2，
树的路径长度 =l12 +l13+l14 +l15+ l16 +l17
=1+1+2+2+2+2=10
6.6 哈夫曼树及其应用完全二叉树是路径长度最短的二叉树。
考虑带权时：设树中有 m个叶结点，每个叶结点带一个权值 wｉ 且根到叶结点 i的路径长度为 Li (ｉ =1,2，．,m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。
Ｍ
即：ＷＰＬ＝ ∑ Ｗ ｋ Ｌ ｋ
Ｋ＝１
6.6 哈夫曼树及其应用例：
使 WPL最小的二叉树成为最优二叉树 (Huffman 树 )
完全二叉树
dca b
7 5 2 4
c
d
ba
2
4
7 5
WPLa=2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2
=36 =46
6.6 哈夫曼树及其应用
Huffman 树
WPLc=7*1+5*2+2*3+4*3
=35
b
dc
a
7
5
2 4
（ 1）完全二叉树并不一定是 Huffman树；
（ 2） HT是权值越大的越靠近根结点；
（ 3） HT不唯一，但
WPL一定相等。
6.6 哈夫曼树及其应用
2．构造 Huffman树算法
(1) 以权值分别为 W1,W2．．．Ｗ ｎ 的ｎ各结点，构成 n棵二叉树 T1,T2,．．,Tn并组成森林 F={T1,T2,．．,Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点；
(2) 在 F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值 =左右孩子权值之和，
叶结点的权值 = Wi）
(3) 从 F中删除这两棵二叉树，同时将新二叉树加入到 F中 ;
(4) 重复 (2),(3)直到 F中只含一棵二叉树为止，这棵二叉树就是 Huffman 树。
由此可知，有 n个叶子结点的哈夫曼树中结点总数为 2n-1 。
6.6 哈夫曼树及其应用
a b c d
7 5 2 4例,F={ }
a bF={ }
c d
7 5 6
2 4
F={ }a
b
c d
11
6
4
2
5
F={ }a
b
c d
11
6
425
7
18
7
6.6 哈夫曼树及其应用
HT不唯一性,可能出现在,
（ 1）构造新树时，左、右孩子未作规定。
（ 2）当有多个权值相同的树，可作有候选树时，选择谁未作规定。
二、哈夫曼编码（ Huffman 树的应用）
1、问题的提出通讯中常需要将文字转换成二进制字符串电文进行传送。文字 电文，称为 编码 。
反之，收到电文后要将电文转换成原来的文字，
电文 文字，称为 译码 。
6.6 哈夫曼树及其应用例如：需将文字,ABACCDA”转换成电文。文字中 有四种字符，用 2位二进制便可分辨。
A B C D
00 01 10 11
编码方案 1：
则上述文字的电文为,00010010101100 共 14位。
译码时，只需每 2位一译即可。
特点：等长等频率编码，译码容易，但电文不一定最短,
6.6 哈夫曼树及其应用
A B C D
0 00 1 01
编码方案 2：
采用不等长编码，让出现次数多的字符用短码。
则上述文字的电文为,000011010 共 9位。
但无法译码，它即可译为 BBCCACA，也可译为
AAAACCDA等。
6.6 哈夫曼树及其应用
A B C D
0 110 10 111
编码方案 3：
采用不等长编码，让出现次数多的字符用短码，
且任一编码不能是另一编码的前缀,即前缀编码。
则上述文字的电文为,0110010101110 共 13位。
6.6 哈夫曼树及其应用设有 n种字符，每种字符出现的次数为 Wi,
其编码长度为 Li (i=1,2,．．,n)，
则整个电文总长度为 ∑ Wi Li,
要得到最短的电文，即使得 ∑ Wi Li最小。
也就是以字符出现的次数为权值，构造一棵 Huffman树，
并规定左分支编码位 0，右分支编码为 1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。
用构造 Huffman树编出来的码，称为 Huffman编码。
6.6 哈夫曼树及其应用对上例有,
1
A
3 C
B D
1
1
2 0
0
0
1 1
习题
A
B C
GF H
D E
I KJ
ML N
PO
1、对于 3个结点 A,B,C可组成多少种不同的二叉树？请画出。
2、写出图中所示的树的叶子结点，非终端结点的度和树深。
习题
3、写出图中所示的二叉树的先序、中序和后序的遍历结果并画出相应的线索树的逻辑图。
4、有一组数值 14,21,32,15,28，画出哈夫曼树的生成过程。
A
B C
D E
I
GF
JH
