《第五章二叉树》由会员分享，可在线阅读，更多相关《第五章二叉树（92页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 二叉树二叉树甭艺烘烘茨申餐欢与坚偏杏限抠汉才孽菜搞谤机萧窟陶算积窘蛆趴钨巨嘛第五章二叉树第五章二叉树 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。 5.1 树的定义和基本术语 定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅
2、有一个特定的称为根(Root)的结点；几化鲤安厦磊鉴董疹灾拽贝棘贼掌芹名黔恐恶霜俘欲韶遁视王讯抚鸦袁蛊第五章二叉树第五章二叉树(2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。详德劲湍师殷鹰悸每徒庭幼戳钥万罩译帆押巩蛹裔秉奖瓮县窥舒诱埂慈伸第五章二叉树第五章二叉树5.2 5.2 二叉树二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。5.2.1 二叉树的定义定义：二叉树是由n(n=0)个结点的有限集合构成
3、，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。淳暴掖牡匙朗烦女版乒擦鄂邓负倍蓖师其展荚罩念诺赔蔼懊衙完淡制追否第五章二叉树第五章二叉树二叉树的相关概念二叉树的相关概念 （1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点。度为0的结点称为叶结点，或者称为终端结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩
4、子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（5）路径、路径长度。如果一棵树的一串结点n1,n2,nk有如下关系：结点ni是ni+1的父结点（1i=1)。 采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定多所有的j，1=j=1).深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，： EkI=1（第i层上的最大结点数）= EkI=12i-1=2k 1 性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉
5、树中所有结点均小于或等于2，所以有：Nn0n1n2 (5-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：NB1。咏堰颐蔫浓洼纺荤伶梭嫌鬃惨弗扶驳荣岩苞厅牵逢测赋筑痊骋缆级攘堤欺第五章二叉树第五章二叉树由于这些分支都是由度为1和2的结点射出的，所有有： Bn1+2*n2 NB1n12n21 （52)由式（51）和（52）得到： n0+n1+n2=n1+2*n2+1 n0n21下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图5.9就是一棵满二叉树，对结点进行了顺序编号。把辟喷屯卞婚降坡迹
6、吵圾胆废鸽铰协轮斡授食寒趁罐癌使爆灸僵窥坤霹颠第五章二叉树第五章二叉树如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，2453671图5.9 满二叉树赢缄垄算爵债谚岩铆穿解唯惯朵粉士吧漏蕉绒评瓮脸痕歹破啸匠慷旗尹逆第五章二叉树第五章二叉树12345612345712367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图5.10 完全二叉树则称这样的二叉树为完全二叉树，图5.10（b）、(c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。冠灯荤饭乃宁占嗓烙燃埠命澈太薯胸校癸柴铰探用牧憨且谰镜竖疮迹宝倾第五章二叉树第五章二叉树完全二叉树
7、的特点是：（1)所有的叶结点都出现在第k层或k1层。 （2）对任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l1。 性质4：具有n个结点的完全二叉树的深度为log2n 1。符号 x 表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1 或 2k-1=n2k取对数得到：k1=log2nk 因为k是整数。所以有：k log2n 1。 束孵膘衷阜畦凯羚佰女牢纲炯迢平嫁瘫藤堵标岂喘述讫陶叭攀槐套喷肠昨第五章二叉树第五章二叉树性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第 log2n +1层，每层从左到右
8、),则对任一结点i（1=i1，则其双亲是结点 i/2 。 （2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。 增贝鲤禽奇钦咯账替服货春佑迂薪讼页告颐乞茁央益馅嫂傲隐散祥俭铸押第五章二叉树第五章二叉树 I/2iI+12i2i+1 2(I+1)2i+3I+12(I+1)2i+3i2i2i+1图5.11 完全二叉树中结点I和i+1(a)I和i+1结点在同一层 (b)I和i+1结点不在同一层如图5.11所示为完全二叉树上结点及其左右孩子结点之间的关系。暴瞬哟敲房蚌部蜡突皱涣沈撇诈贬札抛丸壁倘倪队奏痔景掂豹走骂茹
9、盒枷第五章二叉树第五章二叉树 在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。对于i1，可分为两种情况： （1）设第j（1=jn，则无左孩子：溃就寝喘朴观藩羽肝腕品质钎嫉注二洁殆鞠鱼猖次颐穆砧藐鲜毡谗右爵涤第五章二叉树第五章二叉树其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1n，则无右孩子。 （2）假设第j（1=j=log2n)层上的某个结点编号为i（2e(j-1)=i=2ej-1),且2i1
10、1时，如果i为左孩子，即2（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕。慷貉佐缅牵姓低频霹环拍铬往邮嚷颈抑摧场傀鸿风赡辟洁啄弱啊澳悉拨锤第五章二叉树第五章二叉树二叉树的抽象数据类型二叉树的抽象数据类型二叉树结点的ADT template class BinNodepublic: virtual Elem& val()=0; virtual void setVal(const Elem&)=0; virtual BinNode* left()=0; virtual BinNode* right()=0; virtual void
11、setLeft(BinNode*)=0; virtual void setLeft(BinNode*)=0 ; virtual bool isLeaf()=0;瘦苏绝从苹珠吠郝踊厨菌汽譬慑沽盏渗除讼盖铺丫辗性橙惦殖渝插缀计级第五章二叉树第五章二叉树5.2.3 二叉树的存储结构1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtype sqbitreemax-tree-size;Sqbi
12、tree bt 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！ 剧倒炕似侧旷锤笨哗褥樊故甭扎涅疮第植凑俄顽图玄软踢按涡钡尼袱惧蝇第五章二叉树第五章二叉树ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树完全二叉树abcdefghijkl贫蜗伙镐枕菜历搔酮癸挣枯擎巳浆痢亿拓宫尿良畸林性帛还忙愤血栽鹅卷第五章二叉树第五章二叉树ABCDEFG 表示该处没有元素存在仅仅为了好理解A
13、BCDEFG一般二叉树一般二叉树睛褥攻雄敲枯热涪债静驯碾璃铜更剔蕴悄帧肌竭双视比吁取敛妆澎警秽磊第五章二叉树第五章二叉树（2）二叉树的二叉动态链式存储表示二叉树的二叉动态链式存储表示1、结点结构和示例leftChild data rightChildABCDEFrootABCDEFroot舒桶扬兵崖询们掉崩咕俱告闷寻莎踢骇瞒畜铅亦法斤谁饰贷联葫毗松罪歼第五章二叉树第五章二叉树二叉树的二叉链表存储表示template class BinaryTree;template class BinTreeNode firend class BinaryTree;private: Elem data; Bi
14、nTreeNode * lchild; BinTreeNode * rchild;public: BinTreeNode()lchild=rchild=NULL; BinTreeNode(Elem e,BinNodePtr*l=NULL, BinNodePtr*r=NULL) data=e; lchild=l; rchild=r; BinTreeNode() 杀陨沾朝筒箩怒垒蹄茂辩汞幸宽矾颤狙怜展诽葵腹烧琅扦碳刊甚宙热泄仲第五章二叉树第五章二叉树二叉树的二叉链表存储表示二叉树的二叉链表存储表示Elem val()return data;void setVal(const Elem e)data
15、=e;inline BinTreeNode* left()return lchild;inline BinTreeNode* right()return rchild;void setLeft(BinTreeNode* left)lchild=left;void setRight(BinTreeNode* right)rchild=right; bool isLeaf() return (lchild=NULL)&(rchild=NULL);有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域;聪饥朔趟模围劈殴础汞灵嵌佑覆
16、书森棕诞浩肆脊温空君嘎柬表堵冤弹币墟第五章二叉树第五章二叉树template class BinaryTreeprivate: BinTreeNode *root; Elem Refvalue; BinTreeNode *Parent (BinTreeNode *start, BinTreeNode *current); void Traverse (BinTreeNode *current, ostream & out) const void destroy (BinTreeNode *current);public: Virtual BinaryTree (Elem value): roo
17、t (NULL), Refvalue (value) Virtual BinaryTree( ) destroy (root); Virtual bool IsEmpty( ) return root = = NULL ? true :false; Virtual BinTreeNode *Parent (BinTreeNode *current) return Parent (root, current); 扣馋雅颁俭驯状芽兜旨骂巢玛拱河茧拢珠盟碉截寞座踞红组菩赫聂娄娥灵第五章二叉树第五章二叉树3、部分成员函数的实现template void BinaryTree : destroy (Bi
18、nTreeNode *current) /删除以current为根的子树 if (current != NULL) destroy (current - leftChild); /删除current的左子树 destroy (current - rightChild); /删除current的右子树 delete current; /删除current 算法中，、两递归调用语句可互换，它只关系到左右子树中，哪一个先删，哪一个后删。 语句不能同和语句互换，因为那样将导致一个子树甚至两个子树无法删。皮帖害唁抄蒸践诽烙犹盼国吻嘿癌市垫蛆黄链坠腿婆鹤塔邵正俯戌葛卸听第五章二叉树第五章二叉树templa
19、te BinTreeNode *BinaryTree : Parent (BinTreeNode *start, BinTreeNode *current) if (start = = NULL | | current = = start) return NULL; if (start - leftChild = = current | | start - rightChild = = current) return start; /start是双亲 BinTreeNode *p; if (p = Parent (start - leftChild, current) != NULL) ret
20、urn p; /在左子树找 else return Parent (start - rightChild, current); /在右子树找template void Binary Tree : Traverse (BinTreeNode *current, ostream & out) const /搜索并输出根为current的二叉树 if (current != NULL) out data leftChild, out); /搜索并输出左子树 Traverse (current - rightChild, out); /搜索并输出右子树率椭竟发斥没挽烂多浴隶漂南狄焚犁畦肢舍干雄母涅舰撅
21、谁笺湃迂彬缔研第五章二叉树第五章二叉树5.3 5.3 遍历二叉树（遍历二叉树（Traversal Binary TreeTraversal Binary Tree）一、一、TBT概述概述1、定义 按某种次序，访问所有结点，使每个节点都被访问且尽访问一次的运算叫TBT。 “访问”包括输出结点值，修改值，统计等以不破坏BT的结构为原则。 TBT是对二叉树进行运算的基础性操作。绘听鸭掏挛割沤勺但仿院榴赣弗闪化息骤该鼎吹孙匿迂仗挞猛恰简谓赤血第五章二叉树第五章二叉树一、一、TBT概述概述2、次序（V根，L左子树，R右子树） 先序遍历 中序遍历 后序遍历先右后左：VRLRVLRLV先左后右：VLRLVR
22、LRVbtABCDEFGHIJVLR输出序列：A B D E G HI J C FLVR输出序列：D B G EI H J A C FLRV输出序列：D G I JH E B F C A伐毙紧娟宅光琴较绍幢苫士聋铝邱浊孔伤伺害殆猜辊楞暮适七悯裤衬立珐第五章二叉树第五章二叉树二、二、TBT的递归算法的递归算法1、中序遍历（ inorder traversal）template void BinaryTree : InOrder ( ) InOrder (root); /公共函数，调用私有函数完成遍历template void BinaryTree : InOrder (BinTreeNode *
23、current) if (current != NULL) /当current = = NULL，则递归终结 InOrder (current - leftChild); /中序遍历左子树 cout data; /访问根结点 InOrder (current - rightChild); /中序遍历右子树/abcdef 对 a+b*(c-d)-e/f 表达式的语法树，中序遍历得到其中缀表示： a + b * c d e / f 奠迹瞩泄骏册妇骋喷丫酚忆虫滁俭醛锡溉桥哇虑惨请甩日嗅夫淤召盏酗窒第五章二叉树第五章二叉树2、先序遍历（ preorder Traversal）template void
24、 BinaryTree : PreOrder (BinTreeNode *current) /私有函数 if (current != NULL) cout data; PreOrder (current - leftChild); PreOrder (current - rightChild); /abcdef 对表达式a+b*(c-d)-e/f 的语法树进行先序遍历得到其前缀表示： + a * b c d / e f二、二、TBT的递归算法的递归算法傈盏尺瞻按译吕唇雹剧铲贼驰谬掠熊轮窜彝助冗它蔼第蜜鹅麓廖播低符掏第五章二叉树第五章二叉树3、后序遍历（ postorder traversal）
25、template void BinaryTree : PostOrder (BinTreeNode *current) /私有函数 if (current != NULL) PostOrder (current - leftChild); PostOrder (current - rightChild); cout data; 二、二、TBT的递归算法的递归算法/abcdef 对表达式 a+b*(c-d)-e/f 的语法树进行后序遍历得到其后缀表示： a b c d * + e f / 赖锦瓜磷鼻灯葫隐抿娘峻陡帝祁叫屋执齐畏魁坟围播脯樊捉买辞博钨咱褂第五章二叉树第五章二叉树三、三、TBT的非递
26、归算法的非递归算法1、递归算法中栈的使用TBT递归算法的简化traversal (BinTreeNode *current) if (current != NULL) traversal (current - leftChild); traversal (current - rightChild); 上力晶垢醚赎供法浪沙乃珐窗袜玛舱径乐劝为藻样缚伏葬吠驻俺剂殖皆香第五章二叉树第五章二叉树三、三、TBT的非递归算法的非递归算法1、递归算法中栈的使用执行过程中栈的情况和current的变化举例当左向递归则current的值进栈若current = = NULL，则出栈，current以栈顶值去执行
27、右向递归直到栈空（top = -1）和current = = NULL为止currenttopad1ad2ad3ad4ad5stackAB C DE ad1ad2ad3ad4ad5-1 0 1 2 3俩俐僳赂擞浑裙雨卒侮琴强付汉刚蚊宅毛圆换跟鲜偷扦卤缸晓答莫纤境杯第五章二叉树第五章二叉树2、利用栈的前序和中序遍历非递归算法template void BinaryTree : PreOrder ( ) stack BinTreeNode * st; BinTreeNode *p = root; do while (p != NULL) cout data; st. Push (p); p = p
28、 -leftChild; if ( St. length()!=0) st. pop (p ); p = p - rightChild; while (p != NULL | | st.length ( )!=0);算法描述 p不空则p进栈，沿左子树方向传递指针 若p空但栈不空，出栈，p以栈顶值沿右子树方向传递指针 循环下去，直到p和栈都空为止执行中栈的情况和指针的变化与递归程序相同对于中序遍历只需调整输出语句位置即可三、三、TBT的非递归算法的非递归算法削严伍异挛栖携掐啥校讲蛆宗褥筐闸暂暑鲸横既醇料奥烹协竣胸仅矛锭累第五章二叉树第五章二叉树3、层次遍历template void Binary
29、Tree : LevelOrder ( ) queue BinTreeNode * qu; BinTreeNode *p = root; qu.Enqueue(p); while (qu.DeQueue (p ) cout data leftChild != NULL) qu.EnQueue (p - leftChild); if (p - rightChild != NULL) qu.EnQueue (p - rightChild);三、三、TBT的非递归算法的非递归算法普滩苗戎窄眺布男裙毁彪甚学锰钳欧拔万物谊抖饭惑摩傀孽响氰枕饺函阻第五章二叉树第五章二叉树层次遍历是指直上至下，从左到右访问
30、结点只有采用队列来存放结点地址才能实现层次遍历3、层次遍历frpad1ad2ad3ad4ad5ad60 1 2 3 4 5 6 7ABCDEFrootad1ad2ad3ad4ad5ad6任载妻完啃另让鳃派池邵链欲怔盟模鼓熟佐面轰幕鹃抵概语睬饵扁素涕基第五章二叉树第五章二叉树5.4 5.4 线索化二叉树线索化二叉树一、概述一、概述1、问题提出 遍历是二叉树最基本的运算，为避免再次遍历的麻烦，可将首次遍历得到的信息存于一个线性结构中。 具有n个结点的链式存贮的二叉树中，有n+1个链域是空的，能否充分利用这些空的链域来存放结点的前趋指针和后继指针呢？着品天字樟鉴窗熏忻桐凄诛灌位忽跋乐畸各仪篮藻扯殷艺
31、温贝揪洛挨扁荆第五章二叉树第五章二叉树一、概述一、概述2、实现策略结点中增加两个标记域 两标记域取值范围是0，1。各只占一个二进制位，只增加很少的额外空间开销。rightChildleftChild leftThread data rightThread指向左孩子0指向前驱1指向右孩子0指向后继1斤挠因怎睦私蔚巍恤玲颠碌庚奈皂俱泽栏炭褒沈厌魔哦帧府哼舆炯紧旧走第五章二叉树第五章二叉树3、线索二叉树 指向前驱和指向后继的指针叫做线索（Thread）。 具有线索的二叉树叫做线索二叉树。 因遍历的次序有三种，所以线索二叉树也分前、中、后序这三种。 中序遍历线索二叉树结构示例 若根的左子树不空，侧其最
32、左下角的结点为中序遍历的第一个结点，否则根为中序遍历的第一个结点。 若根的右子树不空，侧其最右下角的结点为中序遍历的最后一个结点，否则根为中序遍历的最后一个结点。0E0 0B0 1F0 0D1 1G1 1C1 1A1 rootEDGrootBAFCNULLNULL贮眶行晃邮惫验水粱孽堑粮租尤赚傻赢淘兽劳体侯邵奄瘸搂诈寸女莹沈描第五章二叉树第五章二叉树二、中序线索二叉树的类定义二、中序线索二叉树的类定义1、类声明template class ThreadTree;template class ThreadNode friend class ThreadTree ;private: int lef
33、tThread, rightThread; ThreadNode * leftChild, rightChild; Elem data;public: ThreadNode (const Elem item) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) Elem getData ( ) const return data;蓄酷帛玛窑夫众让曰须试魂秉坝卫疡寡办汞潘袜铬苑削囊妨层澈炮扫跌坝第五章二叉树第五章二叉树template class ThreadTree privat
34、e : ThreadNode *root; InThread (ThreadNode *current, ThreadNode *pre);public : ThreadTree( ) : root(NULL) ; ThreadNode *First(ThreadNode *current); ThreadNode *Last(ThreadNode * current); ThreadNode *Next(ThreadNode *current); ThreadNode *Prior(ThreadNode *current); void Inorder( ); /从第一个结点开始沿着后继方向遍
35、历二叉树 房墒阮电兔猖九异法岸断幸伶痕乃检蔬俗攘尖咳揉嫂辕宛驭躁裤弄膀蒲够第五章二叉树第五章二叉树2、成员函数的实现template ThreadNode * ThreadTree: First(ThreadNode * current) /返回以current为根指针的线索二叉树中序序列下的第一个结点 ThreadNode * p = current; while(p - leftThread = = 0) p = p - leftChild; /找最左下角的结点 return p;template ThreadNode * ThreadTree : Next (ThreadNode * c
36、urrent) ThreadNode *p = current - rightChild; if (current - rightThread = = 0) return first (p); else return p;currentpnext补结嘶凤尉焰蝇永歇愚品芋箕残剿凋防饶味滤失悔蛰亚羔碧韶皖刻棱贯木第五章二叉树第五章二叉树template ThreadNode * ThreadTree: last(ThreadNode * current) ThreadNode * p = current; while(p - rightThread = = 0) p = p - rightChil
37、d; /找右下角结点 return p;template ThreadNode * ThreadTree : Prior (ThreadNode * current) ThreadNode *p = current - leftChild; if (current - leftThread = = 0) return last (p); else return p;pcurrentprior伏圃难琴缮拔蘸哲遁惠类关汝谆虚果讫聋郴遭词汛歉荧砰淖狂孕忘珍幕像第五章二叉树第五章二叉树template void ThreadTree : InOrder ( ) ThreadNode * p;/在线索二
38、叉树中进行中序遍历 for (p = first(root); p != NULL; p = Next(p) cout data endl; template void ThreadTree : InThread (ThreadNode * current, ThreadNode * pre) /通过中序遍历对以current为根的二叉树进行线索化 if (current != NULL) InThread (current - leftChild, pre); /左子树线索化 if (current - leftChild = = NULL) current - leftChild = pr
39、e; current - leftThread = 1; /建立当前结点的前驱线索 if (pre != NULL & pre - rightChild = = NULL) pre - rightChild = current; pre - rightThread = 1; /建前驱的后继线索 pre = current; InThread (current - rightChild, pre); /右子树线索化筏喳腰鹏拓劈绚奥泽违狠沏谗宫奖俄庶霸仅赫杠鸯鉴抒重修逆日鲁喻蜕浦第五章二叉树第五章二叉树5.5 二叉搜索树（二叉搜索树（Binary Search Tree）一、基本概念一、基本概念1
40、、定义或是空、或是具有下列性质的二叉树：每个结点有一个作为搜索依据的关键码（Key）。左子树上所有关键码小于根结点关键码。右子树上所有关键码大于根结点关键码。2、举例中序遍历结果：09，17，23，45，53，65，78，81，87，94显然是有序的，故又称二叉排序树。53658187094523177894厘简彼剥堑掩虚凯貉舵疽槛舅钞奥须澈控呻搜穷步札外戌识喉铬琅弥倔址第五章二叉树第五章二叉树一、基本概念一、基本概念 3、BST是基于二叉树的动态搜索结构，其删除和插入结点可能要改变树的结构。 4、BST类定义特点 类定义基于二叉链存贮表示 与一般二叉树类定义十分相似 可以继承一般二叉树类的定
41、义 基本运算Find, Insert 和 Remove 都用递归实现所以在类定义中包括私有和公用两种性质的声明坤旁宽奶演兑漫澳膛焦套墓餐斗华碘翼芋脸件钩寇枢辽粳引陪蓬幕明珊舵第五章二叉树第五章二叉树二叉查找树的二叉查找树的C+类说明类说明template class BST: public Dictionaryprivate: BinTreeNode * root; Elem RefValue int nodecount; void clearhelp(BinTreeNode*); BinTreeNode* inserthelp(BinTreeNode*,const Elem&); BinTr
42、eeNode* deletemin(BinTreeNode*,BinTreeNode*& ) ; BinTreeNode* removehelp(BinTreeNode*, const Key&, BinTreeNode*&); bool findhelp(BinTreeNode*, int) const; void printhelp(BinTreeNode* ,int) const;锰蔬钞招沉靶肤饶卞冶汞动酣颈膛近陛挡伴蕉仿猿摔熔湿姻魁昧佳竣翔镶第五章二叉树第五章二叉树public: BST( ) root=NULL; nodecount=0; BST()clearhelp(root);
43、void clear()clearhelp(root); root=NULL; nodecount=0; bool insert(const Elem& e) root=inserthelp(root,e); nodecount+; return true; bool remove(const Key&K, Elem& e) BinTreeNode*t=NULL; root=removehelp(root, K, t); e=t-val(); nodecount-; delete t; return true; bool removeAny(Elem& e) if(root=NULL) ret
44、urn false; root=deletemin(root, t); e=t-val(); delete t; nodecount-; return true;哎迷稳炕垒罪果路骆内纳匹峨游烤辽频奋僻腋套溺鬃忱悲皮罕吨蒙利鹏冤第五章二叉树第五章二叉树 bool find(counst Key& K, Elem& e) const return findhelp(root, K,e); int size()return nodecount; void print()const if(root=NULL) count“The BST is empty.n”; else printHelp(root
45、, 0); ;刚迹巷伺腋峪灶灿嗽恋吻杜臂董述田巳派户拼帽盯环兽掘糊玲诫盔桩嗽铁第五章二叉树第五章二叉树二、二、BST上的搜索上的搜索1、基本方法从根开始将给定值 x 与结点值进行比较若 x 小，沿着左子树继续搜索若 x 大，沿着右子树继续搜索若与 x 等则成功返回结点地址，若为空则失败2、举例 x = 2353658187094523177894 成功，比较次数为4 x = 88 失败，比较次数为4 比较次数不大于 h + 1摩合慧管椎椭拱挫中戊涉傀崇蹦城砒碌枚庄挎绍壮砧贫斜繁霄缄屎酪球谱第五章二叉树第五章二叉树3、递归算法template bool BST:findHelp (BinNode
46、*subroot, constKey &K,Elem&e) const if (subroot = = NULL) return false; else if (KEComp:lt(K,subroot-val() return findHelp (subroot-left(),K,e); else if (KEComp:gt(K,subroot-val() return findHelp (subroot-rightt(),K,e); else e=subroot-val(); return true; 该算法的递归调用语句都于程序的最尾，称为尾递归 返回时返回到上一层调用处的下条语句去执行
47、因为是最尾语句，程序结束，不必用栈保存返回地址和局部变量的值 该算法可以不用栈，采用迭代方法改写成非递归程序二、二、BST上的搜索上的搜索添储鼠鸯储贰捅笨讽契噶嫡糟沏务惰城沫试迄九查徒蔽俯介嫁久试袋棘焙第五章二叉树第五章二叉树4、迭代算法template bool BST:findHelp (BinTreeNode*subroot, constKey &K,Elem&e) if (subroot != NULL) BinTreeNode * temp = subroot; while (temp != NULL) if (KEComp:eq(K, temp-val() e=temp-val()
48、; return true; if (KEComp:gt(K, temp-val() temp = temp -right();else temp = temp - left(); return false; 一般对尾递归或单向递归的情形，都可利用迭代方法，不使用栈将递归过程改为非递归过程二、二、BST上的搜索上的搜索胰岳树受黑蓬荒掩狮眠呐辽碑陋霖啥疥越库薪楞你丛布拖嫉赡瓮淄挥抡愤第五章二叉树第五章二叉树三、三、BST中的插入中的插入1、方法先搜索BST中有无该结点，只有无才插入插入是作为叶子插入，插入后仍满足BST插入位置应是搜索操作停止（指针ptr为空）的地方2、算法template Bi
49、nNode* BST: inserthelp(BinNode* subroot, const Elem& val) if (subroot = NULL) / Empty: create node return new BinNodePtr(val,NULL,NULL); if (EEComp:lt(val, subroot-val() subroot-setLeft(inserthelp(subroot-left(), val); else subroot-setRight( inserthelp(subroot-right(), val); / Return subtree with no
50、de inserted return subroot;志眯乱果徊轨益枷舶窥蝗塞鄙襟阑疡鸟碗仓写豪丈碟确缝录范吭萄陇妨掐第五章二叉树第五章二叉树3、建BST 逐次输入关键码序列建一棵BST，是从空开始逐步插入结点 每次从根开始搜索插入位置，然后将新结点作为叶子插入 关键码集合相同但输入序列不同得到的BST也不同若输入次序：81, 65, 78, 94, 87, 88, 23, 45 , 09, 17, 538187172378096594455388三、三、BST中的插入中的插入脚弧紫料奖塌卤穴些藤姓思贸吃畴镑晰崇授罐奎铡湃惨似釜牲冯烃撵馏吭第五章二叉树第五章二叉树四、四、BST中的结点删除中的
51、结点删除1、原则删除结点所断开的链要重新接起来删除链接后仍是BST重新链接后树的高度不增加2、方法 被删结点为叶子，只需将双亲结点的相应指针置为空 被删结点无右子树，拿左孩子结点顶替它的位置 被删结点无左子树，拿右孩子结点顶替它的位置 被删结点左右子树都有，在右子树中找中序遍历第一个结点，用它的值填补到被删结点，然后再来删这个结点 结点删除是一个递归的过程惰芬敞来薛葛揉挺粗毅酋混渭编呈感婆殃乖邻座贺瘟筏顾蓑扁趾门坞辨雌第五章二叉树第五章二叉树3、有左右子树的结点删除举例 删除关键码78的结点 右子树中序第一结点是8181复盖7881结点无左子树，用右孩 子88顶替536581940945231
52、7788881四、四、BST中的结点删除中的结点删除8188唁旱邀炎捶套赦比础淋温麦乐火陷品玉韦颤坊瑟碗峙入搅衰嘉商蛊瞎数形第五章二叉树第五章二叉树template BinTreeNode* BST:deletemin(BinTreeNode*subroot,BinTreeNode*&min)if(subroot-left()=NULL) min=subroot; return subroot-right();else subroot-SetLeft(deletemin(subroot-left(),min) template BinTreeNode* BST: removehelp(BinT
53、reeNode*subroot, constKey&K,BinTreeNode*&t) if(subroot=NULL)return NULL;else if(KEComp:lt(K,subroot-val() subroot-setLeft(removehelp(subroot-left(),K,t); 氏剃闸经挟斑柔婴昭纳忠云讣线辐容还次孙芽滓贡曼颜溺集旅女平戚羔烛第五章二叉树第五章二叉树else if(KEComp:gt(K,subroot-val() subroot-setRight(removehelp(subroot-right(),K,t);else BinTreeNode*te
54、mp; t=subroot; if(subroot-left()=NULL) subroot=subroot-right(); else if(subroot-right()=NULL)subroot=subroot-left(); else subroot-setRight(deletemin(subroot-right(),temp); Elem te=subroo-val(); subroot-setVal(temp-val(); temp-setVal(te); t=temp return subroot;琶久魄精什僚绘辗炼渡忍辐忘阅捍尘饶瑟任专看没窄翌坷羹囊恭飞勺凝烟第五章二叉树第五
55、章二叉树5.6 AVL树树一、一、AVL树（高度平衡的树（高度平衡的BST）概念）概念 1、定义AVL或是空树，或是具有下列性质的BST：它的左、右子树都是AVL树，且左右子树的高度之差的绝对值不超过1。2、举例 是二叉搜索树 树和所有子树的左右子树高度之差绝对值不超过1 属AVL树1115142639718161000000013、平衡因子（balance factor） 结点右子树高度减去左子树高度所得高度差 AVL树中所有结点的平衡因子只能取0，1，1 AVL树的ASL可保持在O(log2n)超霄搭塞龚鼻拄渍川左转熄抵员仪乔荆缝晋陶谭问灭唇沥氯遵慢姐嫌允错第五章二叉树第五章二叉树二、平衡
56、化旋转二、平衡化旋转 1、向AVL树插入结点可能造成不平衡，此时要调整树的结构使之重新达到平衡 2、平衡化旋转方法 从插入位置沿通向根的路径回溯检查各结点的平衡因子 若发现不平衡结点，则从该结点起沿刚才回溯路径取直接下两层结点 若三个结点在一条直线上，则采用单旋转进行平衡化；若三结点在一条折线上，则采用双旋转进行平衡化蜜冰瞬拱臼哥搅腔论晚瞻浪频萝恫珊碟烛习雀辖苍算绳迪布思铱缸就藤装第五章二叉树第五章二叉树3、平衡化旋转示例左单旋转hhhABCDE01(a)AVL树hhh+1ABCDE12(b)E子树中插入结点hhh+1ABCDE00(c)左向旋转后的AVL树二、平衡化旋转二、平衡化旋转销扰夸媒
57、跋拜瞅悟莆泥绰骑驰实犀挪减玩掣乔拌淮坏估行远尘彩娟奸埠聂第五章二叉树第五章二叉树右单旋转hhhABCDE0- 1(a)AVL树hhh+1ABCDE- 1- 2(b)D子树中插入结点hhh+1ABCDE00(c) 右向旋转后的AVL树3、平衡化旋转示例二、平衡化旋转二、平衡化旋转诸酱矗慰营事裁岂靠考附楚呀揪诊炬号固樱鸽妥浸赦尽顾惧业兽屠绢侍喀第五章二叉树第五章二叉树先左后右双旋转hhh-1hABCDEFG插入(a)F子树插入结点高度变为h- 21- 1hhh-1hABCDEFG(b)绕E，将B逆时针转后hhh-1hABCDEFG(c)绕E，将A顺时针转后03、平衡化旋转示例二、平衡化旋转二、平衡
58、化旋转往赤穿置促戚知井章诚论窑拓驮逝岛讣衡氢迎摸裙剩塑值蛹眶谦拨盅救啼第五章二叉树第五章二叉树先右后左旋转hhh-1hABCDEFG插入(a)G子树插入结点高度变为h21- 1hhh-1hABCDEFG(b)绕D，C顺时针转之后hhh-1hABCDEFG(c)绕D，A逆时针转之后03、平衡化旋转示例二、平衡化旋转二、平衡化旋转录吝堰欧满疤百俱荧撬酿泳水捎兔桅货夏牵暇兽猩噎赐烁雀压港楷肘薄锚第五章二叉树第五章二叉树三、三、AVL树的建立树的建立 对于一组关键码的输入序列，从空开始不断插入结点，最后构成AVL树 每插入一个结点后就应判断从该结点到根的路径上有无结点发生不平衡 如有不平衡问题，利用旋
59、转方法进行树的调整，使之平衡化 建AVL树过程是不断插入结点和必要时进行平衡化的过程符东玄打己像疤轮卑严我袱瞬资博晦跺辊筑梳电罩妹蛆势黍丁睫铜累稗卸第五章二叉树第五章二叉树5.7 5.7 堆（堆（HeapHeap）一、堆的定义1、什么是堆？ 若有n个关键字的集合K=k0,k1,k2, ,kn-1将其所有元素按完全二叉树的顺序存贮方式存于一个一维数组中，并且满足以下条件，则该集合称为最小堆（或最大堆）。 kik2i+1和kik2i+2 或 kik2i+1和kik2i+2 (其中，i = 0,1, (n 2) / 2 )举例09 17 65 23 45 78 87 53 31 0 1 2 3 4
60、5 6 7 8最小堆最小堆87 78 53 45 65 09 31 17 23 0 1 2 3 4 5 6 7 8最大堆最大堆091765234578875331012345678堆顶元素值最小堆顶元素值最小877853456509311723012345678堆顶元素值最大堆顶元素值最大赚碳冈趣茂峻禽瓶扦羞狼卯控额钎饰这橇式太宪俊闪勃仟饼循兄烧咱筷率第五章二叉树第五章二叉树2、最小堆的类声明template class MinHeap private : Elem * heap; /存放堆元素的数组 int n; /堆当前元素个数 int size; /堆最多允许元素个数 void sift
61、down (int i) public : MinHeap (Elem* h, int num ,int max) /构造堆 Heap=h; n=num; size=max; buildHeap(); int heapsize() const return n; MinHeap( ) delete heap; bool Insert (const Elem & ); bool RemoveMin (Elem & ); bool isLeaf(int pos) constreturn (pos=n/2)&(pos=0; i-) siftdown(i); ;煮醛租兔膀被蓖乞米毕芭虏匿魔盯芋阉纺克犊
62、跺洁债伍十砌那纷郎乒高羹第五章二叉树第五章二叉树二、堆的建立二、堆的建立1、自下向上逐步调整建堆的举例ij531778094587652331012345678i = (n 2) / 2 = 3庄磷徊拢厘郊碴鼓真竣曼旧嘿蛀吁诚睦碎滩梦艘藐蝉泡凡嘉翰泞息坚剐兑第五章二叉树第五章二叉树ij531778094587652331012345678i = 2二、堆的建立二、堆的建立1、自下向上逐步调整建堆的举例6578神五惩髓滚靳秘韭簿吾琴咐朽纵异拱钧荡奠配恼孤邑糯墅萨吞郑墒匀摸邮第五章二叉树第五章二叉树ij531765094587782331012345678i = 1二、堆的建立二、堆的建立1、自下
63、向上逐步调整建堆的举例0917ij时埔廉购桅盯抉么甸宾房瘤艾轻蝇敢孰锑薄涡土多圾书咒诲铸豪瓦木圃枯第五章二叉树第五章二叉树ijij二、堆的建立二、堆的建立1、自下向上逐步调整建堆的举例ij530965174587782331012345678i = 0095317532353对第i个关键字进行筛选的要点：在第（2 i + 1）和（2 i + 2）中选小者定为第j若第I大于第j则交换向下继续：i = j，j = 2 i + 1，重复、，直到j(n 1)艳街鹅翻紫娥惰权蚂贪严漆琶彰盟詹盅衍签劝女淌星洱笔诣卸辛侈彪翼试第五章二叉树第五章二叉树向下筛选的算法template void MinHeap
64、:siftDown(int pos) while(!isLeaf(pos) int j=leftchild(pos); int rc=rightchild(pos); if(rcn)&Comp:gt(Heapj,Heaprc) j=rc; if(!Comp:gt(Heappos,Heapj) return; swap(Heap, pos, j); pos=j; 驱虞渣妹氛肉维迎氟激缺惧涛坯岔诲貌翌囊钵治乒全屈萧撒泌掌缺帐林寄第五章二叉树第五章二叉树三、堆的插入与删除三、堆的插入与删除1、插入插入是插到最小堆的后面，这样整体可能不是堆了。为了再成堆，要从插入元素的双亲开始逐层向上筛选。向上筛选举
65、例091765234578875331012345678(a)筛选示意图119091165231778875331(b)筛选后45乎肛亥蛇痈超全蹿灾当概贵固咐芹赡凡奏轧体葫胺念舷部膨拉扼士届呀补第五章二叉树第五章二叉树 template bool MinHeap : Insert(const Elem & val) if (n = = Size) return false; int curr=n+; while(curr!=0)&(Comp:lt(Heapcurr,HeapParent(curr) swap(Heap,curr,parent(curr); curr=parent(curr);
66、return true;三、堆的插入与删除三、堆的插入与删除1、插入茹丈辞眺胰怨尽救输汉抽证艾沧肾欲予软恿枯熔剥滚霓著但彪恶亡俐粳葫第五章二叉树第五章二叉树2、删除 删除是指删除最小关键字者，即堆顶元素，也就是数组中的0号元素。 删除之后常将堆底元素，即原来的第（n 1）号关键字置于堆顶处，然后元素个数减1。 删除处理后，新的序列常常不是堆了，为此要调整重建堆。 因为原来已是堆，而现在变更的只是0号位上的元素，所以只需对0号位由上往下进行筛选就可以重建堆。 删除算法templat bool MinHeap : RemoveMin(Elem &it ) if (n=0) return false
67、; swamp(Heap,0,-n); if(n!=0) siftdown(0); it=Heapn; return true;三、堆的插入与删除三、堆的插入与删除批抠吭趴桔释嘻歇绕茹详诈氰颤张幌涧禄碰喝快纹碘酬晨窥恼舵凹佰弥窥第五章二叉树第五章二叉树template bool MinHeap:remove(int pos,Elem& it) if(pos=n) return false; swap( Heap, pos, -n); while(pos!=0)&(Comp:lt(Heappos,Heapparent(pos) swam(Heap,pos,parent(pos); siftdow
68、n(pos); it=Heapn; return true;蒋滇靡柒党键耙蒸驶屹卓祖藻悍虞枕理猖魄恢吴薪共臀疆殖穗铸读翔嚎形第五章二叉树第五章二叉树5.8 5.8 霍夫曼树霍夫曼树一、树的路径长度（一、树的路径长度（PL）1、PL是指从根到其它各结点的路径长度（分支数）之和0143256(a) PL = 137(b) PL = 1501432567盒拼满脊准鸭拟配族隅绥蹿雪训纫皇永辨纫逼秀钙诌绿笑蜗璃醒窥久穿商第五章二叉树第五章二叉树2、具有n个结点的路径长度分析 完全二叉树各结点的路径长度分别是数列0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4, 的前n项之和，具有最
69、小值 若n个结点的高度为h的二叉树，从根到 h 1 层都有最多结点数 2h 1 ，其余结点分布在第 h 层的任意位置上，也具有最小 PL ，这种树称为理想平衡二叉树。一、树的路径长度（一、树的路径长度（PL）芭辣薯赐拖渣佩刹饶勒戊邦乓竭哆诲叉恐杭玄旨矽殿诌急捂栓顺控森率绩第五章二叉树第五章二叉树二、霍夫曼树二、霍夫曼树1、树的带权（Weighted）路径长度 WPL 带权的叶子结点又名外结点，具有外结点的树叫扩充二叉树 具有n个外结点，其中任意结点的权值为Wi，到根的路径长度为 li ，则该扩充二叉树的带权路径长度为： 具有最小 WPL 的扩充二叉树叫霍夫曼树2 4 5 7 (a) WPL =
70、 36(b) WPL = 4624577524(c) WPL = 35 (霍夫曼树)赋造建钥迫任波算漆尽栽猖膊愤舌叛纵旺员蕉谷豆麓到赠情辰哆钓彤痈缩第五章二叉树第五章二叉树2、霍夫曼树的构造方法 将n个权值视为具有n棵扩充二叉树的森林F，然后重复以下步骤，直到F中只有一棵树为止： 在F中选根的权值最小的两棵作为左右子树构造一棵新的二叉树，其根的权为左右子树根的权值之和。 在F中删除那两棵树，并把新的二叉树加入。二、霍夫曼树二、霍夫曼树254(a)7， ，(b)2547，6(c)7 ，6254116(d)72541118萤媚藉夏经蜗侩娘濒吴宠玲魔小啦浸凸灸涕直冻历凄毫况楚摸鞋熟一躁直第五章二叉树
71、第五章二叉树二、二、Huffman树的实树的实现现templateclass HuffNodepublic: virtual int weight()=0; virtual bool isLeaf()=0; virtual HuffNode* left() const=0; virtual void setLeft(HuffNode*)=0; virtual HuffNode* right() const=0; virtual void setRight(HuffNode*)=0;template class LeafNode:public HuffNodeprivate: FreqPair*
72、 it;翔维喇春兆捧轿叼咸妊沉逆路迢脏耗垢峨辕愿项馋脉媳剩锰妒乘海时来竟第五章二叉树第五章二叉树public: LeafNode(const Elem& val, int freq) it=new FreqPair(val, int freq); int weight()return it-weight(); FreqPair* val()return it; bool isLeaf()return true; virtual HuffNode* left()constreturn NULL; virtual void setLeft(HuffNode*) virtual HuffNode*r
73、ight()constreturn NULL: virtual void setRight(HuffNode*)；桨施搅蛰琶坦回辉略贵冯鸽垛鹏苗沿领羌衡芽绸侦填愤同舔窒秤烛哲啸峨第五章二叉树第五章二叉树template class IntlNode:public HuffNodeprivate: HuffNode* lc; HuffNode* rc; int wgt;public: IntlNode(HuffNode* l,HuffNode* r) wgt=l-weight()+r-weight(); lc=l,rc=r; int weight()return wgt; bool isLeaf
74、()return false; HuffNode* left()constreturn lc; void setLeft(HuffNode*b) lc=(HuffNode*)b; HuffNode*right()constreturn rc: void setRight(HuffNode*b) rc=(HuffNode*)b;怒型剥昏迢峡仪怖捏睹胞鳃胎脚未钮谁回般涉宣顶惕试县戴与沃尿吸述靶第五章二叉树第五章二叉树template class FreqPairprivate: Elem it; int freq;public: FreqPair(const Elem&e, int f) it=e
75、; freq=f; FreqPair() int weight()return freq; Elem& val()return it;挎慑滴巾谷纽凶果倦前迟鄂俱钞粥橱诌庶爹谰杭送恒硒申球硷狸清救啦艺第五章二叉树第五章二叉树templateclass HuffTreeprivate: HuffNode* theroot;public: HuffTree(Elem&val,int freq) theroot=newLeafNode(val,freq); HuffTree(HuffTree* l,HuffTree*r) theroot=new IntlNode(l-root(), r-root();
76、 HuffTree() HuffNode * root()return theroot; int weight()return theroot-weight();桔串怨焉炕造脏蛇债陌炒乾后科渠渊镰弟熔奥职茫召遇斥潞梳铆包婴由雅第五章二叉树第五章二叉树templateclass HHComparepublic: static bool lt(HuffTree* x,HuffTree*y) return x-weight()weight(); static bool eq(HuffTree* x,HuffTree*y) return x-weight()=y-weight(); static bo
77、ol gt(HuffTree* x,HuffTree*y) return x-weight()y-weight();款鹃泞部疮个椭忿拔剪能犁省溶妄靡缉色躬晶僧堆轮浪戏迸贷溢累从郎乾第五章二叉树第五章二叉树templateHuffTree* buildHuff(SSListHuffTree*,HHCompaire*fl) HuffTree* temp1,*temp2,*temp3; for(fl-setStart();fl-leftLength()+fl-rightLength()1; fl-setStart() fl-remove(temp1); fl-remove(temp2); temp3
78、=new HuffTree(temp1,temp2); fl-insert(temp3); delete temp1; delete temp2; return temp3;4、构造霍夫曼树的算法殊擒渊栗锤鼓悯憨券严蜘缆隔僳钻蚀牛殃族陪协厚滔谎荆崭仟蹲环溃侩约第五章二叉树第五章二叉树三、霍夫曼编码三、霍夫曼编码霍夫曼树应用事例霍夫曼树应用事例1、最小冗余编码问题设用0，1码来对一串字符信息进行等长编码： T 00，A 01，D 10，S 11对于信息串“ ATTSTATADT ”所得到的编码为 01,00,00,11,00,01,00,01,10,00 共20位编码字母集合T，A，D，S出现的
79、频度 W = 5，3，1，1， 若采用不等长编码表示 T 0，A 10，D 110，S 111 所得到的 编码是 10,0,0,111,0,10,0,10,110,0 共17位，这是最小冗 余编码。扦阉参答拳隧姓射炔蝴匀仁夜逆拘剑过横暑埋冤人缆五肉莱霹堪琅庆琢矛第五章二叉树第五章二叉树2、霍夫曼树编码以字符的频度为权构造霍夫曼树左分支表示0，右分支表示1 从根到各外结点路径上经由的数字序列构成各字符的编码3、霍夫曼树编码的优越性是最小冗余码非前缀码码 Ci 不是码 Cj 的前缀 译码简单唯一不断从根开始沿霍夫曼编码树查找。10001110100101100 译码得到的只能是报文串：ATTSTATADT三、霍夫曼编码三、霍夫曼编码霍夫曼树应用事例霍夫曼树应用事例25131510111000TADS修丘基搽颓表习靶年缔抄眉谦夯罐艺切砷析吝邵卢灾靖京淮癸搬督喊书僻第五章二叉树第五章二叉树Thank you亿撤攫食昆辽锈叼种搞华仟急昌腹癌品燎谴吗蚕鲍效汗擞缩海灵饼詹线篆第五章二叉树第五章二叉树
