6,4 树和森林
6.4.1树的存储结构
一、双亲表示法（顺序存储）
//-----------树的双亲表存储表示 ----------//
#define MAX_TREE_SIZE 100
typedef struct PTNode {
TElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n; //结点数
}PTree;
双亲表示法举例
R
A
D E F
CB
G KH
R -1
A 0
B 0
C 0
D 1
E 1
F 3
G 6
H 6
K 6
0
1
2
3
4
5
6
7
8
9
数组下标,
* 便于涉及双亲的操作；
* 求结点的孩子时需要遍历整棵树。
6.4.1树的存储结构
二、孩子表示法 （顺序存储）
#define MAX_TREE_SIZE 100
typedef struct PTNode {
TElemType data;
int child1; //第 1个孩子 位置域
int child2; //第 2个孩子 位置域
......
int childd; //第 d个孩子 位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n; //结点数
}PTree;
孩子表示法举例
R
A
D E F
CB
G KH
0
1
2
3
4
5
6
7
8
9
数组下标,
* 便于涉及孩子的操作；求双亲不方便；
* 采用同构的结点，空间浪费。
R 1
A 4
B 0
C 6
D 0
E 0
F 7
G 0
H 0
K 0
2 3
5 0
0 0
0 0
0 0
0 0
8 9
0 0
0 0
0 0
孩子链表存储表示 （链式存储）
typedef struct CTNode{ //孩子结点
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct {
TElemType data;
ChildPtr firstchild; //孩子链表头指针
}CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n,r; //结点数和根的位置
}CTree;
孩子链表存储表示 举例
R
A
D E F
CB
G KH
0
1
2
3
4
5
6
7
8
9
数组下标,
* 便于涉及孩子的操作；
* 求结点的双亲时不方便。
R
A
B /
C
D /
E /
F
G /
H /
K /
1 2 3 /
4 5 /
6 /
7 8 9 /
T.nodes[ ]; T.n=10; T.r = 0;
例 1,设树 T以孩子链表为存储结构,
寻找值为 x的双亲结点的算法如下,
Status parent(Ctree T,TElemType x)
{// 当值为 x的结点不存在时返回 -2;
// 当值为 x的结点为根结点时返回 -1,
// 否则返回 x结点的双亲结点的下标值,
if(T.nodes[T.r].data == x) return –1;
//值为 x的结点为根结点 ;
for(i=0;i<T.n;i++)
{ p=T.nodes[i].firstchild;
while(p && T.nodes[p->child].data != x)
p = p->next;
if(p) return (i); // 找到 x的双亲结点
}
return –2; // 值为 x的结点不存在
}
例 2,删除值为 x的结点的第 i棵子树的
算法 delete如下：
void deletej(Ctree &T,int j)
{// 删除树 T的第 j号结点及其子树
if(!T.nodes[j].firstchild){ // 删除叶结点
for(i=j; i<T.n-1; i++) { // j号结点后的结点全部前移一位
T.nodes[i].data = T.nodes[i+1].data;
T.nodes[i].firstchild = T.nodes[i+1].firstchild;
}
T.n--;
}else{
while(s=T.nodes[j].firstchild){
T.nodes[j].firstchild = s->next;
i = s->child;
free(s);
deletej(T,i); // 递归删除第 i号结点及其子树
}
}
}
Status delete(Ctree &T,TElemType x,int i)
{ // 当值为 x的结点不存在时返回 -2;当值为 x的结点为
//叶结点或无第 i 棵子树时返回 -1,否则返回 1.
for(k=0; k<T.n; k++)
if(T.nodes[k].data == x) break; // 找到值为 x的结点
if(k>=T.n) return –2; // 值为 x的结点不存在
p= T.nodes[k].firstchild;
j = 1;
if(!p) return –1; // x结点为叶结点
if(i==1){ // 删除长子时,特殊处理
j =p->child; // 记住要删除子树的下标
T.nodes[k].firstchild = p->next;
free(p);
}else{
while(p->next && j<i-1){p = p->next ; j++;}
if(j>i-1 || !p->next) return –1; // 无第 i 棵子树
// p指向第 i-1 个儿子
j = p->next->child; // 记住要删除子树的下标
s = p->next; p->next = s->next; free(s);
}
deletej(T,j); // 递归删除第 j号结点及其子树
return 1;
}
三,孩子兄弟表示法
---树的二叉树表示法 (二叉链表示法 )
? //-----树的二叉链表 (孩子兄弟 )存储表示 ------
typedef struct CSNode {
ELemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
R
A
D E F
CB
G KH
R ?
A
?D
E ?? C ?
H?
F ?
G?
B?
K? ?
孩子兄弟表示法示例：
6.4.2 森林与二叉树的转换
一,森林转换成二叉树
? 如果 F={T1,T2,…,Tm}是森林,则可按如下规则
转换成一棵二叉树 B=(root,LB,RB)。
? (1)若 F为空, 即 m=0,则 B为空树；
? (2)若 F非空, 即 m<>0,则 B的根 root即为森林
中第一棵树的根 ROOT(T1)；
? B的左子树 LB是从 T1中根结点的子树森林
F1={T11,T12,…,T1m1}转换而成的二叉树 ;
? 其右子对 RB是从森林 F'={T2,T3,…,Tm} 转换
而成的二叉树,
二, 二叉树转换成森林
? 如果 B=(root,LB,RB)是一棵二叉树,则可按如下规
则转换成森林 F={T1,T2,…,Tm}：
? (1)若 B为空, 则 F为空；
? (2)若 B非空, 则 F中第一棵树 T1的根 ROOT(T1)
即为二叉树 B的根 root；
? T1中的根结点的子树森林 F1是由 B的左子树
LB转换而成的森林 ;
? F中除 T1之外其余树组成的森林 F'={T2,T3,…,
Tm}是由 B的右子树 RB转换而成的森林 。
6.4.3 树和森林的遍历
? 树的两种遍历方法：
? 一, 先根遍历：
? （ 1） 访问树的根结点；
? （ 2） 依次先根遍历每棵子树 。
? R A D E B C F G H K
? 二、后根遍历：
? （ 1）依次后根遍历每棵子树。
? （ 2）访问树的根结点；
? D E A B G H K F C R
R
A
D E F
CB
G KH
森林的两种遍历方法：
? 一, 先序遍历森林：
? 若森林非空, 则
? （ 1） 访问森林中第一棵树的根结点；
? （ 2） 先序遍历第一棵树的根结点的子树森林；
? （ 3） 先序遍历除去第一棵树之后的森林 。
? 二、中序遍历森林：
? 若森林非空，则
? （ 1）中序遍历第一棵树的根结点的子树森林；
? （ 2）访问森林中第一棵树的根结点；
? （ 3）中序遍历除去第一棵树之后的森林。
6.6 赫夫曼树及其应用
6.6.1最优二叉树 (赫夫曼树 )
? 路径长度, 从树中一个结点到另一个结点之
间的分支构成这两个结点之间的路径,路径上的
分支数目称做路径长度 。
? 树的路径长度, 树的路径长度是从树根到每一
结点的路径长度之和 。
? 树的带权路径长度, 树的带权路径长度为树中
所有叶子结点 (k)的带权路径长度 ωkιk之和,
? 通常记作,n
? WPL= ∑ωkιk。
? k=1
最优二叉树
或赫夫曼 (Huffman)树的定义
? 假设有 n个权值 {ω 1,ω 2,…,ω n},试构造一
棵有 n个叶子结点的二叉树,每个叶子结点带权
为 ω i,则其中：
? 带权路径长度 WPL最小的二叉树称做
? 最优二叉树
? 或 赫夫曼树,
例 1：下面三棵二叉树的四个叶子
结点 a,b,c,d的权值为 7,5,2,4
a b c d
7 5 2 4
a b
c
d
7 5
2
4
c d
a
b
7
5
2 4
(a)WPL=7x2+5x2+2x2+4x2 = 36
(b)WPL=7x3+5x3+2x1+4x2 = 46
(c)WPL=7x1+5x2+2x2+4x2 = 35
例 2 最佳判定方法 (p.144)
(a)WPL=10x4+30x4+40x3+15x2+5x1=315
(b)WPL=5x3+15x3+40x2+30x2+10x2=220
10
c <90
e
d
5
15
40
b a
30
<60
<70
<80
N
N
N
N
Y
Y
Y
Y
10
<70 <90
e
c
5
40
15
b a
30
<60
d
<80
N
N
N
N
Y
Y
Y
Y
构造赫夫曼树的算法思想
? (1) 根据给定的 n个权值 {w1,w2,…,wn}构成 n棵二叉树的
集合 F={T1,T2,…,Tn}其中每棵二叉树 Ti中只有一个带权为
Wi的根结点,其左右子树均空,
? (2) 在 F中选取两棵根结点的权值最小的树作为左右子树
构造一棵新的二叉树,且置新的二叉树的根结点的权值为
其左,右子树根结点的权值之和,
? (3) 在 F中删除这两棵树,同时将新得到的二叉树加入 F中,
? (4) 重复 (2)和 (3),直到 F只含一棵树为止,这棵树便是赫夫
曼树,
构造赫夫曼树举例
c d
a
b
7
5
2 4
a b c
2
d
457
a b
c
6
d
57
a
b
c d
117
6.6.2 赫夫曼编码
赫夫曼树中没有度为 1的结点 ---严格的二叉树
? //-----夫曼树和赫夫曼编码的存储表示 -------
? typedef struct{
? unsigned int weight;
? unsigned int parent,lchild,rchild;
? }HTNode,*HuffmanTree;
? //动态分配数组存储赫夫曼树
? typedef char **HuffmanCode;
? //动态分配数组存储赫夫曼编码表
求赫夫曼编码的算法如下,
? Void HuffmanCoding(HuffmanTree *HT,HuffmanCode
*HC,int *w,int n){
? //w存放 n个字符的权值 (均 >0),构造赫夫曼树 HT,并求出 n个
字符的赫夫曼编码 HC.
? if(n<=1) return;
? m=2*n-1;
? HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
//0号单未用
? for(p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0};
? for(;i<=m;++i,++p) *p={0,0,0,0};
求赫夫曼编码的算法 （ 续一 ）,
? for(i=n+1;i<=m;++i){ //建赫夫曼树
? //在 HT[1..i-1]选择 parent为 0且 weight最小的两个结点,
? // 其序号分别为 s1和 s2.
? select(HT,i-1,s1,s2);
? HT[s1].parent=i;HT[s2].parent=i;
? HT[i].lchild=s1;HT[i].rchild=s2;
? HT[i].weight=HT[s1].weight+HT[s2].weight;
? }
? //-----从叶子到根逆向求每个字符的赫夫曼编码 -----
? Hc=(HffmanCode)malloc((n+1*sizeof(char *));
//分配 n个字符编码的头指针向量
? cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
? cd[n-1]="/0"; //编码结束符,
求赫夫曼编码的算法 （ 续二 ）,
? for(i=1;i<=n;++i){ //逐个字符求赫夫曼编码
? start=n-1; //编码结束符位置
? for(c=i,f=HT[i];f!=0;c=f,f=Ht[f].parent)
? //从叶子至根逆向求编码
? if(HT[f].lchild==c) cd[--start]="0";
? else cd[--start]="1";
? Hc[i]=(char *)malloc((n-start)*sizeof(char));
? //为第 i个字符编码分配空间
? strcpy(HC[i],&cd[start]); //从 cd复制编码 (串 )到 HC
? }
? free(cd); //释放工作空间
? }//HuffanCoding
求赫夫曼编码的算法如下,
? //----------无栈非递归遍历赫夫曼树,求赫夫曼编码
? HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
? p=m;cdlen=0;
? for(i=1;i<=m;++i)
? HT[i].weight=0; //遍历赫夫曼树时用作结点状态标志
? while(p){
? if(HT[p].weight==o){ //向左
? Ht[p].weight=1;
? if(HT[p.lchild!=0){p=HT[p].lchild;cd[cdlen++]="0";}
? else if(HT[p].rchild==0){//登记叶子结点的字符的编码
? HC[p]=(char *)malloc((cdlen+1) *sizeof(char));
? cd[cdlen]="\0";strcpy(HC[p],cd);//复制编码 (串 )
? }
? }
无 栈 非 递 归 遍 历 赫 夫 曼 树,
求赫夫曼编码
? else if (HT[p].weight==1){ //向右
? HT[p].weight=2;
? if (HT[p].rchild!=0){p=HT[p].rchild;
cd[cdlen++]="1";}
? }else{ //HT[p].weight==2,退回
? HT[p].weight=0;p=HT[p].parent;--cdlen;
? //退到父结点,编码长度减 1
? }//else
? }//while
例 6-2 八种字符,其频率分别为,
0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11
5 0 0 0
29 0 0 0
7 0 0 0
8 0 0 0
14 0 0 0
23 0 0 0
3 0 0 0
11 0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
HT.weight parent lchild rchild
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 9 0 0
29 14 0 0
7 10 0 0
8 10 0 0
14 12 0 0
23 13 0 0
3 9 0 0
11 11 0 0
8 11 1 7
15 12 3 4
19 13 8 9
29 14 5 10
42 15 6 11
58 15 2 12
100 0 13 14
HT.weight parent lchild rchild
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 3
23
11
1
7 8
29
14
0
0
0
0
0
0
0
1
1
1
1
1
1
0 1 1 01
2
3
4
5
6
7
8
1 0
1 1 1 0
1 1 1 1
1 1 0
0 0
0 1 1 1
0 1 0
HC
6.8 树的计数
? 称二叉树 T和 T'相似是指,二者都为空树或者
二者均不为空树,且它们的左右子树分别相似,
? 称二叉树 T和 T‘等价是指,二者不仅相似, 而
且所有对应结点上的数据元素均相同,
? 对给定的二叉树,其先序遍历, 中序遍历和
后序遍历都是唯一的 。 反过来是否唯一呢？
? 结论是任意两个遍历确定后, 这棵二叉树
也就唯一确定了 。
例 6-5 已知结点的前序序列和中序
序列，求整棵二叉树。
?前序序列,A B C D E F G
?中序序列,C B E D A F G
A
C
B
E
D
F
G
A
B
C D
E
F
G
A
B
C
F
D
E
G
实验与习题
理论习题 6.19,6.20,6.22,6.23 6.26,6.28,6.29,6.37
实验算法题, 6.38
6.4.1树的存储结构
一、双亲表示法（顺序存储）
//-----------树的双亲表存储表示 ----------//
#define MAX_TREE_SIZE 100
typedef struct PTNode {
TElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n; //结点数
}PTree;
双亲表示法举例
R
A
D E F
CB
G KH
R -1
A 0
B 0
C 0
D 1
E 1
F 3
G 6
H 6
K 6
0
1
2
3
4
5
6
7
8
9
数组下标,
* 便于涉及双亲的操作；
* 求结点的孩子时需要遍历整棵树。
6.4.1树的存储结构
二、孩子表示法 （顺序存储）
#define MAX_TREE_SIZE 100
typedef struct PTNode {
TElemType data;
int child1; //第 1个孩子 位置域
int child2; //第 2个孩子 位置域
......
int childd; //第 d个孩子 位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n; //结点数
}PTree;
孩子表示法举例
R
A
D E F
CB
G KH
0
1
2
3
4
5
6
7
8
9
数组下标,
* 便于涉及孩子的操作；求双亲不方便；
* 采用同构的结点，空间浪费。
R 1
A 4
B 0
C 6
D 0
E 0
F 7
G 0
H 0
K 0
2 3
5 0
0 0
0 0
0 0
0 0
8 9
0 0
0 0
0 0
孩子链表存储表示 （链式存储）
typedef struct CTNode{ //孩子结点
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct {
TElemType data;
ChildPtr firstchild; //孩子链表头指针
}CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n,r; //结点数和根的位置
}CTree;
孩子链表存储表示 举例
R
A
D E F
CB
G KH
0
1
2
3
4
5
6
7
8
9
数组下标,
* 便于涉及孩子的操作；
* 求结点的双亲时不方便。
R
A
B /
C
D /
E /
F
G /
H /
K /
1 2 3 /
4 5 /
6 /
7 8 9 /
T.nodes[ ]; T.n=10; T.r = 0;
例 1,设树 T以孩子链表为存储结构,
寻找值为 x的双亲结点的算法如下,
Status parent(Ctree T,TElemType x)
{// 当值为 x的结点不存在时返回 -2;
// 当值为 x的结点为根结点时返回 -1,
// 否则返回 x结点的双亲结点的下标值,
if(T.nodes[T.r].data == x) return –1;
//值为 x的结点为根结点 ;
for(i=0;i<T.n;i++)
{ p=T.nodes[i].firstchild;
while(p && T.nodes[p->child].data != x)
p = p->next;
if(p) return (i); // 找到 x的双亲结点
}
return –2; // 值为 x的结点不存在
}
例 2,删除值为 x的结点的第 i棵子树的
算法 delete如下：
void deletej(Ctree &T,int j)
{// 删除树 T的第 j号结点及其子树
if(!T.nodes[j].firstchild){ // 删除叶结点
for(i=j; i<T.n-1; i++) { // j号结点后的结点全部前移一位
T.nodes[i].data = T.nodes[i+1].data;
T.nodes[i].firstchild = T.nodes[i+1].firstchild;
}
T.n--;
}else{
while(s=T.nodes[j].firstchild){
T.nodes[j].firstchild = s->next;
i = s->child;
free(s);
deletej(T,i); // 递归删除第 i号结点及其子树
}
}
}
Status delete(Ctree &T,TElemType x,int i)
{ // 当值为 x的结点不存在时返回 -2;当值为 x的结点为
//叶结点或无第 i 棵子树时返回 -1,否则返回 1.
for(k=0; k<T.n; k++)
if(T.nodes[k].data == x) break; // 找到值为 x的结点
if(k>=T.n) return –2; // 值为 x的结点不存在
p= T.nodes[k].firstchild;
j = 1;
if(!p) return –1; // x结点为叶结点
if(i==1){ // 删除长子时,特殊处理
j =p->child; // 记住要删除子树的下标
T.nodes[k].firstchild = p->next;
free(p);
}else{
while(p->next && j<i-1){p = p->next ; j++;}
if(j>i-1 || !p->next) return –1; // 无第 i 棵子树
// p指向第 i-1 个儿子
j = p->next->child; // 记住要删除子树的下标
s = p->next; p->next = s->next; free(s);
}
deletej(T,j); // 递归删除第 j号结点及其子树
return 1;
}
三,孩子兄弟表示法
---树的二叉树表示法 (二叉链表示法 )
? //-----树的二叉链表 (孩子兄弟 )存储表示 ------
typedef struct CSNode {
ELemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
R
A
D E F
CB
G KH
R ?
A
?D
E ?? C ?
H?
F ?
G?
B?
K? ?
孩子兄弟表示法示例：
6.4.2 森林与二叉树的转换
一,森林转换成二叉树
? 如果 F={T1,T2,…,Tm}是森林,则可按如下规则
转换成一棵二叉树 B=(root,LB,RB)。
? (1)若 F为空, 即 m=0,则 B为空树；
? (2)若 F非空, 即 m<>0,则 B的根 root即为森林
中第一棵树的根 ROOT(T1)；
? B的左子树 LB是从 T1中根结点的子树森林
F1={T11,T12,…,T1m1}转换而成的二叉树 ;
? 其右子对 RB是从森林 F'={T2,T3,…,Tm} 转换
而成的二叉树,
二, 二叉树转换成森林
? 如果 B=(root,LB,RB)是一棵二叉树,则可按如下规
则转换成森林 F={T1,T2,…,Tm}：
? (1)若 B为空, 则 F为空；
? (2)若 B非空, 则 F中第一棵树 T1的根 ROOT(T1)
即为二叉树 B的根 root；
? T1中的根结点的子树森林 F1是由 B的左子树
LB转换而成的森林 ;
? F中除 T1之外其余树组成的森林 F'={T2,T3,…,
Tm}是由 B的右子树 RB转换而成的森林 。
6.4.3 树和森林的遍历
? 树的两种遍历方法：
? 一, 先根遍历：
? （ 1） 访问树的根结点；
? （ 2） 依次先根遍历每棵子树 。
? R A D E B C F G H K
? 二、后根遍历：
? （ 1）依次后根遍历每棵子树。
? （ 2）访问树的根结点；
? D E A B G H K F C R
R
A
D E F
CB
G KH
森林的两种遍历方法：
? 一, 先序遍历森林：
? 若森林非空, 则
? （ 1） 访问森林中第一棵树的根结点；
? （ 2） 先序遍历第一棵树的根结点的子树森林；
? （ 3） 先序遍历除去第一棵树之后的森林 。
? 二、中序遍历森林：
? 若森林非空，则
? （ 1）中序遍历第一棵树的根结点的子树森林；
? （ 2）访问森林中第一棵树的根结点；
? （ 3）中序遍历除去第一棵树之后的森林。
6.6 赫夫曼树及其应用
6.6.1最优二叉树 (赫夫曼树 )
? 路径长度, 从树中一个结点到另一个结点之
间的分支构成这两个结点之间的路径,路径上的
分支数目称做路径长度 。
? 树的路径长度, 树的路径长度是从树根到每一
结点的路径长度之和 。
? 树的带权路径长度, 树的带权路径长度为树中
所有叶子结点 (k)的带权路径长度 ωkιk之和,
? 通常记作,n
? WPL= ∑ωkιk。
? k=1
最优二叉树
或赫夫曼 (Huffman)树的定义
? 假设有 n个权值 {ω 1,ω 2,…,ω n},试构造一
棵有 n个叶子结点的二叉树,每个叶子结点带权
为 ω i,则其中：
? 带权路径长度 WPL最小的二叉树称做
? 最优二叉树
? 或 赫夫曼树,
例 1：下面三棵二叉树的四个叶子
结点 a,b,c,d的权值为 7,5,2,4
a b c d
7 5 2 4
a b
c
d
7 5
2
4
c d
a
b
7
5
2 4
(a)WPL=7x2+5x2+2x2+4x2 = 36
(b)WPL=7x3+5x3+2x1+4x2 = 46
(c)WPL=7x1+5x2+2x2+4x2 = 35
例 2 最佳判定方法 (p.144)
(a)WPL=10x4+30x4+40x3+15x2+5x1=315
(b)WPL=5x3+15x3+40x2+30x2+10x2=220
10
c <90
e
d
5
15
40
b a
30
<60
<70
<80
N
N
N
N
Y
Y
Y
Y
10
<70 <90
e
c
5
40
15
b a
30
<60
d
<80
N
N
N
N
Y
Y
Y
Y
构造赫夫曼树的算法思想
? (1) 根据给定的 n个权值 {w1,w2,…,wn}构成 n棵二叉树的
集合 F={T1,T2,…,Tn}其中每棵二叉树 Ti中只有一个带权为
Wi的根结点,其左右子树均空,
? (2) 在 F中选取两棵根结点的权值最小的树作为左右子树
构造一棵新的二叉树,且置新的二叉树的根结点的权值为
其左,右子树根结点的权值之和,
? (3) 在 F中删除这两棵树,同时将新得到的二叉树加入 F中,
? (4) 重复 (2)和 (3),直到 F只含一棵树为止,这棵树便是赫夫
曼树,
构造赫夫曼树举例
c d
a
b
7
5
2 4
a b c
2
d
457
a b
c
6
d
57
a
b
c d
117
6.6.2 赫夫曼编码
赫夫曼树中没有度为 1的结点 ---严格的二叉树
? //-----夫曼树和赫夫曼编码的存储表示 -------
? typedef struct{
? unsigned int weight;
? unsigned int parent,lchild,rchild;
? }HTNode,*HuffmanTree;
? //动态分配数组存储赫夫曼树
? typedef char **HuffmanCode;
? //动态分配数组存储赫夫曼编码表
求赫夫曼编码的算法如下,
? Void HuffmanCoding(HuffmanTree *HT,HuffmanCode
*HC,int *w,int n){
? //w存放 n个字符的权值 (均 >0),构造赫夫曼树 HT,并求出 n个
字符的赫夫曼编码 HC.
? if(n<=1) return;
? m=2*n-1;
? HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
//0号单未用
? for(p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0};
? for(;i<=m;++i,++p) *p={0,0,0,0};
求赫夫曼编码的算法 （ 续一 ）,
? for(i=n+1;i<=m;++i){ //建赫夫曼树
? //在 HT[1..i-1]选择 parent为 0且 weight最小的两个结点,
? // 其序号分别为 s1和 s2.
? select(HT,i-1,s1,s2);
? HT[s1].parent=i;HT[s2].parent=i;
? HT[i].lchild=s1;HT[i].rchild=s2;
? HT[i].weight=HT[s1].weight+HT[s2].weight;
? }
? //-----从叶子到根逆向求每个字符的赫夫曼编码 -----
? Hc=(HffmanCode)malloc((n+1*sizeof(char *));
//分配 n个字符编码的头指针向量
? cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
? cd[n-1]="/0"; //编码结束符,
求赫夫曼编码的算法 （ 续二 ）,
? for(i=1;i<=n;++i){ //逐个字符求赫夫曼编码
? start=n-1; //编码结束符位置
? for(c=i,f=HT[i];f!=0;c=f,f=Ht[f].parent)
? //从叶子至根逆向求编码
? if(HT[f].lchild==c) cd[--start]="0";
? else cd[--start]="1";
? Hc[i]=(char *)malloc((n-start)*sizeof(char));
? //为第 i个字符编码分配空间
? strcpy(HC[i],&cd[start]); //从 cd复制编码 (串 )到 HC
? }
? free(cd); //释放工作空间
? }//HuffanCoding
求赫夫曼编码的算法如下,
? //----------无栈非递归遍历赫夫曼树,求赫夫曼编码
? HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
? p=m;cdlen=0;
? for(i=1;i<=m;++i)
? HT[i].weight=0; //遍历赫夫曼树时用作结点状态标志
? while(p){
? if(HT[p].weight==o){ //向左
? Ht[p].weight=1;
? if(HT[p.lchild!=0){p=HT[p].lchild;cd[cdlen++]="0";}
? else if(HT[p].rchild==0){//登记叶子结点的字符的编码
? HC[p]=(char *)malloc((cdlen+1) *sizeof(char));
? cd[cdlen]="\0";strcpy(HC[p],cd);//复制编码 (串 )
? }
? }
无 栈 非 递 归 遍 历 赫 夫 曼 树,
求赫夫曼编码
? else if (HT[p].weight==1){ //向右
? HT[p].weight=2;
? if (HT[p].rchild!=0){p=HT[p].rchild;
cd[cdlen++]="1";}
? }else{ //HT[p].weight==2,退回
? HT[p].weight=0;p=HT[p].parent;--cdlen;
? //退到父结点,编码长度减 1
? }//else
? }//while
例 6-2 八种字符,其频率分别为,
0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11
5 0 0 0
29 0 0 0
7 0 0 0
8 0 0 0
14 0 0 0
23 0 0 0
3 0 0 0
11 0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
HT.weight parent lchild rchild
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 9 0 0
29 14 0 0
7 10 0 0
8 10 0 0
14 12 0 0
23 13 0 0
3 9 0 0
11 11 0 0
8 11 1 7
15 12 3 4
19 13 8 9
29 14 5 10
42 15 6 11
58 15 2 12
100 0 13 14
HT.weight parent lchild rchild
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 3
23
11
1
7 8
29
14
0
0
0
0
0
0
0
1
1
1
1
1
1
0 1 1 01
2
3
4
5
6
7
8
1 0
1 1 1 0
1 1 1 1
1 1 0
0 0
0 1 1 1
0 1 0
HC
6.8 树的计数
? 称二叉树 T和 T'相似是指,二者都为空树或者
二者均不为空树,且它们的左右子树分别相似,
? 称二叉树 T和 T‘等价是指,二者不仅相似, 而
且所有对应结点上的数据元素均相同,
? 对给定的二叉树,其先序遍历, 中序遍历和
后序遍历都是唯一的 。 反过来是否唯一呢？
? 结论是任意两个遍历确定后, 这棵二叉树
也就唯一确定了 。
例 6-5 已知结点的前序序列和中序
序列，求整棵二叉树。
?前序序列,A B C D E F G
?中序序列,C B E D A F G
A
C
B
E
D
F
G
A
B
C D
E
F
G
A
B
C
F
D
E
G
实验与习题
理论习题 6.19,6.20,6.22,6.23 6.26,6.28,6.29,6.37
实验算法题, 6.38
