数据结构第六章树和二叉树

数据结构第六章树和二叉树第1页，共67页，2023年，2月20日，星期六第六章树和二叉树第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4遍历的应用6.7哈夫曼树及应用第2页，共67页，2023年，2月20日，星期六第六章树和二叉树6.1

树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作第3页，共67页，2023年，2月20日，星期六

树形结构是一种重要的非线性结构，讨论的是层次和分支关系。(1)树的定义树是n(n≥0)个结点的有限集,在任意一棵非空树中满足下面两个条件:▲有且仅有一个特定的称为根的结点；6.1

树的有关概念1．树的概念▲当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1，T2，…，Tm，其中每个集合本身又是一棵树，并且称为根的子树。第4页，共67页，2023年，2月20日，星期六(2)图示JIACBDHGFEKLMA

T={A,B,C,D,E,F,G,H,I,J，K，L，M}

A是根，其余结点可以划分为3个互不相交的集合：

T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M}

这些集合中的每一集合都本身又是一棵树，它们是A的子树。例如，对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E，K，L}，T12={F}，T11,T12

是B的子树。第5页，共67页，2023年，2月20日，星期六从逻辑结构看：

1）树中只有根结点没有前趋；

2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；

4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。JIACBDHGFEKLMA第6页，共67页，2023年，2月20日，星期六

①树可表示具有分枝结构关系的对象

JIACBDHGFEKLM局例1家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J，K，L，M，他们之间的关系可用右图所示的树表示：科1科2科3室2室2室2人…

室1室3室1室3室1室3人…

人…

人…

人…

人…

人…

人…

人…

例2单位行政机构的组织关系2．树的应用

第7页，共67页，2023年，2月20日，星期六

例3计算机的文件系统

不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C第8页，共67页，2023年，2月20日，星期六

②广义表

（A

（B（E（K,L）,F）,C（G）,D（H（M）,I,J）））ABCABEKLFCGDHMJIJIACBDHGFEKLMFEKLDHJIM

③凹入表（类似书的目录）

①嵌套集合

G3树的其他表示形式

第9页，共67页，2023年，2月20日，星期六5基本术语⑴结点(node):

数据元素+若干指向其子树的分枝；

⑵结点的度(degree)：结点拥有的子树(分支)数；

⑶

叶子(终端结点leaf)：度为0的结点；JIACBDHGFEKLM⑷分枝结点(非终端结点、内部结点)：度不为0的结点；

⑸

树的度：树中所有结点的度的最大值；

⑹

孩子(child)：结点的子树的根称为该结点的孩子；

⑺

双亲(parent)：B结点是A结点的孩子，则A结点是B结点的双亲；

⑻兄弟(sibling)：同一双亲的孩子之间的称呼；

⑼祖先：根结点到该结点所经分枝上的所有结点；

⑽子孙：以某结点为根的子树中任一结点都称为该结点的子孙第10页，共67页，2023年，2月20日，星期六

⑾层次(level)：从根结点开始定义.根为第一层，根的孩子为第二层，若某结点在第L层,则其子树的根就示第L+1层；⑿堂兄弟：同一层上结点；

⒀树的深度(高度depth)：树中结点的最大层次；

⒁有序树：各子树看成从左至右是有次序的(即不能互换)；如：家族树

⒂无序树：各子树从左至右是无序的(即能互换)；

⒃森林(forest)：m(m≥0)棵树互不相交的集合。森林和树之间的联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。第11页，共67页，2023年，2月20日，星期六第六章树和二叉树6.2二叉树1二叉树的概念2二叉树的性质3二叉树的存储结构第12页，共67页，2023年，2月20日，星期六

树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。6.2二叉树第13页，共67页，2023年，2月20日，星期六1、二叉树(1)二叉树的定义二叉树(BinaryTree)是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。

二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

A

F

G

E

D

C

B

A

G

E

D

B

C

F第14页，共67页，2023年，2月20日，星期六说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;第15页，共67页，2023年，2月20日，星期六(2)二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树第16页，共67页，2023年，2月20日，星期六(4)二叉树应用举例例1

例1可以用二叉树表示表达式

b

e

d

c

f

a

+

*

/

-

-a+b*(c-d)-e/f第17页，共67页，2023年，2月20日，星期六例2双人比赛的所有可能的结局(五局三胜制)甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙开始开局连赢两局或五局三胜第18页，共67页，2023年，2月20日，星期六2二叉树的性质

性质1

在二叉树的第i层上至多有2i-1

个结点(i≥1)。

性质2

深度为k的二叉树至多有2k-1

个结点。(k≥1)

性质3对任何一棵二叉树,如果其终端结点个数为n0，度为2的结点数为n2，则有n0＝n2＋1

第19页，共67页，2023年，2月20日，星期六★两类特殊的二叉树①满二叉树

深度为k且含有2k-1

个结点的二叉树。123456789101112131415②完全二叉树

树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。

A

G

F

E

D

C

B

I

H

G

A

E

D

C

B完全二叉树不是完全二叉树第20页，共67页，2023年，2月20日，星期六

C

A

G

F

E

D

B(a)

B

A

E

D

C(b)

G

A

E

D

C

B(c)、(b)完全二叉树(c)不是完全二叉树第21页，共67页，2023年，2月20日，星期六

性质4

具有n个结点的完全二叉树的深度为log2n+1。

性质5

如果将一棵有n个结点的完全二叉树(其深度为log2n+1)自顶向下，同一层自左向右连续给结点编号1,2,…,n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中,并简称编号为i的结点为结点i(1≤i≤n)。则有以下关系：①若i==1,则i是二叉树的根，无双亲；若i>1,则i的双亲为PARENT(i)=i/2。②若2i>n则结点i无左孩子(是叶子结点)；否则i的左孩子LCHILD(i)=2i。③若2i+1>n则结点i无右孩子(是叶子结点)；否则i的右孩子RCHILD(i)=2i+1。

第22页，共67页，2023年，2月20日，星期六性质5：在完全二叉树中编号为i的结点1）若有左孩子，则左孩编号为2i2）若有右孩子，则右孩子结点编号为2i+13）若有双亲，则双亲结点编号为trunc(i/2)

A

F

E

D

C

B123456第23页，共67页，2023年，2月20日，星期六3二叉树的存储结构二叉树的顺序结构完全二叉树的顺序结构①概念：用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素。例如，用一维数组bt[]存放一棵完全二叉树，将标号为i的结点的数据元素存放在分量bt[i-1]中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，bt[5]（i=6)的双亲结点标号是k=trunc(i/2)=3,双亲结点所对应的数组分量bt[k-1]=bt[2]

第24页，共67页，2023年，2月20日，星期六非完全二叉树的顺序结构按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点编号,将二叉树原有的结点按编号存储到内存单元“相应”的位置上。但这种方式对于畸形二叉树，浪费较大空间。

A

F

G

E

D

C

B1672453810

A

F

G

D

C

B9E012345678910m-1ABCDE0F00G第25页，共67页，2023年，2月20日，星期六②结构定义#definemax—tree—size100typetelemtypesqbitree[max—tree—size]；sqbitreebt；

▲

注意适用性。单支树第26页，共67页，2023年，2月20日，星期六(2)二叉树的链式存储结构①概念：二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式。

②结点结构③(结点)结构定义

typedefstructBiTNode{TElemTypedata;

structBiTNode*lchild;//左孩子指针

structBiTNode*rchild;//右孩子指针}

BiTNode,*BiTree;第27页，共67页，2023年，2月20日，星期六④图示第28页，共67页，2023年，2月20日，星期六6.3二叉树的遍历

一.二叉树的遍历方法二.遍历的递归算法三.遍历的非递归算法第29页，共67页，2023年，2月20日，星期六1、遍历二叉树的方法(Traversingbinarytree)(1)遍历二叉树的概念

遍历二叉树是指按某种搜索路径访问二叉树的每个结点，而且每个结点访问且仅被访问一次。

访问的含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。

遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。6.3二叉树的遍历如何访问二叉树的每个结点，而且每个结点仅被访问一次？？第30页，共67页，2023年，2月20日，星期六(2)二叉树的遍历方法

①二叉树的遍历的特殊性

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。

第31页，共67页，2023年，2月20日，星期六对“二叉树”而言，可以有三条搜索路径：

I先上后下的按层次遍历；

II先左(子树)后右(子树)的遍历；

III

先右(子树)后左(子树)的遍历。

A

F

G

E

D

C

B②二叉树的遍历方法二叉树由根、左子树、右子树三部分组成；二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树；第32页，共67页，2023年，2月20日，星期六令：L：遍历左子树

T：访问根结点

R：遍历右子树

有六种遍历方法：TLR，LTR，LR

T，TR

L，R

TL，R

LT

约定先左后右,有三种遍历方法：TLR、LTR、LR

T，分别称为：先序遍历、中序遍历、后序遍历。第33页，共67页，2023年，2月20日，星期六③三种遍历二叉树的(递归)操作定义

A

F

G

E

D

C

B

I先序遍历二叉树的操作定义(TLR)

若二叉树为空，则为空操作；否则

a、访问根结点

b、先序遍历左子树，即按TLR的顺序遍历左子树

c、先序遍历右子树，

即按TLR的顺序遍历右子树

先序遍历序列：A,B,D,E,G,C,F第34页，共67页，2023年，2月20日，星期六

A

F

G

E

D

C

B

II

中序遍历二叉树的操作定义(LTR)

若二叉树为空，则为空操作；否则

a、中序遍历左子树，即按LTR的顺序遍历左子树

b、访问根结点

c、中序遍历右子树，即按LTR的顺序遍历右子树

中序遍历序列：D,B,G,E,A,C,F第35页，共67页，2023年，2月20日，星期六

III后序遍历二叉树的操作定义(LR

T)

若二叉树为空，则空操作，否则

a、后序遍历左子树，

即按LR

T的顺序遍历左子树

b、后序遍历右子树，

即按LR

T的顺序遍历右子树

c、访问根结点

A

F

G

E

D

C

B后序遍历序列：D,G,E,B,F,C,A第36页，共67页，2023年，2月20日，星期六

d

b

e

a*

-

/

c+例：先序、中序、后序遍历右图所示的二叉树先序序列：+,*,a,-,b,c,/,d,e

--表达式的前缀表示(波兰式)中序序列：a,*,b,-,c,+,d,/,e

--表达式的中缀表示后序序列：a,b,c,-,*,d,e,/,+

--表达式的后缀表示(逆波兰式)第37页，共67页，2023年，2月20日，星期六二.

三种遍历二叉树的递归算法上面先序遍历的定义等价于：若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；第38页，共67页，2023年，2月20日，星期六

①前序

intpreordertraverse(BiTreet,int(*visit)(telemtype)){if(t)

{visit(t→data);

preordertraverse(t→lchild,visit(telemtype));

preordertraverse(t→rchild,visit(telemtype));}}∧

a∧+*/∧d

∧-root∧

e∧∧

b∧∧

c∧a*(b-c)+d/e第39页，共67页，2023年，2月20日，星期六∧

a∧+*/∧d

∧-root∧

e∧∧

b∧∧

c∧②中序

intinordertraverse(BiTreet,int(*visit)(telemtype)){if(t)

{inordertraverse(t→lchild,visit(telemtype));

visit(t→data);

inordertraverse(t→rchild,visit(telemtype));}}第40页，共67页，2023年，2月20日，星期六∧

a∧+*/∧d

∧-root∧

e∧∧

b∧∧

c∧③后序

intpostordertraverse(BiTreet,int(*visit)(telemtype)){if(t)

{postordertraverse(t→lchild,visit(telemtype));

postordertraverse(t→rchild,visit(telemtype));visit(t→data);}}第41页，共67页，2023年，2月20日，星期六+∧

a∧

+

*//\d/\

-root∧e∧∧

b∧∧

c∧

④三种遍历过程示意图a*(b-c)+d/e*a-bc/de

+

*

a

b

-

c

d

/

e

+

/

e

d

*-

+

b

e先序中序后序第42页，共67页，2023年，2月20日，星期六三.

三种遍历二叉树的非递归算法

①前序

分析：对每个结点，在访问完后，沿其左链一直访问下来，直到左链为空，这时，所有已被访问过的结点进栈。然后结点出栈，对于每个出栈结点，即表示该结点和其左子树已被访问结束，应该访问该结点的右子树。

I当前指针指向根结点；

II输出当前结点，当前结点指针进栈，然后指向其左孩子，重复II，直到左孩子为NULL；

III依次退栈，将当前指针指向右孩子；

IV若栈非空或当前指针非NULL，执行II；否则结束。递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑非递归算法。第43页，共67页，2023年，2月20日，星期六

intpreorder(BiTree

t){BiTree

stack[50];inttop;top=-1;do{while(t!=NULL){cprintf("%c",t->data);top++;stack[top]=t;t=t->lchild;}if(top>=0){t=stack[top];top--;t=t->rchild;}}while(top>=0||t!=NULL);}前序遍历二叉树的非递归算法描述∧

a∧+*/∧d

∧-t∧

e∧∧

b∧∧

c∧543210topcprintf("%c",t->data);top++;+topstack[top]=t;t=t->lchild;tcprintf("%c",t->data);*top++;topstack[top]=t;t=t->lchild;tcprintf("%c",t->data);atop++;topstack[top]=t;t=t->lchild;ttt=stack[top];top--;topt=t->rchild;tt=stack[top];ttop--;topt=t->rchild;tcprintf("%c",t->data);-top++;topstack[top]=t;tt=t->lchild;cprintf("%c",t->data);btop++;topstack[top]=t;t=t->lchild;tt=stack[top];ttop--;topt=t->rchild;t=stack[top];tttop--;topt=t->rchild;tcprintf("%c",t->data);ctop++;topstack[top]=t;t=t->lchild;tt=stack[top];ttop--;topt=t->rchild;tt=stack[top];ttop--;topt=t->rchild;tcprintf("%c",t->data);/top++;topstack[top]=t;t=t->lchild;tcprintf("%c",t->data);dtop++;topstack[top]=t;t=t->lchild;tt=stack[top];ttop--;topt=t->rchild;tt=stack[top];ttop--;topt=t->rchild;tcprintf("%c",t->data);etop++;topstack[top]=t;t=t->lchild;tt=stack[top];ttop--;topt=t->rchild;twhile(top>=0||t!=NULL);第44页，共67页，2023年，2月20日，星期六

d

b

a

*

-

/

c

+

erootpnode[]6543210topprintf(“%c,”,root->data);+node[top]=p;top++;topp=p->lch;pprintf(“%c,”,root->data);*node[top]=p;top++;topp=p->lch;pprintf(“%c,”,root->data);anode[top]=p;top++;topp=p->lch;pif(top>0)top--;topp=node[top];pp=p->rch;ptopppprintf(“%c,”,root->data);-node[top]=p;top++;topp=p->lch;pbtopptop--;p=node[top];p=p->rch;topptoppppcprintf(“%c,”,root->data)node[top]=p;top++;topp=p->lch;ptop--;topp=node[top];pp=p->rchtopptprintf(“%d,”,root->data);/node[top]=p;top++;topp=p->lchild;d第45页，共67页，2023年，2月20日，星期六6.4遍历的应用遍历是二叉树的基本操作：二叉树许多操作可在遍历过程中完成，本节再举几个二叉树遍历应用实例。第46页，共67页，2023年，2月20日，星期六

(1)求二叉树各结点的层数

intlevelnum(bitreet,intnum){if(t==NULL)return(0);else{num++;cprintf("%c--%d",t->data,num);levelnum(t->lchild,num)+levelnum(t->rchild,num);}}第47页，共67页，2023年，2月20日，星期六

②求二叉树的深度

intdepth(BiTree

t){intdep1=0,dep2=0;if(t==NULL)return(0);else{dep1=depth(t->lchild);dep2=depth(t->rchild);if(dep1>dep2)return(dep1+1);elsereturn(dep2+1);}}第48页，共67页，2023年，2月20日，星期六例编写求二叉树的叶子结点个数的算法

输入：二叉树的二叉链表

结果：二叉树的叶子结点个数∧

D

A

B

∧

C

∧∧

E

∧∧

F

∧rootvoidleaf(BiTree

*root)//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点//的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数//第一次被调用时，n=0{if(root!=NULL)

{if(root->lchild==NULL&&root->rchild==NULL)n=n+1;//若root所指结点为叶子,则累加

leaf(root->lchild);leaf(root->rchild);}}与先序遍历算法比较一下！第49页，共67页，2023年，2月20日，星期六求二叉树叶子数

intleafnum(bitreet){if(t==NULL)return(0);else{if(t->lchild==NULL&&t->rchild==NULL)return1;returnleafnum(t->lchild)+leafnum(t->rchild);}}

第50页，共67页，2023年，2月20日，星期六

比较先序遍历算法和计算叶子结点算法，有什么相同和不同？结构类似函数名不同访问结点时调用printf()访问结点时统计叶子结点的个数voidprev(BiTree

*root)

{

if(root!=NULL)

{printf(“%d,”,root->data)；

prev(root->lchild);

prev(root->rchild);

}}voidleaf(BiTree

*root){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL)n=n+1;

leaf(root->lchild);leaf(root->rchild);}}第51页，共67页，2023年，2月20日，星期六例建立二叉链表

输入：二叉树的先序序列

结果：二叉树的二叉链表

遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入（在空子树处添加字符*的二叉树的）先序序列（设每个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接

A

F

E

D

C

B*******ABD*F***CE***第52页，共67页，2023年，2月20日，星期六输入（在空子树处添加空格字符的二叉树的）先序序列（设每个元素是一个字符）按先序遍历的顺序，建立二叉链表，并将该二叉链表根结点指针赋给root

BiTree*create_tree(BiTree

*root){charch;scanf(&ch);

if(ch==‘’)root=NULL;

//若ch==‘*’则root=NULL返回

else{

//若ch!=‘*’

root=(BiTree*)malloc(sizeof(BiTNode);

root->data=ch;

//建立（根）结点

root->lchild=create_tree(root->lchild);

//构造左子树链表，并将左子树根结//点指针赋给（根）结点的左孩子域

root->rchild=create_tree(root->rchild);

//构造右子树链表，并将右子树根}return(root);//结点指针赋给（根）结点的右孩子域}第53页，共67页，2023年，2月20日，星期六∧

D

A

B

∧

C

∧∧

E

∧∧

F

∧T先序序列：ABDFCE（在空子树处添加*的二叉树的）先序序列：

ABD

FCE

A

F

E

D

C

B

A

F

E

D

C

B第54页，共67页，2023年，2月20日，星期六6.7哈夫曼树及应用第55页，共67页，2023年，2月20日，星期六1、最优二叉树(赫夫曼(Huffman)树)(1)路径及路径长度ABDECFHIKGJL

n个结点的二叉树的路径长度不小于下述数列前n项的和，即①路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。②路径长度：路径上的分支数目。③树的路径长度：从树根到每一结点的路径长度之和。

在结点数相同的条件下，完全二叉树是路径最短的二叉树。其路径长度最小者为第56页，共67页，2023年，2月20日，星期六(2)树的带权路径长度①带权结点：含权值的结点。根据需要可以给树的结点赋权值。②结点的带权路径长度：从该结点到树根之间路径长度与结点上权的乘积。③树的带权路径长度：树中所有叶子结点的带权路径长度之和。记为(3)最优二叉树(赫夫曼树)①概念：设有n个权值量{W1,W2,…,Wn}，构造一棵有n个叶子结点的二叉树，每个叶子的结点带权为Wi，则其中WPL最小的二叉树称做最优二叉树(赫夫曼树)。②相同结点及权值构造不同的二叉树得到不同WPL的示例第57页，共67页，2023年，2月20日，星期六3582DBCA(b)

DABC2358(c)

ABDC2358

(a)

一个软件小组四个人，由于业务和工作关系，找组长A频率是8，找副组长B的频率是5，找负责数据库程序员C的频率是3，找负责网络程序员D的频率是2，以这些频率为权的带权叶子结点所构成的三棵二叉树如下：其带权路径长度分别为：(a)WPL=8×2+5×2+3×2+2×2=36

(b)

WPL=8×3+5×3+3×2+2×1=47

(c)

WPL=8×1+5×2+3×3+2×3=33

可以验证(c)即为赫夫曼树。若用线性表来组织查找的话，其最小值为35，体现了用构造赫夫曼树来解决这类问题的优越性。第58页，共67页，2023年，2月20日，星期六分数0—5960—6970—7980—8990—100比例数

0.05

0.15

0.40

0.30

0.10

③判定问题

设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：例如下面的程序：if(a<60)p=“bad”;elseif(a<70)p=“pass”;elseif(a<80)p=“general”;elseif(a<90)p=“good”;elsep=“excellent”;a80a90不及格良好中等及格优秀a60a70第59页，共67页，2023年，2月20日，星期六按图的判定过程:转换一个分数所需的比较次数=从根到对应结点的路径长度转换10000个分数所需的总比较次数=10000

(0.051+0.152+0.43+0.34+0.14)=31500

可有不同的判定过程，最佳判定过程为：a<80a<70a<90a<60generalbadpassgoodexcellentYYYYNNNN第60页，共67页，2023年，2月20日，星期六总共仅需进行10000

(0.053+0.153+0.42+0.32+0.12)=22000次比较▲

此二叉树可以认为是满足一定条件的赫夫曼树。是为了减少比较而使得权值相对较小的结点不在相对层次较低的位置上。(4)赫夫曼树的构造①构造思想

把所要构造的带权结点都构造在赫夫曼树的叶子位子，权值