计算机软件及应用树和二叉树

目录第01章数据结构概论第02章线性表第03章栈第04章队列第05章串第06章数组、特殊矩阵和广义表第07章树和二叉树第08章图第09章查找第10章排序第11章文件第7章树和二叉树内容简介六、本章小结O、本章目标一、树二、二叉树及其遍历算法三、线索二叉树四、树和森林五、哈夫曼树第7章树和二叉树树的定义及相关术语二叉树的定义、存储结构和基本运算实现二叉树遍历二叉树与树和森林的相互转换哈夫曼树及应用目标第7章树和二叉树树形结构树的定义树的常用术语和基本概念树的表示方法树的基本运算树第7章树和二叉树树形结构：非线性结构

非线性结构：至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数据结构。树形结构用于描述层次结构的关系，如：人类的族谱、各种社会关系、各类分类编码；操作系统的文件系统、编译程序的语法树；Internet中的DNS（域名系统）第7章树和二叉树树是n(n>0)个结点的有限集合T，对于任意一棵非空树，满足：(1)有且仅有一个特定的称为根的结点，根结点无前驱；(2)当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集T1，T2，….，Tm，其中每个集合本身又是一棵树，称为根的子树。显然：上述树的定义是一个递归定义。树的定义第7章树和二叉树(1)树的根结点无前驱结点，除根结点之外的所有结点有且仅有一个前驱结点；(2)树中所有结点可以有零个或多个后继结点。树的特点第7章树和二叉树2、有关基本概念：结点的度：该结点所拥有的子树的数目。叶子结点：度为0的结点。分支结点：度不为0的结点。树的度：树中各结点的度的最大值子结点：某结点的子树的根，称为他的子结点。父结点：该结点称为其子树根的父结点。兄弟结点：具有同一父结点的子结点称为兄弟结点。结点的层次：根结点的层次为1，其他结点的层次等于其父结点的层次加1。树的深度：树中结点的最大层次。森林：是m(m>0)棵树的集合。

ABCDEFGHIJ

双亲、子女祖先、子孙兄弟、堂兄弟度（结点的度和树的度）分支结点、叶子结点开始结点、内部结点结点的层次、树的深度有序树、无序树森林25647813树的常用术语和基本概念第7章树和二叉树练习：写出树的叶子结点、非终端结点、各结点的度和树的深度第7章树和二叉树ABCDEFGHIJKMABEFGCDHIJKLMABEFGCDHIJKLM(A(B(E(K)(L))(F))(C(G))(D(H(M))(I)(J)))1A2B3E4K4L3F2C3G2D3H4M3I3J树的表示方法第7章树和二叉树树的存储结构——数组表示法利用二维数组的方式表示，Array[m,n]表示一棵m个结点、度为n的树数组的行数表示树中结点的数目，列数表示树中任意结点包含的最多的度，数组元素为当前结点的孩子结点相应的标号由于树中存在大量度小于n的结点，致使大量的数据元素的内容为空，当树的规模较大时浪费大量存储空间第7章树和二叉树分别将每个结点的孩子结点连成一个链表，然后将各表头指针放在一个表中构成一个整体结构。优点：便于搜索后代结点；缺点：搜索结点的祖先结点不便。树的存储结构——孩子链表表示法第7章树和二叉树ABCDEFGG6F5E4D3C2B1A0Datachildren123456孩子链表表示法图示第7章树和二叉树用数组T存放各个结点；每个结点信息包括两部分： 结点本身的值data和双亲结点在该表中的位置。structtnode{datatypedata;intparent;}structtnodetreelist[maxnum];优点：便于搜索相应结点的父结点及祖先结点；缺点：搜索结点的孩子结点及后代结点需要搜索整个表。树的存储结构——双亲表示法第7章树和二叉树ABCDEFGdataparent0071A02B13C14D15E36F37G3树的双亲表示法图示第7章树和二叉树ABCDEFG1.定长结点的多重链表所有结点都采用树的度作为结点中指针域的个数。2.不定长结点的多重链表每个结点采用自己的度作为结点中指针域的个数。树的存储结构——孩子表示法第7章树和二叉树ABCA^BC^^定长结点的多重链表图示第7章树和二叉树ABCABC不定长结点的多重链表图示第7章树和二叉树树的初始化：initial_tree(T)插入子树：insert_tree(T,S)插入兄弟结点：insert_sibling(T,S)查询根结点：rootof(T)查询父结点：fatherof(T)查询孩子结点：childof(T)查询兄弟结点：siblingof(T)树的基本运算第7章树和二叉树二叉树的定义二叉树的性质二叉树的存储遍历二叉树线索二叉树二叉树第7章树和二叉树定义：是由n(n>=0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2的结点；二叉树的子树有左子树和右子树之分，二叉树是有序树。BCDEA二叉树的定义第7章树和二叉树树二叉树1至少要有一个结点可为空集2子树次序通常不做规定两个子树有左、右之分3结点的度没有限制结点的度只能取0、1或2BCDEA25647813二叉树与树的区别——二叉树不是树的特例第7章树和二叉树空树只有一个根结点的二叉树只有左子树的二叉树只有右子树的二叉树左右子树非空的二叉树二叉树的五种形态思考：具有三个结点的二叉树有哪些形态？第7章树和二叉树1243567满二叉树：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。高度为k且有2k-1个结点的二叉树。特点：每一层上都有含有最大结点数。结点编号：从上到下，从左到右按自然数编号。满二叉树第7章树和二叉树123456高度为k，有n个结点的二叉树是一棵完全二叉树，当且仅当其每个结点都与高度为k的满二叉树中层次编号1--n相对应。123756完全二叉树第7章树和二叉树1)除最后一层外，每一层都取最大结点数，最后一层结点都集中在最左边的若干位置。2)叶子结点只可能在层次最大的两层出现。3)对任一结点，若其右分支下的子孙的最大层次为k，则其左分支下的子孙的最大层次为k或k+1。123456完全二叉树的特点第7章树和二叉树性质一：在二叉树的第i层上至多有2i-1个结点（i>=1)。(数学归纳法证明）当i=1时，只有一个根结点，2i-1=20=1,命题成立。假定当j=i时命题成立，即第i层上至多有2i-1个结点可以证明j＝i+1时命题也成立。由于二叉树每个结点的度最大为2，故在第i+1层上最大结点数为第i层上最大结点数的二倍，即2×2i-1＝2（i+1）-1。二叉树的性质第7章树和二叉树证明：深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和；由性质1得到第i层上的最大结点数为2i-1;20+21+22+…+2k-1=2k-1性质二：高度为k的二叉树中至多有2k-1个结点(k>=1)第7章树和二叉树证明：设：n1为二叉树T中度为1的结点数；因为：二叉树中所有结点的度均小于或等于2，所以：结点总数 n=n0+n1+n2(1)又因为：在二叉树中，除根结点外，其余结点都有一个分支进入，设B为分支总数，则有：

n=B+1(2)性质三：在任意一棵二叉树中，若其叶子结点数为n0,度为2的结点数为n2，则有：n0=n2+1。第7章树和二叉树又因为：这些分支是由度为1或2的结点射出的，所以： B=n1+2*n2(3)由（2）式和（3）式，得：

n=n1+2*n2+1（4）由（1）式和（4）式，得：

n0+n1+n2=n1+2*n2+1，立得：

n0=n2+1，即：二叉树中的叶子结点数=度为2的结点数+1。（证毕）第7章树和二叉树性质四：具有n个结点的完全二叉树的深度为不大于的最大整数。证明：设深度为k，根据二叉树性质二知：2k-1-1＜n≤2k-1，即：2k-1≤

n＜2k，于是有：证毕。完全二叉树的两个重要性质第7章树和二叉树(1)若i=1（根结点），则i无双亲；若i＞1，则i的双亲为(2)若i≤n/2，结点i的左孩子是结点2i；否则（即2i>n），若i＞n/2，则i无左孩子。(3)若i≤（n-1)/2，结点i的右孩子是结点2i+1；否则（即2i+1>n），结点i无右孩子。性质五：对有n个结点的完全二叉树的结点按层序编号（从上到下，自左到右）对任一结点i（1<=i<=n),有如下三个性质：第7章树和二叉树i+12i+22i+3i2i2i+1(b)i和i+1结点不在同一层……123456完全二叉树性质五的意义ii+12i2i+12i+22i+3(a)i和i+1结点在同一层第7章树和二叉树ii+115051100由分析知，编号为100的结点的父结点编号为50，从51到100均为叶子结点，共50个。思考：试用其他方法解决该问题。例：已知完全二叉树有100个结点，则该二叉树有多少个叶子结点？第7章树和二叉树因为：n0=20n1=10+15=25n2=n0–1=20–1=19所以：n=n0+n1+n2=20+25+19=64例：一棵二叉树有20个叶子结点，10个结点仅有左儿子，15个结点仅有右儿子，求则该二叉树有多少个结点？第7章树和二叉树用一组连续的存储单元存储二叉树的数据元素。存储要求：必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系用编号的方法：从树根起，自上层至下层，每层自左至右的给所有结点编号.二叉树的顺序存储结构第7章树和二叉树对于完全二叉树LKJIHGFEDCBA123456789101112abcdefghijkl第7章树和二叉树对于一般二叉树ABCDEFGØØØØØ

表示该处没有元素存在GFØØØØEDCBA第7章树和二叉树1.二叉链表：lchilddatarchild左子域右子域数据域2.三叉链表：lchilddatarchildparents双亲域左子域右子域数据域二叉树的链式存储结构第7章树和二叉树ABCDEFGH^F^AB^^CDE^^G^^H^图示-二叉链表法存储二叉树第7章树和二叉树ABEDCHG练习：画出二叉树对应的二叉链表第7章树和二叉树Typedefstructnode{intdata; /*数据域*/structnode*lchild,*rchild;/*左右孩子域*/

}；structnodeTREENODE;二叉链表的结点类型定义第7章树和二叉树采用顺序结构适用于完全、满二叉树，但对于一般二叉树则会浪费许多存储空间，并且在树中经常要插入和删除结点时，运算效率较低。用链表表示二叉树也会存在许多空链域（在含有n个结点的二叉链表中，共有2n个链域，实用n-1个链域，还有n+1个空链域），但在树中经常要插入和删除结点时，用链表表示二叉树运算效率较高。二叉树存储结构的选择第7章树和二叉树

遍历二叉树---即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历操作使非线性结构线性化。

二叉树三个基本组成单元：根结点、左子树和右子树bac(右子树)(左子树)(根结点)遍历二叉树第7章树和二叉树假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有六种遍历方案:DLR、LDR、LRD、DRL、RDL、RLD

若规定先左后右，则只有前三种情况：

DLR——先序遍历

LDR——中序遍历

LRD——后序遍历遍历二叉树顺序分析第7章树和二叉树若二叉树不空，则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。-＋*a/b-dcfe-+a*b–cd/ef1.先序遍历二叉树：先序遍历序列为：遍历二叉树的三种方式第7章树和二叉树Voidpreorder(treenode*t){if(t!=NULL){printf(“%c”,t–>data);preorder(t–>lchild);preorder(t–>rchild);}}二叉树的先序遍历算法第7章树和二叉树若二叉树不空则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。-＋*a/b-dcfea+b*c–d–e/f2.中序遍历二叉树：中序遍历序列为：第7章树和二叉树Voidinorder(treenode*t){if(t!=NULL){inorder(t–>lchild);printf(“%c”,t–>data);inorder(t–>rchild);}}二叉树的中序遍历算法第7章树和二叉树中序遍历递归算法递归函数的调用过程?BCAVoidinorder(A){if(p!=NULL){inorder(B);printf(A);inorder(null);}}Voidinorder(B){if(p!=NULL){inorder(null);printf(B);inorder(C);}}Voidinorder(null){if(p!=NULL){}}Voidinorder(null){if(p!=NULL){}}Voidinorder(C){if(p!=NULL){inorder(null);printf(C);inorder(null);}Voidinorder(null){if(p!=NULL){}}Voidinorder(null){if(p!=NULL){}}第7章树和二叉树中序遍历二叉树的非递归算法init(S);p=root;Do{

while(p!=NULL)

{

PUSH(S,p->data);p=p->lchild;}if(!EMPTY(S)){p=POP(S);Visit(p->data);p=p->rchild;}

}while(!EMPTY(S)||p!=NULL);BCDEA321

0CBA321

0BA321

0DA321

0A321

0E321

0CBDAE第7章树和二叉树若二叉树不空则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。-＋*a/b-dcfeabcd-*+ef/-3.后序遍历二叉树：后序遍历序列为：第7章树和二叉树Voidpostorder(treenode*t){if(t!=NULL){postorder(t–>lchild);postorder(t–>rchild);printf(“%c”,t–>data);}}二叉树的后序遍历算法第7章树和二叉树层次遍历是指：从二叉树的第一层开始，从上到下逐层遍历，同一层按从左到右的顺序对结点逐个访问。-＋*a/b-dcfe-+/a*efb–cd4.层次遍历：层次遍历序列为：第7章树和二叉树用队列q[M]存放当前访问结点首先为根结点先入队再每次从队首取一个结点，访问该结点并把它的孩子访问顺序入队。重复2，直到队空为止。按层次遍历树的思想第7章树和二叉树Voidccbls(JD*T){JD*p,q[M];intj,f=1,w=1;q[1]=T;While(f<=w){p=q[f++];printf(p->data);for(j=0;j<D;j++)If(p->ch[j]!=NULL)q[++w]=p->ch[j];}}ABCDEFH输出序列：ABCDEFHBCDfwA出队CDEFfwB出队EFHfwCD出队AfwA入队按层次遍历树的算法及其模拟实现第7章树和二叉树若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：？______________

按中序遍历,其中序序列为：？______________

按后序遍历,其后序序列为：？______________ABEDCHIKJGF示例–右图所示的二叉树第7章树和二叉树可恢复二叉树的结点序列组合：（1）先序序列和中序序列（2）中序序列和后序序列不可恢复二叉树的结点序列组合：先序序列和后序序列——只能确定根结点，不能划分左右子树由结点序列恢复二叉树第7章树和二叉树由先序序列和中序序列恢复二叉树（1）由先序序列得到二叉树的根结点；（2）由(1)得到的根结点把中序序列分为两个部分：左子树中序序列和右子树中序序列；（3）根据(2)得到的子树中序序列找到对应的左子树先序序列和右子树的先序序列；（4）重复(1)(2)(3)，直到所得左、右子树只含一个结点为止。第7章树和二叉树由结点序列恢复二叉树示例方法： 先序序列：ABCDEFGH（A是根） 中序序列：CBEDAGHF左子树右子树ABCDEFGH以A为根的左、右子树先序序列示意图：已知遍历二叉树的先序序列ABCDEFGH和中序序列CBEDAGHF，请画出该二叉树：第7章树和二叉树同理由右子树先序序列FGH和右子树中序序列GHF构造A的右子树：ABFCDEGHABFCDEGH由左子树先序序列BCDE和左子树中序序列CBED构造A的左子树第7章树和二叉树已知一棵二叉树：先序遍历二叉树的结点序列为：ABDECFG中序遍历二叉树的结点序列为：DBEAFGC要求画出该二叉树ABCDEFG练习第7章树和二叉树练习：已知一棵二叉树的中根序列和后根序列分别为BDCEAFGH和DECBHGFA，试画出二叉树。第7章树和二叉树ABFCGHDEVoidinorder(BNODE*T){if(T!=NULL){inorder(T–>lchild);

if(T->lchild!=null&&T->rchild!=null) printf(“%c”,T–>data);inorder(T–>rchild);}}二叉树遍历算法应用示例-设计算法，按照中序次序输出二叉树T中度为2的结点的数据值第7章树和二叉树Voidinorder(BNODE*T){if(T!=NULL){inorder(T–>lchild);

n++;inorder(T–>rchild);}}二叉树遍历算法应用示例-设计算法，求二叉树T的结点数第7章树和二叉树inthigh(BNODE*T){if(T==NULL)return0;elsereturnmax(high(T–>lchild),high(T–>rchild))+1;}二叉树遍历算法应用示例-设计算法，求二叉树T的高度第7章树和二叉树线索二叉树的定义线索二叉树的结构线索二叉树的基本运算线索二叉树第7章树和二叉树二叉树的遍历得到线性序列，这种先后关系是动态的，利用二叉链表的空指针域来保留这种前后关系有n个结点的二叉链表，共2n个指针域，其中n-1个非空，必有n+1个空链域利用空链域存储指向该结点的直接前驱、直接后继的指针，就形成了所谓的线索二叉树指向结点直接前驱与直接后继的指针叫做线索线索二叉树就是加上线索的二叉树将二叉树转变成线索二叉树的过程称为线索化线索二叉树的引入第7章树和二叉树由非线索的二叉树在遍历、查找时要引入栈来保存留待以后访问的子树信息；而线索化了的二叉树（假设为中序），只要从开始结点开始，顺着线索就能实现遍历和查找操作；线索二叉树利于找前驱和后继。线索二叉树的意义第7章树和二叉树FABCDEGHABCDEFGH示例–画出给出树的中序线索二叉树的结点形式，其中序序列为BFDGAEHC第7章树和二叉树structnode{structnode*lchild;intltag;datatypedata;intrtag;structnode*rchild;};

左孩左标志数据域右标志右孩rchildrtagdataltaglchild线索二叉树的结点类型第7章树和二叉树lchildltagdatartagrchild其中，ltag和rtag为标志域:0lchild域指示结点的左孩子

1lchild域指示结点的前驱

0rchild域指示结点的右孩子

1rchild域指示结点的后驱指向结点前驱与后继的指针叫做线索；Ltag=Rtag=线索二叉树的结点描述第7章树和二叉树0A0^1B00D1^1C11E1TADBEC示例–画出给出树的中序线索二叉树的结点存储形式，其中序序列为BCAED第7章树和二叉树ADBEC0A01B00D11C11E1^T示例–画出给出树的先序线索二叉树的结点存储形式，其先序序列为ABCDE第7章树和二叉树0A01B00D1^1C11E1TADBEC示例–画出给出树的后序线索二叉树的结点存储形式，其后序序列为CBEDA第7章树和二叉树分析：（1）若结点P有左孩子，则其左子树的第一个元素就是其后继，而左子树按照先序方式所选择的第一个元素是根结点，即P的左孩子；（2）否则，若结点P有右孩子，则其右儿子就是后继；（3）否则，P->rchild就是后继线索。ABCDEFGH线索链表的运算(先序后继的求解)第7章树和二叉树（1）查找结点（*P）后继:若结点的：rtag=1，则其rchild域直接指向其后继；rtag=0，则其后继应是它的右子树的最左结点线索链表的运算(中序)第7章树和二叉树ACBFEDIHKGJMLP1确定p1的后继q1：q1=p1->rchild;While(q1->ltag==0)q1=q1->lchild;第7章树和二叉树（2）查找结点（*P）前驱:若结点的：ltag=1，则其lchild域直接指向其前驱；ltag=0，则其前驱应是它的左子树的最右结点线索链表的运算(中序)第7章树和二叉树ACBFEDIHKGJMLP2确定p2的前驱q2：q2=p2->lchild;While(q2->rtag==0)q2=q2->rchild;第7章树和二叉树Voidxsinorder(TREENODE*T){TREENODE*p=T;while(p->ltag==0)p=p->lchild;while(p!=NULL){printf(“%d”,p->data);if(p->rtag==1)p=p->rchild;else{p=p->rchild;while(p->ltag==0)p=p->lchild;}}}中序遍历线索二叉树（树根为T）遍历算法第7章树和二叉树树的存储结构树与二叉树的转换树和森林的遍历树和森林第7章树和二叉树每个结点有两个指针域：First指针:指向该结点的第一个儿子结点；Next指针:指向该结点的右兄弟结点；第一个孩子右兄弟nextdatafirst结点描述与二叉链表相似树的存储结构——孩子兄弟表示法(二叉链表表示法)第7章树和二叉树TypedefstructTreenode{ elementtypedata; structTreenode*firstchild,*nextsibling;};ABCDEFG^AB^C^D^E^F^^G^树的孩子兄弟表示法图示第7章树和二叉树将树根转化为二叉树的根；对每个结点都做如下处理：结点第一个孩子转化为其二叉树中的左儿子；结点的右兄弟转化为其右儿子。转化过程：树与二叉树的转换(树→二叉树)第7章树和二叉树ABDCFEABDCFEABDCFEABDCFE将树转换为二叉树示意图：1.加线2.抹线3.旋转第7章树和二叉树2564781312436578练习：将下图所示树转化为二叉树第7章树和二叉树将二叉树根转化为树的根；对每个结点都做如下处理：结点的左儿子转化为其树中第一个孩子；结点的右儿子转化为其右兄弟。转化过程：树与二叉树的转换(二叉树→树)第7章树和二叉树ABDCFEABDCFEABDCFE将二叉树还原为树示意图第7章树和二叉树123456246315练习：将下图所示二叉树转化为树第7章树和二叉树将各棵树分别转换为二叉树；把第一棵树的根结点作为二叉树根结点；把其余树的根结点作为前一棵树的右孩子。森林与二叉树的转换(森林→二叉树)第7章树和二叉树ADCBEFGADCBEFGADCBEFGADCBEFG第7章树和二叉树抹线：将根结点的右孩子并沿右分支搜索到的所有右孩子与其根的连线抹去（形成各棵孤立的二叉树）还原：将各棵二叉树还原为一般树。森林与二叉树的转换(二叉树→森林)第7章树和二叉树ADCBEFGADCBEFGADCBEFGADCBEFG第7章树和二叉树按先根次序遍历若树不空，则先访问根结点，然后依次先根遍历各棵子树。按后根次序遍历若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历若树不空，则自上而下自左至右访问树中每个结点。树的遍历第7章树和二叉树按先根次序遍历:按后根次序遍历:按层次遍历:ABCDEFHABEFCDHEFBCHDAABCDEFH树的遍历示例第7章树和二叉树练习：将树转化为二叉树，遍历二叉树，得出什么结论？先根与先序等同序列、后根与中序等同序列两种遍历方法：（1）先序遍历森林：对森林中的每一棵树进行先根遍历。（2）后序遍历森林：对森林中的每一棵树进行后根遍历。注：由于在树和森林中，一个结点可以有两棵以上的子树，因此不便于讨论它们的中根遍历。森林的遍历第7章树和二叉树Voidpreorder(Tnode*t){if(t!=NULL){printf(“%c”,t–>data)preorder(t–>firstson);preorder(t–>nextbrother);}}先序遍历森林的递归算法第7章树和二叉树Voidpostorder(Tnode*t){if(t!=NULL){postorder(t–>firstson);printf(“%c”,t–>data);postorder(t–>nextbrother);}}后序遍历森林的递归算法第7章树和二叉树练习：写出树的先根和后根遍历序列第7章树和二叉树ABCDEFGHIJKM哈夫曼树哈夫曼编码哈夫曼树第7章树和二叉树结点间的路径长度：指结点之间的分支个数。设:一棵有n个叶子的二叉树，其每一叶子拥有一个权值Wk。(k=1,2,…,n)定义二叉树的带权路径长度：其中:Wk叶子结点的权值。

Lk从根到拥有权Wk的叶子结点路径的长度34652哈夫曼树的定义第7章树和二叉树3247

但若权值越大的叶子离根越近，则二叉树的带权路径长度就越小。Huffman树74233247

对给定的一组权值（例如{2，3，4，7}）作叶子，可生成多棵二叉树。WPL=4*2+7*2+2*2+3*2第7章树和二叉树问题：给定n个权值(w1,w2,…,wn),构造有n个叶子的哈夫曼树。n个权值(w1,w2,…,wn)构造一个包含n棵二叉树的集合F=(T1,T2,…,Tn),其中Ti为只有一个根结点(权为Wi)的二叉树；在F中选取两棵根权值最小的树分别作为左右子树构造一棵新的二叉树，新树根权值=左右子树根权值之和；在F中删除这两棵树，同时将新树加入F中；重复2、3直到F中只有一棵树为止，该树即为所求。哈夫曼树的构造算法第7章树和二叉树Huffman树的构造图例---以{2，3，4，4，7}为例23474447523选最小和次小4475238后续选最小和次小第7章树和二叉树

接上选最小和次小选最小和次小44752381244752381220WPL=(4+4+7)*2+(2+3)*3=45性质：哈夫曼树带权路径长度等于所有分支结点权值之和。第7章树和二叉树523251051578练习：已知对给定的一组权值{2，3，5，7，8}，构造Huffman树第7章树和二叉树在远程通讯中，要将待传字符转换成二进制的字符串设要传送的字符为：ABACCDA若编码为：A—00B—01 C—10D---11