树的类型定义课件

Tree&BinaryTree

Tree&BinaryTree

1树的类型定义n(n≥0)个元素的有限集合树的类型定义n(n≥0)个元素的有限集合2基本术语基本术语3结点结点的度树的度叶子结点分支结点数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM结点结点的度树的度叶子结点分支结点数据元素+若干指向子树的分4(从根到结点的)路径孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL(从根到结点的)路径孩子结点、双亲结点由从根到该结点5结点的层次树的深度ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次结点的层次树的深度ABCDEFGHIJMKL假设根结点的层次6任何一棵非空树是一个二元组Tree=（root，F）其中root被称为根结点F被称为子树森林森林是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF任何一棵非空树是一个二元组森林是m（m≥0）棵互ArootB7(１)有确定的根(２)树根和子树根之间为有向关系有向树有序树子树之间存在确定的次序关系无序树子树之间不存在确定的次序关系(１)有确定的根有向树有序树子树之间存在确定的次序关系无序8结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子女(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree)结点(node)兄弟(sibling)结点9对比树型结构和线性结构的结构特点对比树型结构和线性结构的结构特点10~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~11树的抽象数据类型定义树的抽象数据类型定义12数据对象DD是具有相同特性的数据元素的集合数据对象DD是具有相同特性的数据元素的集合131.若D为空集，则称为空树2.在D中存在唯一的称为根的数据元素root3.当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树

数据关系R1.若D为空集，则称为空树数据关系R14基本操作查找类插入类删除类基本操作查找类插入类删除类15Root(T)//求树的根结点查找类Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子Root(T)//求树的根结点查找类Value(16RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历RightSibling(T,cur_e)TreeEm17InitTree(&T)//初始化置空树插入类CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树InitTree(&T)//初始化置空树插入类Cr18ClearTree(&T)//将树清空删除类DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ClearTree(&T)//将树清空删除类Des19ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根ABCDEFGHIJMKLA(B(E,F(K,L)),20二叉树的类型定义二叉树的类型定义21二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成ABCDEFGHK根结点左子树右子树二叉树或为空树，或是由一个根结点加上两棵分别称为左子22二叉树的五种基本形态N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的五种基本形态N空树只含根结点NNNLRR右子树为空树23二叉树的主要基本操作查找类插入类删除类二叉树的主要基本操作查找类插入类删除24Root(T)Value(T,e)Parent(T,e)LeftChild(T,e)RightChild(T,e)LeftSibling(T,e)RightSibling(T,e)BiTreeEmpty(T)BiTreeDepth(T)Root(T)Value(T,e)P25PreOrderTraverse(T,Visit())InOrderTraverse(T,Visit())PostOrderTraverse(T,Visit())LevelOrderTraverse(T,Visit())PreOrderTraverse(T,Visit())26

InitBiTree(&T)Assign(T,&e,value)CreateBiTree(&T,definition)InsertChild(T,p,LR,c)InitBiTree(&T)27ClearBiTree(&T)DestroyBiTree(&T)DeleteChild(T,p,LR)ClearBiTree(&T)28完全二叉树丰满二叉树排序二叉树平衡二叉树二叉树的分类完全二叉树二叉树的分类29满二叉树：指的是深度为k且含有2k-1个结点的二叉树完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应123456789101112131415abcdefghij满二叉树：指的是深度为k且含有2k-1个结点的二叉树完全二叉30二叉树

的重要特性二叉树

的重要特性31性质1

在二叉树的第i(i≥1)层上至多有2i-1个结点性质132用归纳法证明归纳基础归纳假设归纳证明i=1

层时，只有一个根结点：

2i-1=20=1假设对所有的j，1≤j

i，命题成立二叉树上每个结点至多有两棵子树，则第i层的结点数

≤

2i-2

2=2i-1用归纳法证明i=1层时，只有一个根结点：假设对所有的33性质2

深度为k（k≥1）的二叉树上至多含2k-1个结点性质234证明

基于上一条性质，深度为k的二叉树上的结点数至多为

20+21++2k-1=2k-1证明基于上一条性质，深度为k的二35性质3

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1性质336证明设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1证明设二叉树上结点总数n=n0+n1+n237性质4

具有n个结点的完全二叉树的深度为

log2n

+1性质438证明设完全二叉树的深度为k则根据第二条性质得2k-1≤n<2k即k-1≤log2n<k因为k只能是整数，因此，k=log2n+1证明设完全二叉树的深度为k39性质5若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：性质5若对含n个结点的完全二叉树从40(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为

i/2

的结点为其双亲结点

(2)若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点(3)若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点(1)若i=1，则该结点是二叉树的根，41树的存储结构一、广义表表示法二、双亲表示法三、孩子表示法四、孩子兄弟表示法

树的存储结构一、广义表表示法42广义表表示法树的广义表表示(结点的utype域没有画出)广义表表示法树的广义表表示43ABCDEFG0A-11B02C03D04E25F26G5dataparent双亲表示法ABCDEFG0A-1datapare44ABCDEFG0A-11B02C03D04E25F26G4datafirstchild123456孩子链表表示法ABCDEFG0A-1datafirstch45ABCDEFGABCEDFGrootABCEDFG孩子兄弟表示法ABCDEFGAroot46孩子兄弟表示法

datafirstChildnextSibling孩子兄弟表示法datafirstChildnextSi47二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示二叉树的存储结构二、二叉树的链一、二叉树的顺48完全二叉树的一般二叉树的数组表示数组表示顺序存储表示完全二叉树的一般二叉树的49ABCDEF

ABDCEF

0123456789101112131401326ABCDEFABDC50

单支树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况单支树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费51ADEBCF

rootlchilddatarchild结点结构二叉链表ADEBCFrootlchilddata52链表表示链表表示53树的类型定义课件54ADEBCF

root

三叉链表parentlchilddatarchild结点结构ADEBCFroot三叉链表parent55二叉链表的静态结构二叉链表的静态结构56森林与二叉树的转换树的类型定义课件57森林转化成二叉树的规则树的类型定义课件58

若F为空，即n=0，则对应的二叉树B为空二叉树

若F不空，则对应二叉树B的根root(B)是F中第一棵树T1的根root(T1)，其左子树为

B(T11,T12,…,T1m)，其中，T11,T12,…,

T1m是root(T1)的子树；其右子树为B(T2,T3,…,Tn)，其中，T2,T3,…,Tn是除T1外其它树构成的森林若F为空，即n=0，则59二叉树转换为森林的规则树的类型定义课件60

如果B为空，则对应的森林F也为空

如果B非空，则

F中第一棵树T1的根为root；T1的根的子树森林(T11,T12,…,T1m)

是由

root的左子树LB转换而来，F

除了T1

之外其余的树组成的森林(T2,T3,…,

Tn)是由root的右子树RB转换而成的森林如果B为空，则对应的森林F也为空61森林与二叉树的转换森林与二叉树的转换62二叉树遍历(BinaryTreeTraversal)树的类型定义课件63

顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次问题的提出“访问”的含义可以很广，如：输出结点的信息等顺着某一条搜索路径巡访二叉树问题的提出“访问64

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题“遍历”是任何类型均有的操作，65对“二叉树”而言，可以有三条搜索路径1．先上后下的按层次遍历2．先左（子树）后右（子树）的遍历3．先右（子树）后左（子树）的遍历对“二叉树”而言，可以有三条搜索路径1．先上66设访问根结点记作V遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有前序VLR逆前序VRL中序LVR逆中序RVL后序LRV逆后序RLV层次遍历设访问根结点记作67前序遍历(PreorderTraversal)若二叉树为空，则空操作否则访问根结点(V)前序遍历左子树(L)前序遍历右子树(R)遍历结果-+

a

*

b-

cd

/ef前序遍历(PreorderTraversal)若二叉树为68若二叉树为空，则空操作否则中序遍历左子树(L)访问根结点(V)中序遍历右子树(R)遍历结果

a

+

b

*

c

-

d

-

e/

f中序遍历(InorderTraversal)表达式语法树若二叉树为空，则空操作中序遍历(InorderTrave69后序遍历(PostorderTraversal)若二叉树为空，则空操作否则后序遍历左子树(L)后序遍历右子树(R)访问根结点(V)遍历结果abcd

-*+

ef

/

-后序遍历(PostorderTraversal)若二叉树70层次遍历(LevelorderTraversal)从上到下，从左到右遍历结果-＋／a*

efb-cd层次遍历(LevelorderTraversal)71按给定的表达式建相应二叉树由前缀表达式建树例如:-×+abc/de由中缀表达式建树例如：(a+b)×c–d/e由后缀表达式建树例如：ab+c×de/-按给定的表达式建相应二叉树由前缀表达式建树由中缀表达式建树72对应前缀表达式-×+abc/de的二叉树abcde-×+/特点：

操作数为叶子结点运算符为分支结点对应前缀表达式-×+abc/deabcde-×73对应中缀表达式(a+b)×c-d/e的二叉树abcde-×+/特点：

操作数为叶子结点运算符为分支结点对应中缀表达式(a+b)×c-d/eabcde74对应后缀表达式ab+c×de/-的二叉树abcde-×+/特点：

操作数为叶子结点运算符为分支结点对应后缀表达式ab+c×de/-abcde-×75a+b(a+b)×c–d/ea+b×c分析表达式和二叉树的关系ab+abc×+abc×+(a+b)×cabcde-×+/a+b(a+b)×c–d/ea+b×c分析表达式和二叉76二叉树的计数由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树二叉树的计数由二叉树的前序序列和中序序列可以唯一地确定一77仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树

如果同时已知二叉树的中序序列“cbdaegf”，则会如何？

二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二78abcdefgcbdaegfaabbccddeeffggabcdefg^^^^^^^^先序序列中序序列abcdefgcbda79前序序列{ABHFDECKG}中序序列{HBDFAEKCG}前序序列{ABHFDECKG}80

如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树如果前序序列固定不变，给出不同的中序序列，可得到不同81问题是有n个数据值，可能构造多少种不同的二叉树？我们可以固定前序排列，选择所有可能的中序排列问题是有n个数据值，可能构造多少种不同的二叉树？82有3个数据{1,2,3}，可得5种不同的二叉树。它们的前序排列均为123，中序序列可能是

123，132，213，231，321有3个数据{1,2,3}，可得5种不同的二叉树83有0个,1个,2个,3个结点的不同二叉树如下有0个,1个,2个,3个结点的不同二叉树如下84具有4个结点的不同二叉树计算具有n个结点的不同二叉树的棵数Catalan函数具有4个结点的不同二叉树计算具有n个结点的不同二叉树的棵数C85树的遍历深度优先遍历树的先根次序遍历树的后根次序遍历广度优先遍历树的层次次序遍历树的遍历86

ABCDEFGHIJK先根遍历ABEFCDGHIJK后根遍历EFBCIJKHGDA层次遍历：ABCDEFGHIJKA先根遍历ABEF87

BCDEFGHIJK1．森林中第一棵树的根结点2．森林中第一棵树的子树森林3．森林中其它树构成的森林森林由三部分构成1．森林中第一棵树的根结点2．森林中88森林的先根遍历森林的二叉树表示若森林F为空,返回否则:

访问F的第一棵树的根结点

先根次序遍历第一棵树的子树森林

先根次序遍历其它树组成的森林森林的先根遍历森林的二叉树表示若森林F为空,返回89森林的后根遍历森林的二叉树表示若森林F为空，返回否则:

后根次序遍历第一棵树的子树森林

后根次序遍历其它树组成的森林

访问F的第一棵树的根结点 森林的后根遍历森林的二叉树表示若森林F为空，返回90森林的层次遍历森林的二叉树表示若森林F为空，返回否则:

依次遍历各棵树的根结点

依次遍历各棵树根结点的所有子女

依次遍历这些子女结点的子女结点

森林的层次遍历森林的二叉树表示若森林F为空，返回91二叉树的类定义树的类型定义课件92template<classType>classBinTreeNode{private:

BinTreeNode<Type>*LChild,*RChild;Typedata;};template<classType>classBinaryTree{ private:BinTreeNode<Type>*root;};template<classType>93二叉树前序遍历递归算法template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*current){if(current!=NULL){cout<<current→data;

PreOrder(current→LChild);

PreOrder(current→RChild);}}二叉树前序遍历递归算法94二叉树中序遍历递归算法template<classType>voidBinaryTree<Type>::

InOrder(BinTreeNode<Type>*current){if(current!=NULL){InOrder(current→LChild);cout<<current→data;

InOrder(current→RChild);}}二叉树中序遍历递归算法95二叉树后序遍历递归算法template<classType>voidBinaryTree<Type>::

PostOrder(BinTreeNode<Type>*current){if(current!=NULL){

PostOrder(current→LChild);

PostOrder(current→RChild);cout<<current→data;}}二叉树后序遍历递归算法96二叉树前序遍历非递归算法树的类型定义课件97template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*p){do{while(p!=NULL){cout<<p→data;

Push

(s,p);p=p→LChild;}if(!Empty(s)){p=pop(s);p=p→RChild;}}while((!Empty(s))||(p!=NULL))

}template<classType>98二叉树中序遍历非递归算法树的类型定义课件99template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*p){do{while(p!=NULL){Push

(s,p);p=p→LChild;}if(!Empty(s)){p=pop(s);cout<<p→data;p=p→RChild;}}while((!Empty(s))||(p!=NULL))

}template<classType>100

应用二叉树遍历的事例

应用二叉树遍历的事例101计算二叉树结点个数的一种方法template<classType>intBinaryTree<Type>::Size(BinTreeNode<Type>*t){if(t==NULL)return0;elsereturn1+Size(t→LChild)+Size(t→RChild);}计算二叉树结点个数的一种方法template<class102计算二叉树的高度template<classType>intBinaryTree<Type>::Depth(BinTreeNode<Type>*t){if(t==NULL)return0;elsereturn1+

Max(Depth(t→LChild),

Depth(t→RChild));}

计算二叉树的高度template<classType>103

线索二叉树

线索二叉树104遍历二叉树的结果是，求得结点的一个线性序列ABCDEFGHK先序序列

ABCDEFGHK中序序列

BDCAHGKFE后序序列

DCBHKGFEA遍历二叉树的结果是，ABCDEFGHK先序序列中序序列后序序105指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^

C^^B

E^指向该线性序列中的“前驱”和与其相应的二叉树，包含“线索”106对线索链表中结点的约定在二叉链表的结点中增加两个标志域LTag和RTag,并作如下规定:若该结点的左子树不空，则LChild域的指针指向其左孩子，且左标志LTag的值为0否则，LChild域的指针指向其“前驱”，且左标志LTag的值为1对线索链表中结点的约定在二叉链表的结点中增加两个标志域若该结107若该结点的右子树不空，则RChild域的指针指向其右孩子，且右标志RTag的值为0否则，RChild域的指针指向其“后继”，且右标志RTag的值为1如此定义的二叉树的存储结构称作“线索链表”若该结点的右子树不空，如此定义的二叉树的存储结构称作“线索链108LTag=0,LChild为指针,指向左孩子LTag=1,LChild为线索,指向前驱RTag=0,RChild为指针,指向右孩子RTag=1,RChild为线索,指向后继LTag=0,LChild为指针,指向左孩子109猜一猜,是哪一种线索二叉树猜一猜,是哪一种线索二叉树110后序序列

DBECA前序序列

ABDCE后序序列前序序列111带表头结点的中序线索二叉树带表头结点的中序线索二叉树112

寻找当前结点在中序下的后继寻找当前结点113if(p

RTag==1)if(p

RChild!=T.root)

后继为

p

RChildelse无后继else//p

RTag==0if(p

RChild!=T.root)

后继为当前结点右子树的中序下的第一个结点else出错情况ABDECFHIKGJLif(pRTag==1)ABDECFHIKGJL114

寻找当前结点在中序下的前趋寻找当前结点115if(p

LTag==1)if(p

LChild!=T.root)

前驱为p

LChildelse无前驱else//p

LTag==0if(p

LChild!=T.root)

前驱为当前结点左子树的中序下的最后一个结点else出错情况ABDECFHIKGJLif(pLTag==1)ABDECFHIKGJL116在前序线索化二叉树中寻找当前结点的后继在前序线索化二叉树中寻找当前结点的后继117在前序线索化二叉树中寻找当前结点的前趋在前序线索化二叉树中寻找当前结点的前趋118在后序线索化二叉树中寻找当前结点的后继在后序线索化二叉树中寻找当前结点的后继119在后序线索化二叉树中寻找当前结点的前趋在后序线索化二叉树中寻找当前结点的前趋120堆(Heap)template<classType>classMinPQ

{public:

Virtualvoid

Insert(constType&)=0;

VirtualType*RemoveMin(Type&)=0;}

最小优先级队列类的定义优先级队列每次出队列的是优先权最高的元素堆(Heap)template<classType121堆的定义完全二叉树的数组表示

Ki

K2i+1&&

Ki

K2i+2完全二叉树的数组表示

Ki

K2i+1&&

Ki

K2i+2堆的定义完全二叉树的数组表示完全二叉树的数组表示122最小堆的类定义template<classType>class

MinHeap

:publicMinPQ<Type>{

public:

MinHeap(int

maxSize)

const;

MinHeap(Type

arr[],int

n);~MinHeap(){

delete[]heap;}

const

MinHeap<Type>&

operator=(constMinHeap&R);

intInsert(constType

&x);

intRemoveMin(Type&x);

int

IsEmpty()const

{return

CurrentSize==0;

}

最小堆的类定义123intIsFull()const{

return

CurrentSize==

MaxHeapSize;

}

void

MakeEmpty(){

CurrentSize=0;

}private:

enum

{

DefaultSize=10};

Type*heap;

int

CurrentSize;

int

MaxHeapSize;

voidFilterDown(inti,int

m);

void

FilterUp(inti);}

intIsFull()const124堆的建立template<classType>MinHeap<Type>::MinHeap(int

maxSize){//根据给定大小maxSize,建立堆对象

MaxHeapSize=DefaultSize<maxSize

?

maxSize

:

DefaultSize;

//确定堆大小

heap=new

Type[MaxHeapSize];//创建堆空间

CurrentSize=0;//初始化}template<classType>MinHeap<Type>::MinHeap(Type

arr[],int

n){//根据给定数组中的数据和大小,建立堆对象

堆的建立template<classType>MinH125MaxHeapSize=DefaultSize<n

?

n

:

DefaultSize;

heap=new

Type[MaxHeapSize];

heap=arr;

//数组传送

CurrentSize=n;//当前堆大小

intcurrentPos=(CurrentSize-2)/2;//最后非叶

while(currentPos>=0){

//从下到上逐步扩大,形成堆

FilterDown(currentPos,CurrentSize);

//从currentPos开始,到CurrentSize为止,调整

currentPos--;

}}MaxHeapSize=DefaultSize126自下向上逐步调整为最小堆将一组用数组存放的任意数据调整成堆自下向上逐步调整为最小堆将一组用数组存放的任意数据调整成堆127树的类型定义课件128树的类型定义课件129树的类型定义课件130最小堆的向下调整算法template<classType>void

MinHeap<Type>::FilterDown(constint

start,constint

EndOfHeap){

int

i=start,

j=2*i+1;//j是i

的左子女Type

temp=heap[i];

while(j<=EndOfHeap){

if(j<EndOfHeap

&&

heap[j].key>

heap[j+1].key)j++; //两子女中选小者

if(temp.key<=heap[j].key)break;

else{heap[i]=heap[j];i=j;j=2*j+1;}

}

heap[i]=temp; }最小堆的向下调整算法131堆的插入template<classType>int

MinHeap<Type>::Insert(constType&x){//在堆中插入新元素xif(CurrentSize==MaxHeapSize)//堆满

{

cout<<"堆已满"<<endl;

return0;

}

heap[CurrentSize]=x;//插在表尾

FilterUp(CurrentSize);//向上调整为堆

CurrentSize++;//堆元素增一

return1;}堆的插入template<classType>int132template<classType>void

MinHeap<Type>::FilterUp(intstart){//从start开始,向上直到0,调整堆intj=start,

i=(j-1)/2;//i是j的双亲

Type

temp=heap[j];

while(j>0){

if(heap[i].key<=temp.key)break;

else{

heap[j]=heap[i];j=i;i=(i

-1)/2;}

}

heap[j]=temp;}template<classType>voidMin133最小堆的向上调整最小堆的向上调整134template<classType>int

MinHeap<Type>::RemoveMin(Type&x){

if(!CurrentSize){cout<<“堆已空

"<<endl;return0;}

x=heap[0];//最小元素出队列

heap[0]=heap[CurrentSize-1];

CurrentSize--;

//用最小元素填补

FilterDown(0,CurrentSize-1);

//从0号位置开始自顶向下调整为堆

return1;}template<classType>intMinH135

哈夫曼树

(HuffmanTree)

与

哈夫曼编码

哈夫曼树

(HuffmanTree)

与

哈136设给出一段报文CASTCASTSATATATASA字符集合是{C,A,S,T}，各个字符出现的频度(次数)是W＝{2,7,4,5}

若给每个字符以等长编码A:00T:10C:01S:11则总编码长度为(2+7+4+5)*2=36设给出一段报文137若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度A:0T:10C:110S:111它的总编码长度为

7*1+5*2+(2+4)*3=35比等长编码的情形要短若按各个字符出现的概率不同而给予不等长编码，可望减少138结点的路径长度

从根结点到该结点的路径上分支的数目结点间路径长度(PathLength)连接两结点的路径上的分支数结点的路径长度结点间路径长度(PathLength)139树的带权路径长度(WeightedPathLength,WPL)树的各叶结点所带的权值与该结点到根的路径长度的乘积的和树的路径长度树中每个结点的路径长度之和树的带权路径长度树的路径长度140

在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”,或“哈夫曼树”

(HuffmanTree)

在所有含n个叶子结点、并带相同141具有不同带权路径长度的二叉树哈夫曼树中，权值大的结点离根最近具有不同带权路径长度的二叉树哈夫曼树中，权值大的结点离根最PL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=72143构造哈夫曼树(以二叉树为例)(以二叉树为例)144

根据给定的n个权值{w1,w2,…,

wn}，造n棵二叉树的集合

F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；(1)根据给定的n个权值{w1,w2,…,145

在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(2)在F中选取其根结点的权值为最(2)146

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

重复(2)和(3)两步，直至F中只含一棵树为止(3)(4)从F中删去这两棵树，同时加入重复(21479已知权值W={5,6,2,9,7}5627527697671395279已知权值W={5,6,2,9,7}562751486713952795271667132900001111000110110111671395279527166713290000111100149哈夫曼树的构造过程哈夫曼树的构造过程150哈夫曼树的构造过程哈夫曼树的构造过程151

任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀前缀编码

利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短任何一个字符的编码都不是同一前缀编码152设给出一段报文CASTCASTSATATATASA字符集合是{C,A,S,T}，