6￥-six(天津科技大学)

第六章树和二叉树6.1

树的定义和基本概念6.2二叉树6.3遍历二叉树6.4树和森林6.6哈夫曼树及其应用

10/8/20241第六章树和二叉树树型结构的简单描述树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。10/8/20242第六章树和二叉树

6.1树的定义和基本术语递归定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。注：树的递归定义将为实现树的各种运算提供方便10/8/20243第六章树和二叉树树的示例及分析AACBEDFGHJILKM只有根结点的树一般的树10/8/20244第六章树和二叉树树的其它定义树是包含n个结点的有限集合，在这个集合上定义了一个唯一的关系，它满足下列条件：集合中存在唯一的一个结点，它没有前驱，称为树的根除根以外，集合中的每个结点都有且仅有一个前驱结点集合中包括树根结点的每个结点可以有任意多个（含0个）后继树的抽象数据类型定义见教材P118在不同的软件系统中树的基本操作可能不同10/8/20245第六章树和二叉树树的表示树形表示法:最常用的一种表示法。结点之间的关系通过连线表示，方向隐含为从上向下二元组表示法:Tree=(D,R)集合图表示法:每棵树对应一个圆形广义表表示法:类似广义表的形式凹入表表示法:类似书的编目注：(1)树表示方法的多样性，说明树结构在日常生活中及在计算机程序设计中的重要性；(2)分等级的分类方案都可用层次结构表示，也就是可通过树形结构描述。10/8/20246第六章树和二叉树树的基本术语根—树中唯一没有前驱的结点。度(结点的度和树的度)—一个结点的子树的数目，称为结点的度。树中结点的度的最大值，称为树的度。叶—度为0的结点，也称为终端结点。分枝结点—度大于0的结点称为分支结点或非终端结点（分为单分支结点、双分支结点等等）。10/8/20247第六章树和二叉树树的基本术语（续）双亲、孩子、祖先、子孙结点的子树的根，称为结点的孩子，而该结点则称为它的孩子的双亲。某结点的祖先指从根到该结点的一条路径上的全部结点，而结点的子孙是指该结点的子树中的全部结点。兄弟、堂兄弟—同一个结点的孩子，互为兄弟，其双亲为兄弟的结点称为堂兄弟。10/8/20248第六章树和二叉树树的基本术语（续）结点的层次、树的深度(高度)—根的层次为第一层，根的孩子为第二层，一个结点的层次为L，则它的孩子的层次为L+1。一棵树中结点的最大层次，称为树的深度或高度。有序树、无序树--若树中各结点的子树是按照一定的次序从左向右安排的，称为有序树。否则称为无序树。森林—m(m>=0)棵互不相交的树的集合。10/8/20249第六章树和二叉树6.2二叉树二叉树是另一种树形结构，它的特点是，每个结点至多只有两棵子树，而且其子树有左右之分，不能任意颠倒。二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。10/8/202410第六章树和二叉树二叉树的定义定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。二叉树抽象数据类型定义见教材P12110/8/202411第六章树和二叉树二叉树的五种基本形态

(a)空二叉树AABABACB

(b)根和空的左右子树

(c)根和左子树(d)根和右子树

(e)根和左右子树10/8/202412第六章树和二叉树二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。证明:当i=1时，只有一个根结点，2i-1=20=1,命题成立。假定第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。10/8/202413第六章树和二叉树二叉树的性质(续)性质2：深度为k的二叉树至多有2k－1个结点（k>=1).事实上，深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，

(第i层上的最大结点数）=

2i-1=2k–1

10/8/202414第六章树和二叉树二叉树的性质(续)性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。事实上，设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点的度均小于或等于2，所以有N＝n0＋n1＋n2

另外，除根结点外,其余结点都有一个进入分支，设B为二叉树中的分支总数,则有

N＝B＋1。由于这些分支都是由度为1和2的结点射出的,所以有B＝n1+2*n2

从而

N＝B＋1＝n1＋2*n2＋1总之n0+n1+n2=n1+2*n2+1故n0＝n2＋110/8/202415第六章树和二叉树满二叉树和完全二叉树一棵深度为k且由2k-1个结点的二叉树称为满二叉树。其特点是每一层上的结点数都是最大结点数。如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则为完全二叉树。10/8/202416第六章树和二叉树满二叉树举例24536718910111213141510/8/202417第六章树和二叉树12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树完全二叉树举例

10/8/202418第六章树和二叉树完全二叉树的特点及性质特点：（1)所有的叶结点都出现在第k层或k－1层；（2）对任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。性质4：具有n个结点的完全二叉树的深度为

log2n

＋1。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1<n<=2k-1或2k-1<=n<2k取对数得到：k－1<log2n<k因为k是整数。所以有：k＝

log2n

＋1。10/8/202419第六章树和二叉树完全二叉树的性质性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第

log2n

+1层，每层从左到右),则对任一结点i（1

i

n),有：（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点

i/2

。（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。10/8/202420第六章树和二叉树完全二叉树上结点之间的关系

[I/2]iI+12i2i+12(I+1)2i+3I+12(I+1)2i+3i2i2i+1(a)I和i+1结点在同一层(b)I和i+1结点不在同一层10/8/202421第六章树和二叉树二叉树的存储结构（一）顺序存储结构：用一组连续的存储单元存储二叉树的数据元素。把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：#definemax-tree-size100Typedef

telemtype

sqbitree[max-tree-size];Sqbitree

bt

10/8/202422第六章树和二叉树

顺序存储结构的特点从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。若经常需要插入与删除树中结点时，则不宜采用顺序存储结构。10/8/202423第六章树和二叉树二叉树的顺序存储结构示例

123456完全二叉树12367非完全二叉树123456123006710/8/202424第六章树和二叉树二叉树的链式存储结构—二叉链表

lchildDatarchildA^BC^D^E^F^^G^^H^头指针二叉链表结点结构10/8/202425第六章树和二叉树

二叉树的链式存储结构(续)

二叉树的二叉链表存储表示

Typedef

struct

BiTNode{

TelemTypedata;

struct

BiTNode*lchild,*rchild;}BiTNode,*BiTree;基本操作的函数原型说明见教材P127三叉链表--结点结构lchilddataparentrchild10/8/202426第六章树和二叉树6.3遍历二叉树和线索二叉树1遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。遍历二叉树即按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。“访问”可以是对结点作各种处理，如输出结点的信息等。遍历二叉树是二叉树中所有其它运算的基础。10/8/202427第六章树和二叉树如何遍历二叉树遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。A(根结点)(右子树)(左子树)10/8/202428第六章树和二叉树如何遍历二叉树（续）假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：

DLR——先（根）序遍历，

LDR——中（根）序遍历，

LRD——后（根）序遍历。按层次顺序对二叉树进行遍历。10/8/202429第六章树和二叉树遍历二叉树的递归算法先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。10/8/202430第六章树和二叉树如何遍历二叉树（续）后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。10/8/202431第六章树和二叉树先序遍历二叉树的递归算法Voidpreorder(BiTreeroot){if(root!=NULL){printf(“%5d”,root->data);preorder(root->lchild);preorder(root->rchild);}}10/8/202432第六章树和二叉树中序遍历二叉树的递归算法Voidinorder(BiTreeroot){if(root!=NULL){inorder(root->lchild);printf(“%5d”,root->data);

inorder(root->rchild);}}10/8/202433第六章树和二叉树后序遍历二叉树的递归算法Voidpostorder(BiTreeroot){if(root!=NULL){postorder(root->lchild);

postorder(root->rchild);printf(“%5d”,root->data);}}10/8/202434第六章树和二叉树三种遍历举例对右图所示的二叉树，三种遍历的结果为：先序：1,2,4,5,3,6中序：4,2,5,1,6,3后序：4,5,2,6,3,112345610/8/202435第六章树和二叉树三种遍历举例（续）如右图所示的二叉树表达式

a+b*(c-d)-e/f先序：-+a*b-cd/ef中序：a+b*c-d-e/f后序：abcd-*+ef/-人工处理用中缀形式的算术表达式；计算机处理使用后缀表达式易于求值－＋*a/b-dcfe10/8/202436第六章树和二叉树三种递归算法比较三种遍历算法不同之处在于访问根结点和遍历左、右子树的先后关系。若在算法中去掉和递归无关的输出语句，则三个遍历算法完全相同。从递归执行过程的角度看三种遍历也是完全相同的，参见三种递归过程示意图P13010/8/202437第六章树和二叉树先序遍历的非递归算法Voidpreorder(BiTreeroot){BiTreep,s[N];inttop=0;p=root;while(1){while(p!=NULL){printf(“%5d”,p->data);/*先访问*/top++;s[top]=p;/*进栈，保留信息，以便稍后去遍历右子树*/p=p->lchild;/*递归，一直向左，直到最左点*/}10/8/202438第六章树和二叉树先序遍历的非递归算法（续）

if(top!=0/*如果栈不空*/{p=s[top];top--;p=p->rchild;}/*出栈，找到栈顶结点的右孩子，转去递归*/elsereturn;}}10/8/202439第六章树和二叉树二叉树遍历算法效率分析在先序遍历中，每个结点只经过一次，中序遍历中，有左、右孩子的结点要经过两次（先去中序遍历它的左子树，从左子树返回时才访问它），而后序中，有左、右孩子的结点要经过三次。三种遍历算法的时间复杂度都是O(n)。所需辅助空间为栈空间，栈的容量为树的高度，最多不超过n，所以空间复杂度也为O(n)。10/8/202440第六章树和二叉树二叉树的层次遍历层次遍历的形式有多种，最为常用的是第一种自上而下，自左而右的方式其它层次遍历形式包括：第二种自底向上，自左向右；第三种自上而下，从第二层开始的各层交替地按自左向右的顺序和自右向左的顺序；第四种自下而上，各层交替地按自右向左的顺序和自左向右的顺序。10/8/202441第六章树和二叉树二叉树遍历算法的应用“遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树可求结点的双亲，求结点的孩子结点，判定结点所在层次，求二叉树的深度，求二叉树的叶子结点个数等。可在遍历过程中生成结点，建立二叉树的存储结构。10/8/202442第六章树和二叉树利用先序序列建立二叉树二叉树及二叉链表存储结构ABCDEFGABDCGEF^^^^^^^^顺序读入字符ABC##DE#G##F###10/8/202443第六章树和二叉树利用先序序列建立二叉树的算法VoidCreateBiTree(BiTNode*t)//构造二叉链表表示的二叉树{charc;

c=getchar();if(c==‘#’)return(NULL);else{t=(BiTNode)malloc(sizeof(BiTNode))t–>data=c;//生成根结点

CreateBiTree(t–>lchild);//构造左子树

CreateBiTree(t–>rchild);}//构造右子树

returnOK;}10/8/202444第六章树和二叉树求二叉树深度的算法int

depth(BiTNodet){inthl,hr;if(!t)return0;else{hl=depth(t->lchild);hr=depth(t->rchild);if(hl>=hr)returnhl+1;elsereturnhr+1;}}10/8/202445第六章树和二叉树线索二叉树遍历二叉树实质上是对一个非线性结构进行线性化操作。当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能直接得到结点在任一序列中的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到。为了能保存遍历过程中得到的信息，可为每个结点增加两个指针域fwd和bkwd，分别指示结点在任一次序遍历是得到的前驱和后继信息，但这样做使得结构的存储密度大大降低。10/8/202446第六章树和二叉树线索二叉树的结点结构有n个结点的二叉链表中有n+1个空链域，可利用这些空链域来存放结点的前驱和后继的信息。规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。为了避免混淆，其结点结构可增加标志域lchildltagdatartagrchild10/8/202447第六章树和二叉树线索二叉树的结点结构（续）其中:0lchild

域指示结点的左孩子

ltag={1lchild

域指示结点的前驱

0rchild

域指示结点的右孩子

rtag={1rchild

域指示结点的后驱以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。10/8/202448第六章树和二叉树6.4树和森林主要内容：树的表示及其遍历操作；森林与二叉树的对应关系。树的三种存储结构

1、双亲表示法

2、孩子表示法

3、孩子兄弟表示法

10/8/202449第六章树和二叉树双亲表示法以一组连续空间存储树的结点，同时在每个结点种附设一个指示器指示其双亲结点在链表中的位置,见图6.13形式说明如下：

#defineMAX_TREE_SIZE100

typedef

struct

PTNode

{//结点结构

ElemTypedata;

intparent;//双亲位置域

}

PTNode;:

typedef

struct{//树结构

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}

PTree;缺点：求结点的孩子时需要遍历整个结构10/8/202450第六章树和二叉树孩子表示法把每个结点的孩子结点排列起来，看作一个线性链表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）n个头指针又组成一个线性表，采用顺序存储结构存储结构形式说明见P136孩子表示法便于那些涉及孩子的操作的实现，却不适用于对双亲的操作。可以把双亲表示法和孩子表示法结合起来，即把双亲表示和孩子链表合在一起。10/8/202451第六章树和二叉树孩子兄弟表示法以二叉链表作树的存储结构，又称二叉树表示法或二叉链表表示法。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域树的二叉链表(孩子-兄弟)存储表示

typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree10/8/202452第六章树和二叉树孩子兄弟表示法举例

RBCDEFGABDGEC^^^^^HKAH^K^^F^R^^^注：这种存储结构便于实现各种树的操作10/8/202453第六章树和二叉树6.4树和森林主要内容：树的表示及其遍历操作；森林与二叉树的对应关系。树的三种存储结构

1、双亲表示法

2、孩子表示法

3、孩子兄弟表示法

10/8/202454第六章树和二叉树孩子兄弟表示法以二叉链表作树的存储结构，又称二叉树表示法或二叉链表表示法。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域树的二叉链表(孩子-兄弟)存储表示

typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree10/8/202455第六章树和二叉树孩子兄弟表示法举例

RBCDEFGABDGEC^^^^^HKAH^K^^F^R^^^注：这种存储结构便于实现各种树的操作10/8/202456第六章树和二叉树森林与二叉树的转换

由于二叉树和树都可用二叉链表作为存储结构，则通过二叉链表可导出树与二叉树之间的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构看，它们的二叉链表是相同的，只是解释不同。10/8/202457第六章树和二叉树树与二叉树的对应关系示例ABCEDABCEDABCDE^^^^^^任何一棵和树对应的二叉树，其右子树必空10/8/202458第六章树和二叉树森林与二叉树的转换（续）若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则可导出森林和二叉树的对应关系森林与二叉树之间的对应关系示例见P138森林或树与二叉树相互转换的形式定义见P138将树转换为二叉树的转换规则：将树中每个结点的第一个孩子结点转换为二叉树中对应结点的左孩子，将第二个孩子结点转换为左孩子的右孩子，将第三个结点转换为右孩子的右孩子10/8/202459第六章树和二叉树树和森林的遍历树的遍历可有三条搜索路径先根次序遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根次序遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历：若树不空，则自上而下自左至右访问树中每个结点。

树的遍历举例P13910/8/202460第六章树和二叉树森林的遍历先序遍历(对森林中的每一棵树进行先根遍历)

若森林不空，则

访问森林中第一棵树的根结点;

先序遍历森林中第一棵树的子树森林;

先序遍历森林中(除第一棵树之外)其余树构成的森林。中序遍历(对森林中的每一棵树进行后根遍历)

若森林不空，则中序遍历森林中第一棵树的子树森林;

访问森林中第一棵树的根结点;

中序遍历森林中(除第一棵树之外)其余树构成的森林。10/8/202461第六章树和二叉树森林的遍历（续）森林的遍历示例见P139当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，则上述森林的先序和中序遍历即为对应的二叉树的先序和中序遍历序列。若以二叉链表作树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序和中序遍历的算法实现10/8/202462第六章树和二叉树6.8哈夫曼树与哈夫曼编码

哈夫曼(Huffman)树，又称最优树，是一类带权路径长度最短的树。从树中一个结点到另一个结点之间路径上的分支数称做路径长度。树根到每一个结点的路径长度之和称为树的路径长度。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为从树中所有叶子结点的带权路径长度之和，记作WPL(T)=

wklk

(对所有叶子结点)

。10/8/202463第六章树和二叉树最优二叉树(哈夫曼树)假设有n个权值{w1,w2,…,wn}，构造一棵有

n个叶子结点的二叉树，每个叶子结点带权为wi

，则其中带权路径长度WPL最小的二叉树称做最优二叉树或哈夫曼树。具有不同带权路径长度的二叉树示例见P144，权值越大的结点离根越近的二叉树才是最优二叉树。在解某些判定问题时，利用哈夫曼树可以得到最佳判定算法，如：编制一个将百分制转换成五分制的程序。10/8/202464第六章树和二叉树哈夫曼算法根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;

从F中删去这两棵树，同时加入刚生成的新树;

重复(2)和(3)两步，直至F中只含一棵树为止。10/8/202465第六章树和二叉树哈夫曼树的构造过程

abcd7524(a)a7b5cd6(b)a7bcd11(c)abcd18(d)10/8/202466第六章树和二叉树哈夫曼编码哈夫曼树的应用很广，哈夫曼编码就是其中的一种。在电报通讯中，电文是以二进制的0,1序列传送的。发送端需编码,接受端需译码。等长编码是最简单的二进制编码方式。但电文中每个字符的出现频率不同，采用等长编码，传送电文的总长度较大。举例:电文为‘ABACCDA’,设A,B,C,D的编码分别为00,01,10,11,则电文为‘00010010101101’总长为14位。10/8/202467第六章树和二叉树哈夫曼编码（续）解决办法之一是采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，从而可缩短传送电文的总长度。若设A,B,C,D的编码分别为0,00,1和01，则电文‘ABACCDA’可转换成长度为9的字符串‘000011010’,此时电文无法译码。要设计长短不等的编码，必须是任一个字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。显然等长编码是前缀编码。10/8/202468第六章树和二叉树哈夫曼编码（续）为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树。如图所示的二叉树有4个叶子结点A,B,C,D，其二进制前缀编码分别为0,10,110,111。ABCD00011110/8/202469第六章树和二叉树哈夫曼编码（续）设每种字符在电文中出现的次数为wi,其编码长度为li,电文中只有n种字符，则电文总长为

wili.对应二叉树，若置wi为叶子结点的权，li恰为从根到叶子结点的路径长度，则

wili恰为二叉树上带权路径长度。为了获得传送电文的最短长度，可将每个字符的出现频率作为字符结点的权赋予该结点上，设计一棵哈夫曼树的问题，求出此树的最小带权路径长度就等于求出了传送电文的最短长度。由此得到的二进制前缀编码称为哈夫曼编码。10/8/202470第六章树和二叉树哈夫曼编码（续）以电文中每个字符出现的频率作为叶子结点的权值来设计哈夫曼树。求每个叶结点的编码。从叶到根通过依次找双亲来进行，但编码串是从根开始的。对每个编码进行译码。译码就是要对一个二进制串所代表的字符给出它唯一的解释，需从根到叶进行查找。注：哈夫曼树没有度为1的结点，一棵有n个叶子结点的二叉哈夫曼树共有2n-1个结点。10/8/202471第六章树和二叉树哈夫曼编码举例例：已知某系统在通信联络中可能出现8种字符，其概率为0.05,0.29,0.07,0.08,0.l4,0.23,0.03,0.11,试设计哈夫曼编码。解：设权w=(5,29,7,8,14,23,3,11),根据哈夫曼算法可构造哈夫曼树。5311237814290000000111111110/8/202472第六章树和二叉树树的计数具有n个结点的不同形态的树有多少棵？二叉树T和T’相似是指：二者都为空树或者二者均不为空树，且它们的左右子树分别相似。二叉树T和T’等价是指：二者不仅相似，而且所有对应结点上的数据元素均相同。二叉树的计数问题就是求具有n个结点、互不相似的二叉树的数目？含有n个结点、互不相似的二叉树有10/8/202473第六章树和二叉树二叉树的确定任意一棵二叉树结点的先序序列和中序序列是唯一的。问题：给定结点的先序序列和中序序列，能否确定一棵二叉树？是否唯一？分析：二叉树的先序遍历是先访问根结点D；其次遍历左子树L，最后遍历右子树R。在结点的先序序列中，第一个结点必是根D。10/8/202474第六章树和二叉树二叉树的确定（续）另一方面，由于中序遍历是先遍历左子树L，然后访问根D，最后遍历右子树R，则根结点D将中序序列分割成两部分：在D之前是左子树结点的