1
§ 5.6.2 根据广义表表示创建树
(一 )二叉树的广义表表示
一棵以 r为根的二叉树的广义表表示 （ 广义表表达式 ） 定义为如下形
式：
(R)
其中, R可递归地定义为：
a) 若 r空树, 则 R的形式为星号, 即, *” ；
b) 若 r是叶子, 则 R的形式为, rN
c) 若 r是非叶子结点, 则 R的形式为,r(rL,rR)
其中,rN为结点 r的标识,rL和 rR分别为 r的左右子树的广义表表示。
2
§ 5.6.2 根据广义表表示创建树
(一 )二叉树的广义表表示
1
2 3
4
5
3
1
2 4
5
广义表,(1(2(*,4(5,*)),3)) 广义表,(1(*,3(2,4(5,*))))
图 - 二叉树的广义表表示
3
§ 5.6.2 根据广义表表示创建树
(二 )广义表创建树的非递归算法
template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>::
GListToTree(long *gListExp,TElem *es,long numElem)
{
TBinTreeNode<TElem> *p,*rt,**s;
long top,i;
if (numElem<2) return NULL;
s = new TBinTreeNode<TElem> *[numElem+1];
if (s==NULL) throw TExcepComm(3);
4
p = new TBinTreeNode<TElem>;
if (p==NULL)
{
delete [] s;
throw TExcepComm(3);
}
top=0; i=1;
rt = p;
p->SetElem(&es[gListExp[i]]);
s[++top] = p;
5
do
{
i++;
if (gListExp[i]=='(') continue;
if (gListExp[i]==',' || gListExp[i]==')') top--;
else
{
if (gListExp[i]=='*') p = NULL;
else
{
p = new TBinTreeNode<TElem>;
if (p==NULL)
{
delete [] s;
throw TExcepComm(3);
}
p->SetElem(&es[gListExp[i]]);
}
6
if (gListExp[i-1] == '(' )
{
s[top]->SetSon(1,p);
if (p!=NULL) p->SetFather(1,s[top]);
}
else
{
s[top]->SetSon(2,p);
if (p!=NULL) p->SetFather(2,s[top]);
}
s[++top] = p;
}
} while (top!=0);
delete [] s;
return rt;
}
7
§ 5.6.2 根据广义表表示创建树
(三 )广义表创建树的递归算法
? 二叉树广义表表达式，其表元素有三种：
– 空子树符号, *”
– 叶子结点符号（其后不带左圆括号）
– 子树的广义表表达式。
8
§ 5.6.2 根据广义表表示创建树
(三 )广义表创建树的递归算法
? 在算法中，应分别考虑这三种情况，即先读出根结点名
称，为其申请一个树结点，然后读它的左右子树
– 若子树的根结点为, *”,则将根的相应链域置为空；
– 若子树的根结点为叶子，则为其分配一个树结点，并将根的相
应链域置为所分配结点的地址；
– 否则通过递归调用建立子树，然后将子树的根指针作为树的根
结点的相应链域的值。
9
§ 5.7 二叉树的线索化
§ 5.7.1线索化的概念
? 线索化的目的
– 有时需知道二叉树结点在某种遍历方式下的前趋与后继。
? 一棵具有 n个结点的二叉树，有 (n+1)个 空链域 (2n0
+n1)，占总链域数目（ 2n）的 1/2多
? 线索化
– 规定对任一结点，用空左链域存放它的前趋的指针
– 用空右链存放它的后继的指针
– 若某链域不空，则不存贮前趋与后继指针。 线索化,
被线索化了的树为线索树。
10
§ 5.7.1线索化的概念
要分清是
哪种哦
? 四种线索化方法和线索树：
– 前序线索化 /树
– 中序线索化 /树
– 后序线索化 /树
– 层序线索化 /树。
11
§ 5.7.1线索化的概念
? 【 例 5.5】 中序线索化树。
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
12
§ 5.7.1线索化的概念
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
? 标志 信息
– 00：左右链均为树结构信息；
– 01：左为树结构信息, 右为线索；
– 10：左为线索, 右为树结构信息；
– 11：左右均为线索；
13
§ 5.7.1线索化的概念
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
改写二叉树二指针存贮结构的描述,
增加关于线索的标志：
struct TBinTreeNodeThread
{
TElem info;
struct TBinTreeNode *lc,*rc;
unsigned char threadTag;
… …
};
14
§ 5.7.1线索化的概念
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
该类 /结构应是前面介绍的 TBinTreeNode的派生类：
struct TBinTreeNodeThread, public TBinTreeNode
{
unsigned char threadTag;
… …
};
15
§ 5.7.2 线索化算法
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
? 线索化过程实质上是一种特殊的遍历过程。
? 在线索化中,,访问, 结点就是要检查结点的
左右链是否为空，若空，则令其指向（遍历意
义下的）前趋或后继。
16
§ 5.7.2 线索化算法
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
long InThread(TBinTreeNode *rt,TBinTreeNode **pre)
{
long cnt=0;
if (rt==NULL) return 0;
cnt = InThread(rt->lc,pre);
if (rt->lc==NULL)
{
rt->lc = *pre;
rt->threadTag=0x02;
}
else rt->threafTag = 0x00;
中序线索化
17
if (*pre!=NULL)
if (*pre->rc==NULL)
{
pre->rc=rt;
pre->threadTag=pre->threadTag| 0x01;
//由于该标志已在前面设置过左标志, 故为了不破坏其, 应使用, 或,
}
else *pre->threadTag=pre->threadTag | 0x00;
*pre = rt;
cnt = cnt + InThread(rt->rc,pre);
return cnt+1;
}
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
18
再定义一个函数 (C++重载 ),它是上面函数的, 打包,, 但参数
中去掉了只在实现中使用的部分 。
long InThread(TBinTreeNodeThread *rt)
{
TBinTreeNodeThread *pre=NULL;
return InThread(rt,&pre);
}
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
19
§ 5.8 树与森林
? 树与森林操作
? 树与森林存储
? 树与森林与二叉树的转化
20
§ 5.8.1 树与森林的遍历
(一 )树的遍历
? 遍历方法
– 先根
– 后根
– 层序
21
§ 5.8.1 树与森林的遍历
(一 )树的遍历
1．先根遍历
先根遍历以 root为根的树 （ 子树 ） 的规则为：
a) 若 root为空, 则无动作, 结束 ;
b) 若 root不空, 则先访问根结点, 然后按此规则
（ 先根 ）, 按各子树的次序 （ 若为无序树, 则次
序任意 ） 分别遍历 root的各子树 。
22
§ 5.8.1 树与森林的遍历
(一 )树的遍历
2．后根遍历
后根遍历以 root为根的树 （ 子树 ） 的规则为：
a) 若 root为空, 则无动作, 结束 ;
b) 若 root不空, 则按后根遍历规则, 按各子树
的次序 （ 若为无序树, 则次序任意 ） 分别遍
历 root的各子树, 然后访问根 。
23
§ 5.8.1 树与森林的遍历
(一 )树的遍历
? 若为无序树，则各子树的访问 /遍历次序是随意的，
因此，无序树的先根和后根遍历结果不唯一。
? 一般情况下，我们假定按各子树的（在图中，或在存
储结构中，或在形式定义中）出现次序遍历。
24
§ 5.8.1 树与森林的遍历
(一 )树的遍历
【 例 5.6】 对图 5-0所示树的遍历结果为：
先根,1 2 4 6 5 7 8 12 3 9 10 11
后根,4 5 7 6 8 2 12 10 9 11 3 1
1
2 3
4 119
12
6 8
5 7 10
图 - 一棵 3叉树
25
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
? 遍历方式：
– 前序遍历
– 后序遍历
– 层序遍历
26
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
1,前序遍历
a) 若森林为空, 则无动作, 返回 。
b) 若森林非空, 则
·先访问森林中的第 1棵子树的根结点；
·前序遍历第 1棵子树的根的各子树构成的森林；
·前序遍历除去第 1棵子树后剩余子树构成的森林 。
27
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
2,后序遍历
a) 若森林为空, 则无动作, 返回 。
b) 若森林不空, 则
·后序遍历森林中第 1棵子树的根结点的各子树构
成 的森林 。
·访问第 1棵子树的根 。
·后序遍历除去第 1棵子树后剩余子树构成的森林 。
28
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
【 例 5.7】 对图 5-0所示森林的遍历结果为：
前序,1 2 4 6 8 5 3 7 a b c d f e g h i k j
后序,4 8 6 2 5 7 3 1 b f d e c a h k i j g
a
c
ed
b
f
（ b）树 b
g
h i j
k
（ c）树 c
3
7
1
2
4
5
6
8
（ a）树 a
图 - 一个森林
29
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 树与二叉树间的转化，主要目的
– 若能将树确定地转化为二叉树，并可确定地将转化
后的结果还原为原树，则对树的处理就转化为对二
叉树的处理了
30
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 树 二叉树
– 基本思想是，对每一树结点，都将它转化为一个二
叉树结点，它的第 1个儿子作为它在二叉树中的左
儿子，而将它的第二个儿子做为第一个儿子的右儿
子，第三个儿子做为第二个儿子的右儿子,…,余
类推。
31
1
2
4
6
5
3
78
a
b
c
ef
d
g
h
i
jk
图 - 图 5.18所示的三棵树的二叉树转化形式
转化后的二叉树的根肯定无右儿子，而且，树中叶子，在二叉树
中无左儿子，若其（树中的叶子）在树中无兄弟，或有兄弟，但
排行最后（兄弟），则转化后仍为叶子。
a
c
ed
b
f
（ b）树 b
g
h i j
k
（ c）树 c
3
7
1
2
4
5
6
8
（ a）树 a
图 - 一个森林
32
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 二叉树 树
? 具体方法：
– 对任一个二叉树结点，将它的左儿子作为第 1个儿
子，而将左儿子的右分枝上各结点依次作为它的第
2、第 3,… 第 n个儿子。
33
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 可以将上述转化方法推广到森林。
– 设森林中有 n棵树 (n>1)，先按上述方法分别将这 n
棵树转化为 n棵二叉树，然后，将这 n棵二叉树的根
相连即可。根相连的方法是，将第 k棵二叉树作为
第 (k-1)棵二叉树的根的右子树,k=2,3,… n
34
§ 5.8.2 树 /森林与二叉树之间的转化
(二 )转化方法的形式描述
1,森林转化为二叉树
设 F={T1,T2,...,Tm}是森林, 则可按如下规则转化为一棵
二叉树 B=(root,LB,RB).
? 若 F为空, 即 m=0,则 B为空树；
? 若 F非空, 则 B的根 root即为 F中第 1棵子树的根, B的
左子树 LB是由森林 F1={T11,T12,...,T1k}转化来的二叉
树, 这里 F1是由 T1的各子树构成的森林；而 B的右子树
RB是由森林 F1={T2,T3,...,Tm}转化来的二叉树 。
35
§ 5.8.2 树 /森林与二叉树之间的转化
(二 )转化方法的形式描述
2,二叉树转化为森林
设 B=(root,LB,RB)是一棵由森林林转化来的二叉树, 则
可按如下规则将它还原为森林 F={T1,T2,...,Tm}。
·若 B为空, 则 F为空 。
·若 B非空, 则 F中第 1棵树 T1的根即为 B的根 root； T1中根
结点的子树森林 F1是由 B的左子树 LB转化而成的森林；
F中除 T1之外的其他树组成的森林 F'={T2,T3,...,Tm}是
由 B的右子树 RB转化而成的森林 。
36
§ 5.8.2 树 /森林与二叉树之间的转化
(二 )转化方法的形式描述
? 树的遍历结果与它对应的二叉树 （ 由树转化成的二叉
树 ） 有如下对应关系：
树的先根遍历＜＝＝＞转化二叉树的前序遍历
树的后根遍历＜＝＝＞转化二叉树的中序遍历
? 另外, 森林的前序与后序遍历分别与它对应的二叉树
的前序和中序遍历结果相同 。
37
§ 5.8.3 树的存储结构
(一 )双亲表示法（一指针法）
? 每个树结点设置指向父结点的指针
? 特点是与结点结构和子树数目无关
? 某结点出发，容易找到它的祖先，但不能搜索
到后代
38
§ 5.8.3 树的存储结构
(二 )多指针式
? 每个结点设立 n个指向儿子的指针,n为各结点
的最大子树个数
? 由于结点子树个数变化范围大，所以会造成很
大的存储浪费。
39
§ 5.8.3 树的存储结构
(三 )邻接表法
1．存储方法
? 为每个树元素结点分别设一个结点（称为, 元
素结点, ）：其结构为：
元素内容 链头指针
其中,,元素内容, 存放树元素结点的内容；, 链头指
针, 指向该结点对应的, 兄弟链表, 的首结点。
40
§ 5.8.3 树的存储结构
(三 )邻接表法
? 将各结点的“元素结点”集中放在一个一维数组中，
该数组称为邻接表的“头数组”，是邻接表的代表。
也可以不采用数组，而是在“元素结点”中设立链指
针，使各元素结点链为一条链（称为“元素链”）。
? 对每个树结点，设一个单链表，将它的各儿子依次链
到该单链表中。该单链中的结点（称为, 链结点, ）
的结构为：
元素索引 链指针
41
§ 5.8.3 树的存储结构
(三 )邻接表法
元素索引 链指针
其中,,元素索引, 存放该结点对, 头数组,
（存放结点内容的数组）的索引信息，通过该索
引，可在头数组中找到对应, 元素结点, 的位置。
,链指针, 为指向单链表中下个结点的指针。
42
1
2 3
4 109
7
6 8
5
2 7 3 ^
4 6 8 ^
9 10 ^
5 ^
1
2
3
4
5
6
7
8
9
10
^
^
^
^
^
^
图 - 树的邻接表存贮结构示例
43
§ 5.8.3 树的存储结构
(三 )邻接表法
2．高级语言描述：元素结点和链结点
链结点的 C/C++描述为：
struct TTreeLinkNode
{
long nodeId; //元素索引
TTreeLinkNode *next; //链指针
};
44
§ 5.8.3 树的存储结构
(三 )邻接表法
2．高级语言描述：元素结点和链结点
元素结点的 C/C++描述为：
template <class TElem>
struct TTreeNodeAdj
{
TElem info; //元素内容
TTreeLinkNode *firstSon; //链头指针, 实质上指向其第一个儿子
long fatherId; //父亲索引, 即父亲元素结点在数组中的位置
long numSons; //儿子数目
};
45
§ 5.8.3 树的存储结构
(四 )孩子兄弟法
1．存储方法
又称二叉链表法。这种方法与邻接表法很类似，不同的是，
为每个结点另设一个链域，使它提向它的儿子单链表，
而取消头数组。
46
§ 5.8.3 树的存储结构
(四 )孩子兄弟法
1．存储方法
? 对树中每一结点, 设立一个如下结构的结点：
· 对树中每一结点，设立一个单链表，将它的各儿子通过, 下个兄
弟指针, 链在一起，并用它的, 大儿子指针, 指向该链的首结点。
元素内容 大儿子指针 下个兄弟指针
47
8 ^
1 ^
2 7 ^ 3 ^
4 ^ 6 ^ 9 ^ 10 ^ ^
5 ^ ^
图 - 图 5.20所示树的孩子兄弟表示法
1
2 3
4 109
7
6 8
5
48
§ 5.8.3 树的存储结构
(四 )孩子兄弟法
2．高级语言描述
template <class TElem>
struct TTreeNodeBinLink
{
TElem info; //元素内容
TTreeNodeBinLink *firstSon; //大儿子指针
TTreeNodeBinLink *nextBrother; //下个兄弟指针
TTreeNodeBinLink *father; //父亲指针 （ 可不设立 ）
};
49
§ 5.9 树对象模型
? 将树看作一个独立的对象，给出它的属性和方
法（基本操作）接口描述。
? 树对象也主要涉及两个类：
– 树结点类 TTreeNode0
– 树类 TTree
50
§ 5.9.1 树结点对象
(一 )抽象结点
template <class TElem>
class TTreeNode0
{
public:
TElem info;
virtual TElem& GetElem ( ){return info;};
virtual TTreeNode0* SetElem (TElem *e) {info=*e; return this;};
virtual TTreeNode0* GetSon (char sonNo)=0;
virtual TTreeNode0* SetSon (char sonNo,TTreeNode0* pSon)=0;
51
§ 5.9.1 树结点对象
(一 )抽象结点
virtual TTreeNode0* GetFirstSon (void)=0;
virtual TTreeNode0* GetNextSon (void)=0;
virtual TTreeNode0* GetFather ( )=0;
virtual TTreeNode0* SetFather (char sonNo,TTreeNode0* f)=0;
char IsLeaf ( ) {return GetSon(1)==NULL && GetSon(2)==NULL;};
};
52
§ 5.9.1 树结点对象
(二 )具体存储结构下的树结点类
? 邻接表中的 TTreeNodeAdj，孩子兄弟链中的
TTreeNodeBinLink，都应该是这里的 TTreeNode0的派
生类
? 留作练习
53
§ 5.9.2 树类
(二 )具体存储结构下的树结点类
enum TTraverseMode {PreOrder,InOrder,PostOrder,LevelOrder};
template <class TElem>
class TTree
{
public:
TTreeNode0<TElem> *root;
long numNodes;
Ttree ( );
~Ttree ( );
54
virtual TTreeNode0<TElem>* GetRoot(){return root;};
virtual void SetRoot(TTreeNode0<TElem>* rt){root=rt;};
virtual long GetLevel(TTreeNode0<TElem>* pNode);
virtual long GetHeight(TTreeNode0<TElem>* pNode);
virtual long GetNumSubNodes(TTreeNode0<TElem>* pNode);
virtual long GetNumSubNodes(void);
virtual long GetNumLeaves(TTreeNode0<TElem>* pNode);
virtual long Cluster(TTreeNode0<TElem>* pNode,TElem **e,TTraverseMode
tm);
virtual long Cluster(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode tm);
55
virtual long Cluster2(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode tm);
virtual long ClusterDescendants(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterAncestors(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe);
virtual long ClusterAncestors(TTreeNode0<TElem>* pNode,TElem **e);
virtual long ClusterAncestors(TElem &e,TTreeNode0<TElem>**
pNodes);
56
virtual long ClusterJuniors(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterSeniors(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual TTreeNode0<TElem> *DeleteSubTree(
TTreeNode0<TElem>* pNode,char sonNo);
57
/*
virtual long ClusterDescendants(TTreeNode0<TElem>* pNode,
TElem **es,TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterDescendants(TElem &e,TTreeNode0<TElem> **pe,
TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterDescendants(TElem &e,TElem **es,
TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
58
virtual long ClusterJuniors(TTreeNode0<TElem>* pNode,
TElem **es,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterJuniors(TElem& e,TTreeNode0<TElem> **pe,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterJuniors(TElem& e,TElem **es,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
59
virtual long ClusterSeniors(TTreeNode0<TElem>* pNode,
TElem **es,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterSeniors(TElem& e,TElem **es,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterSeniors(TElem& e,TTreeNode0<TElem> **pe,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual TTreeNode0<TElem> *Locate(TTreeNode0<TElem>* rt,TElem &e,
TTraverseMode travMode=PreOrder,long sn=1);
*/
60
virtual long ReleaseSubs(TTreeNode0<TElem>* pNode);
virtual TTreeNode0<TElem> *Locate(TTreeNode0<TElem>* rt,TElem
*e);
virtual void Print(TTreeNode0<TElem> *rt,char mode);
};
61
§ 5.10 树的应用示例 — 哈夫曼树
? 具体应用时，树都有具体的语义
? 应用很广的二叉树 ----哈夫曼树
62
§ 5.10.1 哈夫曼树的基本概念
?权 (Weight)：权是赋予某个实体的一个量, 是对实体的
某个 /些属性的数值化描述 。 在数据结构中, 实体有结点
（ 元素 ） 和边 （ 关系 ） 两大类, 所以, 对应有 结点权 和
边权 。 具体边权或结点权代表什么意义, 由具体情况决
定 。
?通路, 通路长,定义同前 。
?树通路长,从根到各个叶子结点的各条通路的长度之和 。
63
§ 5.10.1 哈夫曼树的基本概念
?树加权通路长,从根到各个叶子结点的各条通路的长度,
分别乘以各自叶子的权, 然后相加, 所得结果称为树加
权通路长 。 设树有 n个叶子, 它们的权分别为 w1,w2,…,
wn,从根到它们的通路的长度分别为 p1,p2,…,pn,则该
树的加权通路长为：
i
n
i
i pw?
?1
64
加权通路长为：
3*1 + 5*8 + 4*6 + 3*2 + 4*4 + 4*3 = 101
§ 5.10.1 哈夫曼树的基本概念
图 - 一棵完全二叉树
2
6 4 3
8
1
65
【 定理 5.1】 给定 n个结点, 可以构造出无数多棵
以这 n个结点为叶子的二叉树 。
§ 5.10.1 哈夫曼树的基本概念
图 - 一棵完全二叉树
2
6 4 3
8
1
66
哈夫曼树,给定 n个值及分别以这 n个值为权的结
点, 则可以构造出任意多棵以这 n个结点为叶
子的二叉树 （ 定理 5.1）, 而其中加权通路长最
小的那棵, 就称为哈夫曼树 。 哈夫曼树也称 最
优二叉树 。
§ 5.10.1 哈夫曼树的基本概念
67
【 定理 5.2】 哈夫曼树是完全二叉树 （ 完全二叉树
为无度为 1的结点的二叉树 ） 。
【 定理 5.3】 完全二叉树的结点总数为 2n-1,这里,
n为叶子总数 。
§ 5.10.1 哈夫曼树的基本概念
68
? 假定已知 n个权值 W={w1,w2,…,wn},构造一棵具有 n个叶子且叶
子权分别对应这 n个值的哈夫曼树 。 则可按下面的步骤建立对应的哈
夫曼树 。
1.[初试化 ] 构造一个森林 F={w1,w2,…,wn},它有 n棵树, 每棵树
只有一个结点, 且其权分别为给定的 n的权值 。
2.[找最小树 ] 从 F中找两棵根权最小的树, 分别以它们为左右子树,
构造一棵新树, 并令新树的根的权为这两棵根权之和 。
3.[删除 ]从 F中将所找到的两棵最小树删除
4.[加入 ]将新构造的树加入 F.
5.[判断 ]若 F中只剩一棵树, 则结束, 其即为所求, 否则, 转 2。
§ 5.10.2 哈夫曼树构造算法
69
? 【 例 5.8】 设有 W={2,3,5,6,7}
§ 5.10.2 哈夫曼树构造算法
2 3 5 6 7
2 3
5 6 75
2 3
5
6 7
5
10
70
2 3
55
10
6 7
13
2 3
5 6 75
10 13
23
图 - 构造哈夫曼树
71
(一 )数据结构的存储考虑
? 构造哈夫曼树的目的一般是求得某种最优化的方案，
如哈夫曼码、逻辑判断方案等
? 数据结构存储方式的选取，一般不需顾及通用性，只
求解决对应的问题
? 给出一种用一维数组存储哈夫曼树的方法
§ 5.10.3 哈夫曼树构造算法的实
现
72
(一 )数据结构的存储考虑
? 该方法实质是树的三指针静态结构 。 每个结点的结构
为
（权值，父亲序号，左儿子序号，右儿序号）
? 各结点存储在一维数组中。 0号位置不使用
? 设哈夫曼树有 n个叶子，则由前面的定理知，其结点总
数为 2n-1,
? 叶子集中存储在前面部分，即 1~n的位置，而
(n+1)~(2n-1)存储其余结点。用 0表示空指针。
§ 5.10.3 哈夫曼树构造算法的实
现
73
2 3
5 6 75
10 13
23
权 父亲 左儿 右儿
0
1 2 6 0 0
2 3 6 0 0
3 5 7 0 0
4 6 8 0 0
5 7 8 0 0
6 5 7 1 2
7 10 9 3 6
8 13 9 4 5
9 23 0 7 8
哈夫曼树存储结构
示例
74
(二 )结构描述
struct THuffmanNode
{
float weightl
long father,lc,rc;
};
? 整棵哈夫曼树, 是元素类型为 THuffmanNode的一维数组 。
? 构造哈夫曼树的已知条件是存放着各个权值的一个一维浮点数组,
其定义形式为
float W[n+1]
? 这里 n表示元素 （ 叶子 ） 个数 。
§ 5.10.3 哈夫曼树构造算法的实
现
75
(二 )程序
? 设哈夫曼树构造子程序原型为
HuffmanGen(float *W,int n,THuffmanNode *ht)
? 这里, W存放为已知的 n个权值, ht为存放所生成的哈
夫曼树的一维树组 。
§ 5.10.3 哈夫曼树构造算法的实
现
76
(二 )程序
? 程序开始时, 应先初始化 ht,使其 1~n号元素存方各个叶子 （ 相当
于初始森林 ） 。 此时, 它们都没有父亲, 也没有儿子 。
for (i=1; i<=n; i++)
{
ht[i].weight = W[i];
ht[i].father = 0;
ht[i].lc = ht[i].rc = 0;
}
§ 5.10.3 哈夫曼树构造算法的实
现
77
(二 )程序
? 完成初始化后, 就可以进入一个循环过程, 依次生成 ht
的 (n+1)~(2n-1)号结点, 也就是实施哈夫曼树构造算法中
的步骤 2~5
§ 5.10.3 哈夫曼树构造算法的实
现
78
for (i=n+1; i<2*n; i++)
{
Selecte2Small(ht,i-1,&s1,&s2); //从 ht[1]~ht[i-1]中找两个无父亲的权
最小的结点,
//将其序号存入 s1和 s2
ht[i].weight = ht[s1].weight+ ht[s2].weight;
ht[i].father= 0;
ht[i].lc = s1;
ht[i].rc = s2;
ht[s1].father = i;
ht[s2].fathe = i;
};
79
下面是 Selecte2Small()的实现 。
int Selecte2Small(THuffmanNode *ht,int k,int *s1,int *s2)
{ //从 ht[1]~ht[k]中找两个无父亲的权最小的结点, 将其序号分别存入 s1和 s2
long i,j;
if (k<2) return -1;
*s1=0; *s2=0;
for (j=1; j<=k; j++) //令 *s1和 *s2分别指向 ht中最前两个无父亲的元素
{
if (ht[j].father != 0 ) continue;
if (*s1==0) *s1=j;
else {*s2=j; break; }
}
80
if (*s1==0 || *s2==0) return -1;
if (ht[(*s1].weight> ht[*s2].weight)
/*令 s1和 s2分别持有 ht中最前面两个无父亲的根权最小者中第一和第
二小 */
{
i = *s1; *s1=*s2; *s2 = i;
}
81
for (i=j+1; i<=k; i++)
{
if (ht[i].father != 0 ) continue;
if (ht[i].weight < ht[*s1].weight )
{
*s2 = *s1;
*s1 = i;
}
else
if (ht[i].weight < ht[*s2].weight) *s2 = i;
} //for
return 0;
}
82
? 凡涉及根据给定叶子（带权）求其, 规模最小, 的二
叉树的问题，都可归结到哈夫曼树
– 哈夫曼逻辑判定树
– 哈夫曼编码
§ 5.10.4 哈夫曼树的应用
83
(一 )哈夫曼逻辑判定树
? 设某工厂的某种产品按某种测度（属性）分等级
§ 5.10.4 哈夫曼树的应用
表 5-2 某种产品按某种测度（属性）的分等级及其出现
测度 f 0—20 21—40 51—60 71—90 91--100
等级 g E D C B A
出现概率 p(%) 2 5 13 70 10
84
f≤20
f≤40E级
f≤60
f≤90
D级
C级
B级 A级
70<f≤90
B级 50<f≤60
90<f≤100
20<f≤40
C级
C级
D级 E级
图 - 两棵不同的判定树
哪一个 判定方式效率高？
若把等级的出现概率看作叶子的权，则上述判定方式
的选择，是个构造哈夫曼树的问题。
85
(二 )哈夫曼编码与文本压缩
? 目前，在用电子方式处理符号时，先对符号用二进制
编码
? 为了缩短文件（报文）长度，也采用不定长编码。其
基本思想是，给使用频度较高的字符，编以较短的编码。
? 如何给电文字符编以不定长编码，使各种电文平均最
短呢？这也是个哈夫曼树问题。
§ 5.10.4 哈夫曼树的应用
ASCII编码
定长编码
86
(二 )哈夫曼编码与文本压缩
? 前缀码,如果在一个编码系统中, 任一个编码都不是另
外其他任何编码的的前缀 （ 最左子串 ）, 则称该编码系统
中的编码是前缀码 。
? 例如, 下面一组编码：
01,001,010,100,110
就不是前缀码
? 若是前缀码，则在电文中，各字符对应的编码之间不需
要分隔符。
§ 5.10.4 哈夫曼树的应用
87
(二 )哈夫曼编码与文本压缩
? 哈夫曼码,对一棵具有 n个叶子的哈夫曼树, 若对树中
的每个左分支赋予 0,右分支赋予 1,则从根到每个叶子的
通路上, 各分支的赋值分别构成一个二进制串, 该种二进
制串就称为哈夫曼码 。
? 显然, 在哈夫曼树中, 每个叶子分别对应一个哈夫曼码 。
§ 5.10.4 哈夫曼树的应用
88
? 例如, 设图 5-1是一棵哈
夫曼树, 则各叶子的哈夫
曼码为：
15,00
8,0100
2,0101
10,011
40,10
25,11
0
0 1
1
15 40 25
10
8 2
1
1
1
0
0
0
图 - 哈夫曼编码树
89
(二 )哈夫曼编码与文本压缩
? 【 定理 5.4】 哈夫曼码是前缀码 。
? 【 定理 5.5】 哈夫曼码是最短前缀码, 即, 对于 n个字符,
分别以它们的使用频度为叶子权, 构造哈夫曼树, 则该树
对应的哈夫曼码, 则能使各种报文 （ 由这 n种字符构成的
文本 ） 对应的二进制串平均最短 。
§ 5.10.4 哈夫曼树的应用
§ 5.6.2 根据广义表表示创建树
(一 )二叉树的广义表表示
一棵以 r为根的二叉树的广义表表示 （ 广义表表达式 ） 定义为如下形
式：
(R)
其中, R可递归地定义为：
a) 若 r空树, 则 R的形式为星号, 即, *” ；
b) 若 r是叶子, 则 R的形式为, rN
c) 若 r是非叶子结点, 则 R的形式为,r(rL,rR)
其中,rN为结点 r的标识,rL和 rR分别为 r的左右子树的广义表表示。
2
§ 5.6.2 根据广义表表示创建树
(一 )二叉树的广义表表示
1
2 3
4
5
3
1
2 4
5
广义表,(1(2(*,4(5,*)),3)) 广义表,(1(*,3(2,4(5,*))))
图 - 二叉树的广义表表示
3
§ 5.6.2 根据广义表表示创建树
(二 )广义表创建树的非递归算法
template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>::
GListToTree(long *gListExp,TElem *es,long numElem)
{
TBinTreeNode<TElem> *p,*rt,**s;
long top,i;
if (numElem<2) return NULL;
s = new TBinTreeNode<TElem> *[numElem+1];
if (s==NULL) throw TExcepComm(3);
4
p = new TBinTreeNode<TElem>;
if (p==NULL)
{
delete [] s;
throw TExcepComm(3);
}
top=0; i=1;
rt = p;
p->SetElem(&es[gListExp[i]]);
s[++top] = p;
5
do
{
i++;
if (gListExp[i]=='(') continue;
if (gListExp[i]==',' || gListExp[i]==')') top--;
else
{
if (gListExp[i]=='*') p = NULL;
else
{
p = new TBinTreeNode<TElem>;
if (p==NULL)
{
delete [] s;
throw TExcepComm(3);
}
p->SetElem(&es[gListExp[i]]);
}
6
if (gListExp[i-1] == '(' )
{
s[top]->SetSon(1,p);
if (p!=NULL) p->SetFather(1,s[top]);
}
else
{
s[top]->SetSon(2,p);
if (p!=NULL) p->SetFather(2,s[top]);
}
s[++top] = p;
}
} while (top!=0);
delete [] s;
return rt;
}
7
§ 5.6.2 根据广义表表示创建树
(三 )广义表创建树的递归算法
? 二叉树广义表表达式，其表元素有三种：
– 空子树符号, *”
– 叶子结点符号（其后不带左圆括号）
– 子树的广义表表达式。
8
§ 5.6.2 根据广义表表示创建树
(三 )广义表创建树的递归算法
? 在算法中，应分别考虑这三种情况，即先读出根结点名
称，为其申请一个树结点，然后读它的左右子树
– 若子树的根结点为, *”,则将根的相应链域置为空；
– 若子树的根结点为叶子，则为其分配一个树结点，并将根的相
应链域置为所分配结点的地址；
– 否则通过递归调用建立子树，然后将子树的根指针作为树的根
结点的相应链域的值。
9
§ 5.7 二叉树的线索化
§ 5.7.1线索化的概念
? 线索化的目的
– 有时需知道二叉树结点在某种遍历方式下的前趋与后继。
? 一棵具有 n个结点的二叉树，有 (n+1)个 空链域 (2n0
+n1)，占总链域数目（ 2n）的 1/2多
? 线索化
– 规定对任一结点，用空左链域存放它的前趋的指针
– 用空右链存放它的后继的指针
– 若某链域不空，则不存贮前趋与后继指针。 线索化,
被线索化了的树为线索树。
10
§ 5.7.1线索化的概念
要分清是
哪种哦
? 四种线索化方法和线索树：
– 前序线索化 /树
– 中序线索化 /树
– 后序线索化 /树
– 层序线索化 /树。
11
§ 5.7.1线索化的概念
? 【 例 5.5】 中序线索化树。
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
12
§ 5.7.1线索化的概念
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
? 标志 信息
– 00：左右链均为树结构信息；
– 01：左为树结构信息, 右为线索；
– 10：左为线索, 右为树结构信息；
– 11：左右均为线索；
13
§ 5.7.1线索化的概念
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
改写二叉树二指针存贮结构的描述,
增加关于线索的标志：
struct TBinTreeNodeThread
{
TElem info;
struct TBinTreeNode *lc,*rc;
unsigned char threadTag;
… …
};
14
§ 5.7.1线索化的概念
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
该类 /结构应是前面介绍的 TBinTreeNode的派生类：
struct TBinTreeNodeThread, public TBinTreeNode
{
unsigned char threadTag;
… …
};
15
§ 5.7.2 线索化算法
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
? 线索化过程实质上是一种特殊的遍历过程。
? 在线索化中,,访问, 结点就是要检查结点的
左右链是否为空，若空，则令其指向（遍历意
义下的）前趋或后继。
16
§ 5.7.2 线索化算法
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
long InThread(TBinTreeNode *rt,TBinTreeNode **pre)
{
long cnt=0;
if (rt==NULL) return 0;
cnt = InThread(rt->lc,pre);
if (rt->lc==NULL)
{
rt->lc = *pre;
rt->threadTag=0x02;
}
else rt->threafTag = 0x00;
中序线索化
17
if (*pre!=NULL)
if (*pre->rc==NULL)
{
pre->rc=rt;
pre->threadTag=pre->threadTag| 0x01;
//由于该标志已在前面设置过左标志, 故为了不破坏其, 应使用, 或,
}
else *pre->threadTag=pre->threadTag | 0x00;
*pre = rt;
cnt = cnt + InThread(rt->rc,pre);
return cnt+1;
}
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
18
再定义一个函数 (C++重载 ),它是上面函数的, 打包,, 但参数
中去掉了只在实现中使用的部分 。
long InThread(TBinTreeNodeThread *rt)
{
TBinTreeNodeThread *pre=NULL;
return InThread(rt,&pre);
}
1
2 3
4
5
76
图 - 中序线索树
中序,2 5 4 1 6 3 7
19
§ 5.8 树与森林
? 树与森林操作
? 树与森林存储
? 树与森林与二叉树的转化
20
§ 5.8.1 树与森林的遍历
(一 )树的遍历
? 遍历方法
– 先根
– 后根
– 层序
21
§ 5.8.1 树与森林的遍历
(一 )树的遍历
1．先根遍历
先根遍历以 root为根的树 （ 子树 ） 的规则为：
a) 若 root为空, 则无动作, 结束 ;
b) 若 root不空, 则先访问根结点, 然后按此规则
（ 先根 ）, 按各子树的次序 （ 若为无序树, 则次
序任意 ） 分别遍历 root的各子树 。
22
§ 5.8.1 树与森林的遍历
(一 )树的遍历
2．后根遍历
后根遍历以 root为根的树 （ 子树 ） 的规则为：
a) 若 root为空, 则无动作, 结束 ;
b) 若 root不空, 则按后根遍历规则, 按各子树
的次序 （ 若为无序树, 则次序任意 ） 分别遍
历 root的各子树, 然后访问根 。
23
§ 5.8.1 树与森林的遍历
(一 )树的遍历
? 若为无序树，则各子树的访问 /遍历次序是随意的，
因此，无序树的先根和后根遍历结果不唯一。
? 一般情况下，我们假定按各子树的（在图中，或在存
储结构中，或在形式定义中）出现次序遍历。
24
§ 5.8.1 树与森林的遍历
(一 )树的遍历
【 例 5.6】 对图 5-0所示树的遍历结果为：
先根,1 2 4 6 5 7 8 12 3 9 10 11
后根,4 5 7 6 8 2 12 10 9 11 3 1
1
2 3
4 119
12
6 8
5 7 10
图 - 一棵 3叉树
25
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
? 遍历方式：
– 前序遍历
– 后序遍历
– 层序遍历
26
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
1,前序遍历
a) 若森林为空, 则无动作, 返回 。
b) 若森林非空, 则
·先访问森林中的第 1棵子树的根结点；
·前序遍历第 1棵子树的根的各子树构成的森林；
·前序遍历除去第 1棵子树后剩余子树构成的森林 。
27
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
2,后序遍历
a) 若森林为空, 则无动作, 返回 。
b) 若森林不空, 则
·后序遍历森林中第 1棵子树的根结点的各子树构
成 的森林 。
·访问第 1棵子树的根 。
·后序遍历除去第 1棵子树后剩余子树构成的森林 。
28
§ 5.8.1 树与森林的遍历
(二 )森林的遍历
【 例 5.7】 对图 5-0所示森林的遍历结果为：
前序,1 2 4 6 8 5 3 7 a b c d f e g h i k j
后序,4 8 6 2 5 7 3 1 b f d e c a h k i j g
a
c
ed
b
f
（ b）树 b
g
h i j
k
（ c）树 c
3
7
1
2
4
5
6
8
（ a）树 a
图 - 一个森林
29
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 树与二叉树间的转化，主要目的
– 若能将树确定地转化为二叉树，并可确定地将转化
后的结果还原为原树，则对树的处理就转化为对二
叉树的处理了
30
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 树 二叉树
– 基本思想是，对每一树结点，都将它转化为一个二
叉树结点，它的第 1个儿子作为它在二叉树中的左
儿子，而将它的第二个儿子做为第一个儿子的右儿
子，第三个儿子做为第二个儿子的右儿子,…,余
类推。
31
1
2
4
6
5
3
78
a
b
c
ef
d
g
h
i
jk
图 - 图 5.18所示的三棵树的二叉树转化形式
转化后的二叉树的根肯定无右儿子，而且，树中叶子，在二叉树
中无左儿子，若其（树中的叶子）在树中无兄弟，或有兄弟，但
排行最后（兄弟），则转化后仍为叶子。
a
c
ed
b
f
（ b）树 b
g
h i j
k
（ c）树 c
3
7
1
2
4
5
6
8
（ a）树 a
图 - 一个森林
32
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 二叉树 树
? 具体方法：
– 对任一个二叉树结点，将它的左儿子作为第 1个儿
子，而将左儿子的右分枝上各结点依次作为它的第
2、第 3,… 第 n个儿子。
33
§ 5.8.2 树 /森林与二叉树之间的转化
(一 )基本转化方法
? 可以将上述转化方法推广到森林。
– 设森林中有 n棵树 (n>1)，先按上述方法分别将这 n
棵树转化为 n棵二叉树，然后，将这 n棵二叉树的根
相连即可。根相连的方法是，将第 k棵二叉树作为
第 (k-1)棵二叉树的根的右子树,k=2,3,… n
34
§ 5.8.2 树 /森林与二叉树之间的转化
(二 )转化方法的形式描述
1,森林转化为二叉树
设 F={T1,T2,...,Tm}是森林, 则可按如下规则转化为一棵
二叉树 B=(root,LB,RB).
? 若 F为空, 即 m=0,则 B为空树；
? 若 F非空, 则 B的根 root即为 F中第 1棵子树的根, B的
左子树 LB是由森林 F1={T11,T12,...,T1k}转化来的二叉
树, 这里 F1是由 T1的各子树构成的森林；而 B的右子树
RB是由森林 F1={T2,T3,...,Tm}转化来的二叉树 。
35
§ 5.8.2 树 /森林与二叉树之间的转化
(二 )转化方法的形式描述
2,二叉树转化为森林
设 B=(root,LB,RB)是一棵由森林林转化来的二叉树, 则
可按如下规则将它还原为森林 F={T1,T2,...,Tm}。
·若 B为空, 则 F为空 。
·若 B非空, 则 F中第 1棵树 T1的根即为 B的根 root； T1中根
结点的子树森林 F1是由 B的左子树 LB转化而成的森林；
F中除 T1之外的其他树组成的森林 F'={T2,T3,...,Tm}是
由 B的右子树 RB转化而成的森林 。
36
§ 5.8.2 树 /森林与二叉树之间的转化
(二 )转化方法的形式描述
? 树的遍历结果与它对应的二叉树 （ 由树转化成的二叉
树 ） 有如下对应关系：
树的先根遍历＜＝＝＞转化二叉树的前序遍历
树的后根遍历＜＝＝＞转化二叉树的中序遍历
? 另外, 森林的前序与后序遍历分别与它对应的二叉树
的前序和中序遍历结果相同 。
37
§ 5.8.3 树的存储结构
(一 )双亲表示法（一指针法）
? 每个树结点设置指向父结点的指针
? 特点是与结点结构和子树数目无关
? 某结点出发，容易找到它的祖先，但不能搜索
到后代
38
§ 5.8.3 树的存储结构
(二 )多指针式
? 每个结点设立 n个指向儿子的指针,n为各结点
的最大子树个数
? 由于结点子树个数变化范围大，所以会造成很
大的存储浪费。
39
§ 5.8.3 树的存储结构
(三 )邻接表法
1．存储方法
? 为每个树元素结点分别设一个结点（称为, 元
素结点, ）：其结构为：
元素内容 链头指针
其中,,元素内容, 存放树元素结点的内容；, 链头指
针, 指向该结点对应的, 兄弟链表, 的首结点。
40
§ 5.8.3 树的存储结构
(三 )邻接表法
? 将各结点的“元素结点”集中放在一个一维数组中，
该数组称为邻接表的“头数组”，是邻接表的代表。
也可以不采用数组，而是在“元素结点”中设立链指
针，使各元素结点链为一条链（称为“元素链”）。
? 对每个树结点，设一个单链表，将它的各儿子依次链
到该单链表中。该单链中的结点（称为, 链结点, ）
的结构为：
元素索引 链指针
41
§ 5.8.3 树的存储结构
(三 )邻接表法
元素索引 链指针
其中,,元素索引, 存放该结点对, 头数组,
（存放结点内容的数组）的索引信息，通过该索
引，可在头数组中找到对应, 元素结点, 的位置。
,链指针, 为指向单链表中下个结点的指针。
42
1
2 3
4 109
7
6 8
5
2 7 3 ^
4 6 8 ^
9 10 ^
5 ^
1
2
3
4
5
6
7
8
9
10
^
^
^
^
^
^
图 - 树的邻接表存贮结构示例
43
§ 5.8.3 树的存储结构
(三 )邻接表法
2．高级语言描述：元素结点和链结点
链结点的 C/C++描述为：
struct TTreeLinkNode
{
long nodeId; //元素索引
TTreeLinkNode *next; //链指针
};
44
§ 5.8.3 树的存储结构
(三 )邻接表法
2．高级语言描述：元素结点和链结点
元素结点的 C/C++描述为：
template <class TElem>
struct TTreeNodeAdj
{
TElem info; //元素内容
TTreeLinkNode *firstSon; //链头指针, 实质上指向其第一个儿子
long fatherId; //父亲索引, 即父亲元素结点在数组中的位置
long numSons; //儿子数目
};
45
§ 5.8.3 树的存储结构
(四 )孩子兄弟法
1．存储方法
又称二叉链表法。这种方法与邻接表法很类似，不同的是，
为每个结点另设一个链域，使它提向它的儿子单链表，
而取消头数组。
46
§ 5.8.3 树的存储结构
(四 )孩子兄弟法
1．存储方法
? 对树中每一结点, 设立一个如下结构的结点：
· 对树中每一结点，设立一个单链表，将它的各儿子通过, 下个兄
弟指针, 链在一起，并用它的, 大儿子指针, 指向该链的首结点。
元素内容 大儿子指针 下个兄弟指针
47
8 ^
1 ^
2 7 ^ 3 ^
4 ^ 6 ^ 9 ^ 10 ^ ^
5 ^ ^
图 - 图 5.20所示树的孩子兄弟表示法
1
2 3
4 109
7
6 8
5
48
§ 5.8.3 树的存储结构
(四 )孩子兄弟法
2．高级语言描述
template <class TElem>
struct TTreeNodeBinLink
{
TElem info; //元素内容
TTreeNodeBinLink *firstSon; //大儿子指针
TTreeNodeBinLink *nextBrother; //下个兄弟指针
TTreeNodeBinLink *father; //父亲指针 （ 可不设立 ）
};
49
§ 5.9 树对象模型
? 将树看作一个独立的对象，给出它的属性和方
法（基本操作）接口描述。
? 树对象也主要涉及两个类：
– 树结点类 TTreeNode0
– 树类 TTree
50
§ 5.9.1 树结点对象
(一 )抽象结点
template <class TElem>
class TTreeNode0
{
public:
TElem info;
virtual TElem& GetElem ( ){return info;};
virtual TTreeNode0* SetElem (TElem *e) {info=*e; return this;};
virtual TTreeNode0* GetSon (char sonNo)=0;
virtual TTreeNode0* SetSon (char sonNo,TTreeNode0* pSon)=0;
51
§ 5.9.1 树结点对象
(一 )抽象结点
virtual TTreeNode0* GetFirstSon (void)=0;
virtual TTreeNode0* GetNextSon (void)=0;
virtual TTreeNode0* GetFather ( )=0;
virtual TTreeNode0* SetFather (char sonNo,TTreeNode0* f)=0;
char IsLeaf ( ) {return GetSon(1)==NULL && GetSon(2)==NULL;};
};
52
§ 5.9.1 树结点对象
(二 )具体存储结构下的树结点类
? 邻接表中的 TTreeNodeAdj，孩子兄弟链中的
TTreeNodeBinLink，都应该是这里的 TTreeNode0的派
生类
? 留作练习
53
§ 5.9.2 树类
(二 )具体存储结构下的树结点类
enum TTraverseMode {PreOrder,InOrder,PostOrder,LevelOrder};
template <class TElem>
class TTree
{
public:
TTreeNode0<TElem> *root;
long numNodes;
Ttree ( );
~Ttree ( );
54
virtual TTreeNode0<TElem>* GetRoot(){return root;};
virtual void SetRoot(TTreeNode0<TElem>* rt){root=rt;};
virtual long GetLevel(TTreeNode0<TElem>* pNode);
virtual long GetHeight(TTreeNode0<TElem>* pNode);
virtual long GetNumSubNodes(TTreeNode0<TElem>* pNode);
virtual long GetNumSubNodes(void);
virtual long GetNumLeaves(TTreeNode0<TElem>* pNode);
virtual long Cluster(TTreeNode0<TElem>* pNode,TElem **e,TTraverseMode
tm);
virtual long Cluster(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode tm);
55
virtual long Cluster2(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode tm);
virtual long ClusterDescendants(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterAncestors(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe);
virtual long ClusterAncestors(TTreeNode0<TElem>* pNode,TElem **e);
virtual long ClusterAncestors(TElem &e,TTreeNode0<TElem>**
pNodes);
56
virtual long ClusterJuniors(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterSeniors(TTreeNode0<TElem>* pNode,
TTreeNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual TTreeNode0<TElem> *DeleteSubTree(
TTreeNode0<TElem>* pNode,char sonNo);
57
/*
virtual long ClusterDescendants(TTreeNode0<TElem>* pNode,
TElem **es,TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterDescendants(TElem &e,TTreeNode0<TElem> **pe,
TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterDescendants(TElem &e,TElem **es,
TTraverseMode tm = PreOrder,
int startLevel=1,int endLevel=-1);
58
virtual long ClusterJuniors(TTreeNode0<TElem>* pNode,
TElem **es,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterJuniors(TElem& e,TTreeNode0<TElem> **pe,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterJuniors(TElem& e,TElem **es,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
59
virtual long ClusterSeniors(TTreeNode0<TElem>* pNode,
TElem **es,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterSeniors(TElem& e,TElem **es,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual long ClusterSeniors(TElem& e,TTreeNode0<TElem> **pe,
TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
virtual TTreeNode0<TElem> *Locate(TTreeNode0<TElem>* rt,TElem &e,
TTraverseMode travMode=PreOrder,long sn=1);
*/
60
virtual long ReleaseSubs(TTreeNode0<TElem>* pNode);
virtual TTreeNode0<TElem> *Locate(TTreeNode0<TElem>* rt,TElem
*e);
virtual void Print(TTreeNode0<TElem> *rt,char mode);
};
61
§ 5.10 树的应用示例 — 哈夫曼树
? 具体应用时，树都有具体的语义
? 应用很广的二叉树 ----哈夫曼树
62
§ 5.10.1 哈夫曼树的基本概念
?权 (Weight)：权是赋予某个实体的一个量, 是对实体的
某个 /些属性的数值化描述 。 在数据结构中, 实体有结点
（ 元素 ） 和边 （ 关系 ） 两大类, 所以, 对应有 结点权 和
边权 。 具体边权或结点权代表什么意义, 由具体情况决
定 。
?通路, 通路长,定义同前 。
?树通路长,从根到各个叶子结点的各条通路的长度之和 。
63
§ 5.10.1 哈夫曼树的基本概念
?树加权通路长,从根到各个叶子结点的各条通路的长度,
分别乘以各自叶子的权, 然后相加, 所得结果称为树加
权通路长 。 设树有 n个叶子, 它们的权分别为 w1,w2,…,
wn,从根到它们的通路的长度分别为 p1,p2,…,pn,则该
树的加权通路长为：
i
n
i
i pw?
?1
64
加权通路长为：
3*1 + 5*8 + 4*6 + 3*2 + 4*4 + 4*3 = 101
§ 5.10.1 哈夫曼树的基本概念
图 - 一棵完全二叉树
2
6 4 3
8
1
65
【 定理 5.1】 给定 n个结点, 可以构造出无数多棵
以这 n个结点为叶子的二叉树 。
§ 5.10.1 哈夫曼树的基本概念
图 - 一棵完全二叉树
2
6 4 3
8
1
66
哈夫曼树,给定 n个值及分别以这 n个值为权的结
点, 则可以构造出任意多棵以这 n个结点为叶
子的二叉树 （ 定理 5.1）, 而其中加权通路长最
小的那棵, 就称为哈夫曼树 。 哈夫曼树也称 最
优二叉树 。
§ 5.10.1 哈夫曼树的基本概念
67
【 定理 5.2】 哈夫曼树是完全二叉树 （ 完全二叉树
为无度为 1的结点的二叉树 ） 。
【 定理 5.3】 完全二叉树的结点总数为 2n-1,这里,
n为叶子总数 。
§ 5.10.1 哈夫曼树的基本概念
68
? 假定已知 n个权值 W={w1,w2,…,wn},构造一棵具有 n个叶子且叶
子权分别对应这 n个值的哈夫曼树 。 则可按下面的步骤建立对应的哈
夫曼树 。
1.[初试化 ] 构造一个森林 F={w1,w2,…,wn},它有 n棵树, 每棵树
只有一个结点, 且其权分别为给定的 n的权值 。
2.[找最小树 ] 从 F中找两棵根权最小的树, 分别以它们为左右子树,
构造一棵新树, 并令新树的根的权为这两棵根权之和 。
3.[删除 ]从 F中将所找到的两棵最小树删除
4.[加入 ]将新构造的树加入 F.
5.[判断 ]若 F中只剩一棵树, 则结束, 其即为所求, 否则, 转 2。
§ 5.10.2 哈夫曼树构造算法
69
? 【 例 5.8】 设有 W={2,3,5,6,7}
§ 5.10.2 哈夫曼树构造算法
2 3 5 6 7
2 3
5 6 75
2 3
5
6 7
5
10
70
2 3
55
10
6 7
13
2 3
5 6 75
10 13
23
图 - 构造哈夫曼树
71
(一 )数据结构的存储考虑
? 构造哈夫曼树的目的一般是求得某种最优化的方案，
如哈夫曼码、逻辑判断方案等
? 数据结构存储方式的选取，一般不需顾及通用性，只
求解决对应的问题
? 给出一种用一维数组存储哈夫曼树的方法
§ 5.10.3 哈夫曼树构造算法的实
现
72
(一 )数据结构的存储考虑
? 该方法实质是树的三指针静态结构 。 每个结点的结构
为
（权值，父亲序号，左儿子序号，右儿序号）
? 各结点存储在一维数组中。 0号位置不使用
? 设哈夫曼树有 n个叶子，则由前面的定理知，其结点总
数为 2n-1,
? 叶子集中存储在前面部分，即 1~n的位置，而
(n+1)~(2n-1)存储其余结点。用 0表示空指针。
§ 5.10.3 哈夫曼树构造算法的实
现
73
2 3
5 6 75
10 13
23
权 父亲 左儿 右儿
0
1 2 6 0 0
2 3 6 0 0
3 5 7 0 0
4 6 8 0 0
5 7 8 0 0
6 5 7 1 2
7 10 9 3 6
8 13 9 4 5
9 23 0 7 8
哈夫曼树存储结构
示例
74
(二 )结构描述
struct THuffmanNode
{
float weightl
long father,lc,rc;
};
? 整棵哈夫曼树, 是元素类型为 THuffmanNode的一维数组 。
? 构造哈夫曼树的已知条件是存放着各个权值的一个一维浮点数组,
其定义形式为
float W[n+1]
? 这里 n表示元素 （ 叶子 ） 个数 。
§ 5.10.3 哈夫曼树构造算法的实
现
75
(二 )程序
? 设哈夫曼树构造子程序原型为
HuffmanGen(float *W,int n,THuffmanNode *ht)
? 这里, W存放为已知的 n个权值, ht为存放所生成的哈
夫曼树的一维树组 。
§ 5.10.3 哈夫曼树构造算法的实
现
76
(二 )程序
? 程序开始时, 应先初始化 ht,使其 1~n号元素存方各个叶子 （ 相当
于初始森林 ） 。 此时, 它们都没有父亲, 也没有儿子 。
for (i=1; i<=n; i++)
{
ht[i].weight = W[i];
ht[i].father = 0;
ht[i].lc = ht[i].rc = 0;
}
§ 5.10.3 哈夫曼树构造算法的实
现
77
(二 )程序
? 完成初始化后, 就可以进入一个循环过程, 依次生成 ht
的 (n+1)~(2n-1)号结点, 也就是实施哈夫曼树构造算法中
的步骤 2~5
§ 5.10.3 哈夫曼树构造算法的实
现
78
for (i=n+1; i<2*n; i++)
{
Selecte2Small(ht,i-1,&s1,&s2); //从 ht[1]~ht[i-1]中找两个无父亲的权
最小的结点,
//将其序号存入 s1和 s2
ht[i].weight = ht[s1].weight+ ht[s2].weight;
ht[i].father= 0;
ht[i].lc = s1;
ht[i].rc = s2;
ht[s1].father = i;
ht[s2].fathe = i;
};
79
下面是 Selecte2Small()的实现 。
int Selecte2Small(THuffmanNode *ht,int k,int *s1,int *s2)
{ //从 ht[1]~ht[k]中找两个无父亲的权最小的结点, 将其序号分别存入 s1和 s2
long i,j;
if (k<2) return -1;
*s1=0; *s2=0;
for (j=1; j<=k; j++) //令 *s1和 *s2分别指向 ht中最前两个无父亲的元素
{
if (ht[j].father != 0 ) continue;
if (*s1==0) *s1=j;
else {*s2=j; break; }
}
80
if (*s1==0 || *s2==0) return -1;
if (ht[(*s1].weight> ht[*s2].weight)
/*令 s1和 s2分别持有 ht中最前面两个无父亲的根权最小者中第一和第
二小 */
{
i = *s1; *s1=*s2; *s2 = i;
}
81
for (i=j+1; i<=k; i++)
{
if (ht[i].father != 0 ) continue;
if (ht[i].weight < ht[*s1].weight )
{
*s2 = *s1;
*s1 = i;
}
else
if (ht[i].weight < ht[*s2].weight) *s2 = i;
} //for
return 0;
}
82
? 凡涉及根据给定叶子（带权）求其, 规模最小, 的二
叉树的问题，都可归结到哈夫曼树
– 哈夫曼逻辑判定树
– 哈夫曼编码
§ 5.10.4 哈夫曼树的应用
83
(一 )哈夫曼逻辑判定树
? 设某工厂的某种产品按某种测度（属性）分等级
§ 5.10.4 哈夫曼树的应用
表 5-2 某种产品按某种测度（属性）的分等级及其出现
测度 f 0—20 21—40 51—60 71—90 91--100
等级 g E D C B A
出现概率 p(%) 2 5 13 70 10
84
f≤20
f≤40E级
f≤60
f≤90
D级
C级
B级 A级
70<f≤90
B级 50<f≤60
90<f≤100
20<f≤40
C级
C级
D级 E级
图 - 两棵不同的判定树
哪一个 判定方式效率高？
若把等级的出现概率看作叶子的权，则上述判定方式
的选择，是个构造哈夫曼树的问题。
85
(二 )哈夫曼编码与文本压缩
? 目前，在用电子方式处理符号时，先对符号用二进制
编码
? 为了缩短文件（报文）长度，也采用不定长编码。其
基本思想是，给使用频度较高的字符，编以较短的编码。
? 如何给电文字符编以不定长编码，使各种电文平均最
短呢？这也是个哈夫曼树问题。
§ 5.10.4 哈夫曼树的应用
ASCII编码
定长编码
86
(二 )哈夫曼编码与文本压缩
? 前缀码,如果在一个编码系统中, 任一个编码都不是另
外其他任何编码的的前缀 （ 最左子串 ）, 则称该编码系统
中的编码是前缀码 。
? 例如, 下面一组编码：
01,001,010,100,110
就不是前缀码
? 若是前缀码，则在电文中，各字符对应的编码之间不需
要分隔符。
§ 5.10.4 哈夫曼树的应用
87
(二 )哈夫曼编码与文本压缩
? 哈夫曼码,对一棵具有 n个叶子的哈夫曼树, 若对树中
的每个左分支赋予 0,右分支赋予 1,则从根到每个叶子的
通路上, 各分支的赋值分别构成一个二进制串, 该种二进
制串就称为哈夫曼码 。
? 显然, 在哈夫曼树中, 每个叶子分别对应一个哈夫曼码 。
§ 5.10.4 哈夫曼树的应用
88
? 例如, 设图 5-1是一棵哈
夫曼树, 则各叶子的哈夫
曼码为：
15,00
8,0100
2,0101
10,011
40,10
25,11
0
0 1
1
15 40 25
10
8 2
1
1
1
0
0
0
图 - 哈夫曼编码树
89
(二 )哈夫曼编码与文本压缩
? 【 定理 5.4】 哈夫曼码是前缀码 。
? 【 定理 5.5】 哈夫曼码是最短前缀码, 即, 对于 n个字符,
分别以它们的使用频度为叶子权, 构造哈夫曼树, 则该树
对应的哈夫曼码, 则能使各种报文 （ 由这 n种字符构成的
文本 ） 对应的二进制串平均最短 。
§ 5.10.4 哈夫曼树的应用
