数据结构与算法 课件 第6章 树和二叉树

第6章树和二叉树线性结构与非线性结构线性表、栈和队列等数据结构都属于线性结构，其元素间的逻辑关系都呈现一对一的关系。树结构和图结构属于非线性结构，其元素间的逻辑关系分别呈现一对多和多对多的关系。树的元素之间存在明显的分支和层次关系。它在客观世界中大量存在，例如人类社会的家谱、各种社会组织结构、计算机操作系统的多级目录等。1【本章重点】①树和二叉树的定义；②二叉树的性质；③二叉树和树的存储表示；④二叉树的遍历和遍历算法的应用；⑤树、森林与二叉树之间的转换；⑥哈夫曼树及应用。2【本章难点】①二叉树深度优先非递归遍历算法；②基于二叉树深度优先递归遍历实现二叉树的其他操作；③线索二叉树。3【本章内容】树的基本概念二叉树二叉树的遍历线索二叉树树和森林哈夫曼树及其应用习题646.1树的基本概念树的定义（递归定义）：树（Tree）是n（n≥0）个结点的有限集合T，满足两个条件：（1）有且仅有一个特定的称为根（Root）的结点，它没有前驱；（2）其余的结点可分成m个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为根的子树。当n=0时的空集合定义为空树。5关于树的基本术语:结点：指树中的一个元素，包含数据项及若干指向其子树的分支。结点的度：指结点拥有的子树个数。树的度：指树中最大结点度数。叶子：指度为零的结点，又称为终端结点。孩子：一个结点的子树的根称为该结点的孩子。双亲：一个结点的直接上层结点称为该结点的双亲。兄弟：同一双亲的孩子互称为兄弟。结点的层次：从根结点开始，根结点为第一层，根的孩子为第二层，根的孩子的孩子为第三层，依次类推。66.1树的基本概念6.1树的基本概念树的深度：树中结点的最大层次数。

堂兄弟：双亲在同一层上的结点互称为堂兄弟。路径：若存在一个结点序列k1,k2,…,kj,可使k1到达kj,则称这个结点序列是k1到达kj的一条路径。子孙和祖先：若存在k1到kj的一条路径k1,k2,…,kj，则k1,…,kj-1为kj的祖先，而k2,…,kj为k1的子孙。森林：m(m≥0)棵互不相交的树的集合构成森林。有序树和无序树：若将树中每个结点的各个子树都看成是从左到右有次序的（即不能互换），则称该树为有序树，否则为无序树。7树的存储结构（1）顺序存储顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。（2）链式存储链式存储时，使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。86.2二叉树二叉树定义（递归定义）：

二叉树是n（n≥0）个结点的有限集，它或为空树（n=0），或由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树构成。二叉树的五种基本形态：二叉树与度为2的树的区别：二叉树的子树有左右之分，而树的子树不分左右。9性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。证明：可用数学归纳法予以证明。

当i=1时，有2i-1=20=1，同时第一层上只有一个根结点，故命题成立。

设当i=k时成立，即第k层上至多有2k-1个结点。

当i=k+1时，由于二叉树的每个结点至多有两个孩子，所以第k+1层上至多有2

2k-1=2k个结点，故命题成立。10二叉树的性质二叉树的性质性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。证明：性质1给出了二叉树每一层中含有的最大结点数，深度为k的二叉树的结点总数至多为

故命题成立。11二叉树的性质在讲性质3之前，我们先了解什么是满二叉树和完全二叉树。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

满二叉树的特点是每一层的结点数都达到该层可具有的最大结点数。如果一个深度为k的二叉树，它的结点按照从根结点开始，自上而下，从左至右进行连续编号后，得到的顺序与满二叉树相应结点编号顺序一致，则称这个二叉树为完全二叉树。完全二叉树的1~k-1层上共有2k-1-1个结点，第k层的结点集中在左边。满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。12二叉树的性质性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设度为1的结点数为n1，则一棵二叉树的结点总数为：n=n0+n1+n2

因为除根结点外，其余结点都有一个进入的分支(边)，设B为分支总数，则n=B+1。又考虑到分支是由度为1和2的结点发出的，故有

B=2n2+n1，即n=2n2+n1+1

比较两式可得n0=n2+1，证毕。

13二叉树的性质性质4：具有n个结点的完全二叉树的深度为

log2n

+1或

log2(n+1)

。

其中，

x

表示不大于x的最大整数，

x

表示不小于x的最小整数。证明：设完全二叉树的深度为k，则有

2k-1-1<n2k–1

2k-1

n<2k

取对数k-1log2n<k

因为k为整数，所以k=log2n

+114二叉树的性质性质5：如果将一棵有n个结点的完全二叉树的结点按层序(自顶向下，同一层自左向右）连续编号1,2,…,n，第i个结点(1≤i≤n)具有以下关系：若i=1，则结点i是二叉树的根结点，无双亲；若i>1，则结点i的双亲为结点

i/2

若2*i≤n，则结点i的左孩子为2*i，否则无左孩子若2*i+1≤n，则结点i的右孩子为2*i+1，否则无右孩子若i为偶数，且i!=n，则其右兄弟为i+1若i为奇数，且i!=1，则其左兄弟为i-1结点i所在层次为

log2i

+11516与二叉树性质相关的几个例题【例1】若一棵二叉树的叶子数为n，在该二叉树中左、右指针域皆非空的结点个数为________。【例2】任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度为1的结点为________个。【例3】深度为6的二叉树最多有________个结点。根据性质3分析：n0=m，n2=n0-1=m-1度为1的结点个数：n-m-(m-1)=n-2m+1根据性质2分析：2k-1深度为6的二叉树最多的结点个数：26-1=63根据性质3分析：n0=n，n2=n0-1=n-1

子树皆非空（度为2）的结点个数为n-1。17【例4】具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号是__（1）__，编号最小的分支结点序号是__（2）__，编号最大的叶子结点序号是__（3）_，编号最小的叶子结点序号是__（4）__。

根据性质5分析：（1）编号最大的分支结点序号是

n/2

（2）编号最小的分支结点的序号是1（3）编号最大的叶子结点序号是n（4）编号最小的叶子结点序号是

n/2+118【例5】将含有83个结点的完全二叉树从根结点开始编号，根结点的编号为1，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为______。【例6】设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少______个。【例7】深度为5的完全二叉树最多有______个结点，最少有______个结点。根据性质5分析，编号为41的双亲结点编号为：

41/2=20根据性质2分析，1~k-1层为满二叉树，含有2k-1-1个结点，由于只有度为0和度为2的结点，所以第k层上至少有两个结点，二叉树上所含结点总数最少有2k-1+1个。根据性质2分析，最多有25-1=31个结点，最少有24-1+1=16个结点。19【例8】如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1≤i≤n)的结点X有：若i=1,则结点X是__（1）__；若i>1,则X的双亲PARENT(X)的编号为__（2）__。若2i>n，则结点X无__（3）__且无__（4）__；否则，X的左孩子LCHILD(X)的编号为__（5）__。若2i+1>n，则结点X无__（6）__；否则，X的右孩子RCHILD(X)的编号为__（7）__。根据性质5分析：（1）根结点 （2）

i/2

（3）左孩子 （4）右兄弟（5）2i （6）右孩子 （7）2i+1二叉树的存储结构（1）顺序存储结构①存储一棵完全二叉树根据二叉树性质5，在一棵完全二叉树中，按照从根结点起，自上而下，从左至右的方式对结点进行顺序编号，便可得到一个反映结点之间关系的线性序列。完全二叉树的顺序存储结构：20②存储一般二叉树为了能够通过下标反映出结点之间的关系，必须通过增加虚结点的方法，将二叉树映射为完全二叉树。然后按照完全二叉树进行存储。21二叉树顺序存储结构的类型定义#definemaxsize1024;typedefchardatatype;typedefstruct{ datatypedata[maxsize];//存放二叉树的向量

intlast;//最后一个结点的下标}sequenlist;根据性质2，采用顺序存储结构存储一棵深度为k的完全二叉树或一般二叉树，向量的长度是2k-1。22由于一般二叉树必须按照完全二叉树进行存储，可能会浪费很多存储空间。单支树就是一个极端的情况。例如存储一棵只有右分支的二叉树，所需的向量长度为25-1=31，其中存放了5个结点和26个虚结点。23（2）链式存储结构①二叉链表每个结点含有数据域和2个指针域，左、右指针域分别用来指向左孩子和右孩子。二叉树的链式存储结构通常采用二叉链表。

二叉链表结点的结构体类型定义：

typedefchardatatype；

typedefstructnode{

datatypedata；

structnode*lchild，*rchild；

}bitree；

bitree*root;

其中root是指向根结点的指针，当二叉树为空时，root为NULL值。若结点的某个孩子不存在时，该结点相应的指针域为NULL值。24【例】采用二叉链表存储二叉树。25

在二叉链表中，只能找到某个结点的后继结点，不能找到某个结点的前驱结点。

n个结点的二叉链表中，共有2n个指针域，其中n－1个指针域用于指示结点，其余n＋1个指针域必为空。②

三叉链表26每个结点含有数据域和3个指针域，左、右指针域分别用来指向左孩子和右孩子，双亲指针域指向直接前驱结点。二叉树的建立（建立二叉链表）算法的基本思想按照结点的序号，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。如此反复进行，直到输入结束标志“＃”为止。27算法实现时的考虑设置一个指针数组作为队列保存已输入结点的地址（虚结点的地址为空），队尾(rear)指向当前输入的结点，队头(front)指向这个结点的双亲结点。由于根结点的地址放在队列的第一个单元里，所以当rear为偶数时，则rear所指的结点应作为左孩子与其双亲链接，否则rear所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则无须链接。当一个双亲结点与两个孩子链接完毕，则进行出队操作，使队头指针指向下一个待链接的双亲结点。28二叉树的建立（建立二叉链表）算法bitree*CREATREE()//建立二叉树函数，函数返回指向根结点的指针{

charch;//结点信息变量

bitree*Q[maxsize];//设置指针类型数组来构成队列

int front,rear;//队头和队尾指针变量

bitree*root,*s;//根结点指针和中间指针变量

root=NULL;//二叉树置空

front=1;//设置队列指针变量初值

rear=0;

//以上为初始化

29

while((ch=getchar())!='#')//输入一个字符，当不是结束符时执行以下操作

{s=NULL;

if(ch!='@')//@表示虚结点。若不是虚结点，则建立新结点

{ s=(bitree*)malloc(sizeof(bitree));

s->data=ch;

s->lchild=NULL;

s->rchild=NULL;

}

rear++;

//队尾指针增1，指向新结点地址应存放的单元

Q[rear]=s;//将新结点地址入队或虚结点指针NULL入队30

if(rear==1)

root=s;//输入的第一个结点作为根结点

else

{

if(s&&Q[front])//孩子和双亲结点都不是虚结点

if(rear%2==0)

Q[front]->lchild=s;//rear为偶数，新结点是左孩子

else

Q[front]->rchild=s;//rear为奇数且不等于1，新结点是右孩子

if(rear%2==1)front++;//结点*Q[front]的两个孩子处理完毕，出队

}

}

returnroot;//返回根指针}316.3二叉树的遍历所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。遍历的结果：产生一个关于结点的线性序列。二叉树的遍历分为深度优先和广度优先，深度优先又分为递归和非递归两种。32（1）深度优先递归遍历访问根结点,记作D

遍历根的左子树,记作L

遍历根的右子树,记作R深度优先可能的遍历次序：先序DLR逆先序DRL

中序LDR逆中序RDL

后序LRD逆后序RLD33①先序遍历DLR先序遍历算法的遍历过程若二叉树非空，执行以下操作：访问根结点；先序遍历左子树；先序遍历右子树。voidpreorder(bitree*p)//先序遍历二叉树，p指向二叉树的根结点{if(p!=NULL)//二叉树p非空，则执行以下操作

{printf(“%c”,p->data);//访问p所指结点

preorder(p->lchild);//先序遍历左子树

preorder(p->rchild);//先序遍历右子树

}}34黑色箭头表示递归调用，红色箭头表示从左子树递归返回，蓝色箭头表示从右子树递归返回②中序遍历LDR中序遍历算法的遍历过程若二叉树非空，执行以下操作：中序遍历左子树；访问根结点；中序遍历右子树。voidinorder(bitree*p)//先序遍历二叉树，p指向二叉树的根结点{if(p!=NULL)//二叉树p非空，则执行以下操作

{inorder(p->lchild);//中序遍历左子树

printf(“%c”,p->data);//访问p所指结点

inorder(p->rchild);//中序遍历右子树

}}35③后序遍历LRD后序遍历算法的遍历过程若二叉树非空，执行以下操作：后序遍历左子树；后序遍历右子树；访问根结点。voidpostorder(bitree*p)//后序遍历二叉树，p指向二叉树的根结点{if(p!=NULL)//二叉树p非空，则执行以下操作

{postorder(p->lchild);//后序遍历左子树

postorder(p->rchild);//后序遍历右子树

printf(“%c”,p->data);//访问p所指结点

}}36（2）深度优先非递归遍历中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，根结点出栈并访问，再遍历右子树。voidinorder(BiTree*T){ SqStack*S; BiTree*p=T; InitStack(S);//顺序栈初始化

while(p!=NULL||!Empty(S))

{if(p!=NULL){Push(S,p);//根结点入栈

p=p->lchild;//遍历左子树}

else{Pop(S,p);//左子树遍历结束，出栈

printf(“%c”,p->data);//访问出栈的结点

p=p->rchild;//遍历右子树} }}37深度优先非递归遍历的过程38（3）二叉树的广度优先遍历（按层次遍历二叉树）从根开始逐层访问。先遍历二叉树的第一层结点，然后遍历第二层结点，……最后遍历最下层的结点。而对每一层的遍历按照从左至右的顺序进行。基本思想：

在上层中先被访问的结点，它的下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个队列。在遍历进行之前先把二叉树的根结点的存储地址入队，然后依次从队列中出队结点的存储地址，每出队一个结点的存储地址则对该结点进行访问，然后依次将该结点的左孩子和右孩子的存储地址入队，如此反复，直到队空为止。39二叉树的广度优先遍历算法voidlayer(BiTree*T){BiTree*p;SqQueue*Q;InitQueue(Q);//初始化队列

if(T!=NULL)

{Q->rear=(Q->rear+1)%MAXSIZE;//修改循环队列尾指针

Q->data[Q->rear]=T;//入队

while(Q->front!=Q->rear)//循环队列非空

{Q->front=(Q->front+1)%MAXSIZE;//修改队头指针

p=Q->data[Q->front];printf(“%c”,p->data);//出队，输出结点的元素值

if(p->lchild!=NULL)//出队结点的左子树非空

{Q->rear=(Q->rear+1)%MAXSIZE;

Q->data[Q->rear]=p->lchild;//左子树根结点入队

}

if(p->rchild!=NULL)//出队结点的右子树非空

{Q->rear=(Q->rear+1)%MAXSIZE;

Q->data[Q->rear]=p->rchild;//右子树根结点入队

}

}

}}40【例】二叉树的广度优先遍历输出序列为：A,B,C,D,E,F,G41（4）由遍历序列恢复二叉树由DLR和LDR的遍历序列可以唯一地确定一棵二叉树；由LRD和LDR的遍历序列可以唯一地确定一棵二叉树。通过DLR或者LRD的遍历序列确定二叉树或子树的根结点；通过LDR确定左、右子树的序列。42【例】由先序序列{ABHFDECKG}和中序序列{HBDFAEKCG}恢复二叉树的过程。43（5）深度优先递归算法的应用①统计二叉树的叶子结点数intcount=0;intcountleaf(bitree*p){ if(p!=NULL){

count=countleaf(p->lchild); //对左子树上的叶子结点计数

if((p->lchild==NULL)&&(p->rchild==NULL))

count=count+1;

count=countleaf(p->rchild);

//对右子树上的叶子结点计数

}

returncount;}请考虑如何统计度为1的结点个数，度为2的结点个数。44②利用二叉树后序遍历计算二叉树的深度intDepth(BiTree*T){ intdepL,depR; if(T!=NULL)

{ depL=Depth(T->lchild);//计算左子树的深度

depR=Depth(T->rchild);//计算右子树的深度

if(depL>=depR)return(depL+1); elsereturn(depR+1);

//二叉树的深度为左右子树深度较大者加一（根结点）

} elsereturn(0);}45③求二叉树结点个数intSize(BiTree*T){if(T==NULL)return(0);

elsereturn(1+Size(T->lchild)+Size(T->rchild));

//二叉树的结点个数是根结点、左右子树结点个数之和}46④交换左右子树voidExchange(BiTree*T){ BiTree*S; if(T!=NULL){S=T->lchild; T->lchild=T->rchild; T->rchild=S; Exchange(T->lchild);//在左子树中交换

Exchange(T->rchild);//在右子树中交换

}}47⑤利用先序遍历方法，以广义表（嵌套括号）的形式输出二叉树的层次结构。voidOutBT(BiTree*p){if(p!=NULL){ printf(“%c”,p->data); //输出根结点

if(p->lchild!=NULL||p->rchild!=NULL)//根结点有左子树或右子树

{ printf(“(”);

OutBT(p->lchild);//遍历左子树

if(p->rchild!=NULL)printf(“,”);

//有右子树输出逗号

OutBT(p->rchild);//遍历右子树

printf(“)”);

}}}486.4线索二叉树按照不同的遍历序列，可以得到先序、中序和后序线索二叉树。线索二叉树是将一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这些线性序列中有且仅有一个直接前趋和一个直接后继。线索是指向遍历序列中的结点前趋和后继的指针，若结点有左孩子，则lchild指示其左孩子，否则lchild指示该结点的直接前趋结点；若结点有右孩子，则rchild指示其右孩子，否则rchild指示该结点的直接后继结点。49线索二叉树及其线索链表的表示50标志域ltag、rtag：ltag=0,lchild为左孩子指针ltag=1,lchild为前趋线索指针rtag=0,rchild为右孩子指针rtag=1,rchild为后继线索指针线索二叉树的结点结构类型定义typedef结点的数据域类型datatype;typedefstructBiThrNode{datatypedata；

structBiThrNode*lchild,*rchild;//左、右指针域

intltag,rtag；//左、右标志域}BiThrNode；通过算法可以建立二叉树的先序、中序和后序线索二叉树。采用线索二叉树作为二叉树的存储结构，可以方便的查找某个结点在遍历序列中的前趋和后继。在先序和中序线索二叉树中查找后继结点比较简单；在后序和中序线索二叉树中查找前趋结点比较简单。516.5树和森林（1）树的存储结构①双亲表示法树的双亲表示法是用一组连续空间（向量）存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在向量中的位置。双亲表示法可以方便地查找结点的双亲或祖先，但是查找孩子结点或子孙时需要遍历整个树结构。5253

双亲表示法的结构类型定义#defineMAXSIZE100//

结点的最大数目typedefstruct//结点的结构{datatypedata；

intparent；//双亲位置域}PTNode；typedefstruct//树的结构{PTNodenodes[MAXSIZE]；//存储结点的向量

intn；//结点个数}PTree；54【例】采用双亲表示法存储树。55②孩子表示法

把所有结点以单链表形式储存，同时以每个结点作为头结点，对其孩子结点另建立一个孩子链表。则n个结点有n个孩子链表(叶子的孩子链表为空表)。孩子表示法可以方便地查找结点的孩子或子孙结点，但是查找双亲或祖先结点不方便。56

孩子表示法的结构类型定义typedefstructCTNode//孩子结点{intchild；

structCTNode*next；}*ChildPtr；typedefstruct{datatypedata；

ChildPtrchild；//孩子链表头指针

intparent;//双亲指针，在孩子双亲表示法中定义}CTBox；typedefstruct{CTBoxnodes[MAXSIZE]；

intn；//结点数}CTree；57【例】采用孩子表示法存储树。58③

孩子兄弟表示法

二叉链表中每个结点有两个指针域child域和next域，分别指向该结点的最左边的孩子结点和右邻兄弟结点。孩子兄弟表示法可以方便地查找结点的孩子和孩子的兄弟结点，但是不能查找双亲或祖先结点。孩子兄弟表示法的结构类型定义typedefstructCSNode{datatypedata；

structCSNode*child，*next；}CSNode，*CSTree；59【例】采用孩子兄弟表示法存储树。60（2）树、森林转换成二叉树树转换成二叉树①树T中结点N的第一个子结点N1在二叉树T’中是对应结点N的左孩子；②N1的兄弟在T’中被依次链接成一串开始于N1的右孩子。树转换成二叉树，二叉树的右子树一定为空。树转换成二叉树，实质上就是树的孩子兄弟表示法。61

森林转换成二叉树①把每一棵树依次换换成二叉树；②合并二叉树，把第二棵二叉树作为第一棵二叉树的右子树，第三棵二叉树作为第二棵二叉树的右子树，……。即将第2，3，……棵二叉树串接在第1棵二叉树的右分支上。62

二叉树转为树①将二叉树T’中结点x的右孩子，右孩子的右孩子…，都与x的双亲结点Y用线相连；②去掉原有的双亲到右孩子的连线，得到树T。63

二叉树转为森林①从二叉树的根结点开始，将右指针断开，分解二叉树，使第一棵二叉树的右子树为空，不断重复着一过程，直到所有二叉树的右子树均为空；②将每棵二叉树分别转换为树，成为森林。646.6哈夫曼树及其应用（1）最优二叉树（哈夫曼树）路径长度

两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。具有不同路径长度的二叉树(a)PL=0+1*2+2*4+3=13(b)PL=0+1*2+2*3+3*2=1465

带权路径长度

树的带权路径长度是树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和。

其中n为树中叶子结点的数目，wi为叶子结点i的权值，li为叶子结点i到根结点之间的路径长度。66

叶子结点的权值相同，具有不同带权路径长度的二叉树哈夫曼树带权路径长度最小的二叉树称为哈夫曼树（最优二叉树），例如（c）是哈夫曼树。在哈夫曼树中，权值越大的结点离根越近。67

哈夫曼树的不唯一性

权值为w1,w2,…,wn

的n个叶子结点构成哈夫曼树，可以有形态不同的多棵哈夫曼树。68

完全二叉树不一定是哈夫曼树

在叶子数和权值相同的二叉树中，完全二叉树不一定是哈夫曼树（最优二叉树）。69（2）哈夫曼树的构造由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵二叉树的森林F={T0,T1,T2,…,Tn-1}，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。重复以下步骤,直到F中仅剩下一棵二叉树为止：①在F中选取两棵根结点的权值最小和次最小的二叉树,分别作为左、右子树构造一棵新的二叉树。置新的二叉树根结点的权值为其左、右子树根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。70

哈夫曼树的构造过程说明：①一个有n个叶子结点的初始集合，要生成哈夫曼树共进行n-1次合并，产生n-1个新结点。②最终求得的哈夫曼树共有n+n-1=2n-1个结点，并且哈夫曼树中没有度为1的分支结点。③没有度为1的结点的二叉树又称为严格二叉树。71

哈夫曼树的存储结构＃definen16//叶子数目＃definem(2*n-1)//结点总数typedefchardatatype;typedefstruct{floatweight;//权值，设权值均大于零

datatypedata;intlchild,rchild,parent;//左、右孩子及双亲指针}hufmtree;hufmtreetree[m];//顺序表的每个结点为一个结构体。

72

哈夫曼树构造算法的基本思想

①对m=2n-1个结点初始化，将双亲域，左、右孩子域，权值，结点值置0②输入n个叶子结点的权值和结点值③进行n-1次合并，产生n-1个新结点：在i个结点中找出两个双亲域为0（没有被合并的结点）且权值最小的结点，p1指示权值最小的结点，p2指示权值次最小的结点；将两棵根结点权值最小的二叉树进行合并：

tree[p1].parent=i;//i为新结点，即新产生的双亲结点

tree[p2].parent=i;tree[i].lchild=p1;//新产生的双亲结点指向左、右子树的根结点

tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight;//新结点的权值是左、右子树根结点权值之和。73

构造哈夫曼树的结果数组下标lchilddataweightrchildparent00a70610b50520c20430d40442‘0’63551‘0’114660‘0’185-174

哈夫曼树的构造算法voidHUFFMAN(hufmtreetree[]){ inti,j,p1,p2;charch;

floatsmall1,small2,f;

for(i=0;i<m;i++)//对长度为2n-1的顺序表初始化

{ree[i].parent=0;tree[i].lchild=0;tree[i].rchild=0;

tree[i].weight=0.0;tree[i].data=‘0’;

}

for(i=0;i<n;i++)//输入n个叶子结点的权值和结点值

{scanf(“%f”,&f);tree[i].weight=f;scanf(“%c”,&ch);tree[i].data=ch;}75for(i=n;i<m;i++)//进行n-1次合并，产生n-1个新结点

{p1=p2=0;small1=small2=Maxval;//Maxval为足够大的值

for(j=0;j<=i-1;j++)

if(tree[j].parent==0)

if(tree[j].weight<small1)

{small2=small1;//改变最小权，次最小权及位置

small1=tree[j].weight;p2=p1;p1=j;

}elseif(tree[j].weight<small2)//改变次小权及位置

{small2=tree[j].weight;p2=j;}

tree[p1].parent=i;tree[p2].parent=i;//合并两个结点

tree[i].lchild=p1;tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight;}

}76（3）哈夫曼树的应用在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法，减少比较的次数。用于通讯和数据传送时的哈夫曼编码和哈夫曼译码，实现数据的压缩。最佳判定算法【例】编制一个将百分制转换成五级制的算法，要求平均比较次数尽可能少。各分数段分布情况如下：百分制0~5960~6970~7980~8990~100五级制不及格（E）及格

（D）中

（C）良

（B）优

（A）比例数0.050.150.40.30.177哈夫曼树判定流程10.40.60.30.30.150.150.050.1AEDBCs<80s<70s<90s<60EDCBA78②哈夫曼编码设给出一段报文：abaccda

字符集合是{a,b,c,d}，各个字符出现的频度(次数)是W＝{3,1,2,1}。若给每个字符以等长编码

a:00b:01c:10d:11

则总编码为00010010101100

长度为(3+1+2+1)*2=14若按各个字符出现的概率不同而给予不等长编码，有可能减少总编码长度。各字符出现的概率为{3/7,1/7,2/7,1/7}，化整为{3,1,2,1}。79

以{3,1,2,1}作为各叶子结点上的权值，建立哈夫曼树。左分支赋0，右分支赋1，得到哈夫曼编码(不等长编码)：a:0b

:110c:10d:111电文的编码：0110010101110（abaccda）电文的总编码长度：1*3+3*1+2*2+3*1=13。比等长编码短。

n个叶子结点的最大编码长度不会超过n-1。总编码长度正好等于哈夫曼树的路径长度，例如字符a、b、c、d的总编码长度为9，哈夫曼树的路径长度也是9。任一字符的编码都不是另一字符编码的前缀，称为前缀编码。哈夫曼编码是一种前缀编码，译码时不会混淆。80哈夫曼编码的数据结构typedefchardatatype;

typedefstruct

{charbits[n];//编码数组位串，其中n为叶子结点数目

intstart;//编码在位串的起始位置

datatypedata;//结点值

}codetype;

codetypecode[n];一个字符的哈夫曼编码在数组bits中从高位到低位顺序存储，数组code存储n个字符的哈夫曼编码。81哈夫曼编码算法的基本思想从叶子到根逆向求哈夫曼编码从叶子tree[i]出发，利用双亲地址找到双亲结点tree[p]，再利用tree[p]的lchild和rchild指针域判断tree[i]是tree[p]的左孩子还是右孩子，然后决定分配代码的‘0’还是‘1’,然后以tree[p]为出发点继续向上回溯，直到根结点为止。82哈夫曼编码算法voidHUFFMANCode(codetypecode[]，hufmtreetree[])//code存放求出的哈夫曼编码的数组，tree已知的哈夫曼树{inti,c,p;

codetypecd;//缓冲变量

for(i=0;i<n;