哈夫曼树右子树一定比左子树大吗_哈夫曼树只有度为0和度为2

24山西大学计算机/软工考研 | 树和二叉树考点总结 　　树和二叉树专题 　　树(Tree)是n(n≥0)个结点的有限集，它或为空树(n=0);或为非空树，对于非空树T: 　　(1）有且仅有一个称之为根的结点; 　　(2）除根结点以外的其余结点可分为m(m>0）个互不相交的有限集T1，T2……，Tm，其中每个集合本身又是一棵树，并且称为根的子树（SubTree )。

　　总：树的定义是一个递归定义，即在树的定义中又用到树的定义，它道出了树的固有特性。 　　树的基本术语： 　　(1)结点：树中的一个独立单。包含一个数据素及若干指向其子树的分支，如上图中的A、B、C、D等。 　　(2)结点的度：结点拥有的子树数称为结点的度。例如，A的度为3，C的度为1，F的度为0。 　　(3)树的度：树的度是树内各结点度的最大值。图(b)所示的树的度为3。 　　(4)叶子：度为0的结点称为叶子或终端结点。结点K、L、F、G、M、I、J都是树的叶子。 　　(5)非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。 　　(6)双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A，B的孩子有E和F。 　　(7)兄弟：同一个双亲的孩子之间互称兄弟。例如，H、I和J互为兄弟。 　　(8)祖先：从根到该结点所经分支上的所有结点。例如，M的祖先为A、D和H。 　　(9)子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L和F。 　　(10)层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加1。 　　(11)堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。 　　(12)树的深度：树中结点的最大层次称为树的深度或高度。图(b)所示的树的深度为4。 　　(13)有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 　　(14)森林：是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用递归的定义来描述树。 　　二叉树（Binary Tree）是n（n>=0）个结点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树T： 　　(1)有且仅有一个称之为根的结点 　　(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。 　　二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点: 　　(1)二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点); 　　(2)二叉树的子树有左右之分，其次序不能任意颠倒。 　　二叉树的五种基本形态： 　　

　　二叉树的性质： 　　

　　完全二叉树的特点是： 　　(1叶子结点只可能在层次最大的两层上出现； 　　(2)对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为1或l+1。 　　二叉树的存储结构： 　　顺序存储结构： 　　顺序存储结构使用一组地址连续的存储单来存储数据素，对于完全二叉树只要从根起按层序存储即可，依次自上而下，自左至右存储节点素。由此可见，顺序存储结构仅适用于完全二叉树；存储普通的二叉树遇多个无素的结点会导致存储空间的极大浪费。对于一般二叉树更适合采取下面的链式存储结构 　　链式存储结构： 　　对于二叉树中的结点包括一个数据域和三个指针域（左子树和右子树和父母） 　　遍历二叉树： 　　遍历二叉树是按照某条搜索路径访问树中的每一个节点（仅访问一次），想要对二叉树进行操作首先得遍历。二叉树是由三个基本单组成：根节点、左子树、右子树；则遍历二叉树的思路就是依次遍历左根右等不同的顺序，在此介绍三种： 　　先序遍历二叉树的操作定义如下: 　　若二叉树为空,则空操作;否则 　　(1)访问根结点; 　　(2)先序遍历左子树; 　　(3)先序遍历右子树。 　　中序遍历二叉树的操作定义如下: 　　若二叉树为空,则空操作;否则 　　(1)中序遍历左子树; 　　(2)访问根节点 　　(3)中序遍历右子树 　　后序遍历二叉树的操作定义如下: 　　若二叉树为空,则空操作;否则 　　(1)后序遍历左子树 　　(2)后序遍历右子树 　　(3)访问根节点 　　中序遍历递归算法： 　　



　　无论是递归还是非递归遍历二叉树，因为每个节点被访问一次，则不论按照哪一种次序进行遍历，对含有n个结点的二叉树，其时间复杂度均为O(n)；所需辅助空间为遍历过程中栈的最大容量，最坏情况下为n，则空间复杂度为O(n) 　　线索二叉树： 　　在上述二叉树中每个节点包含左右子树信息。但无法知道结点在任意序列中的前驱和后继，这种信息只有在遍历二叉树后得到，线索二叉树就是来解决该问题；由于有n个结点的二叉链表中必定有n+1个空链域，因此我们可以充分利用空链域来存放结点的前驱和后继信息。防止混淆，我们在二叉树的结点增加两个标志域。 　　若标志域是0表示的是指向该结点的左（右）孩子，标志域是1表示的是前驱（后继） 　　二叉树的二叉线索类型定义如下： 　　以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针叫做线索；加上线索的二叉树称之为线索二叉树 　　线索二叉树的实质就是把二叉链表中的空指针改为指向前驱或者后继的线索，而前驱或后继的信息只有在遍历时才能得到。 　　以结点p为根的子树中序线索化：

　　树的存储结构： 　　双亲表示法、孩子表示法、孩子兄弟表示法 　　树和二叉树的转换： 　　树转换成二叉树的思路（口诀：兄弟相连留长子）： 　　加线：在兄弟之间加一连线 　　抹线：对每个结点，除了其左孩子外，去除其与其孩子之间的关系 　　旋转：以树的根节点为轴心，将整树顺时针转 　　给定一棵树，可以找到 唯一的一棵二叉树与之对应 　　二叉树转换成树思路： 　　加线：若p结点是双亲结点的左孩子，则将p的右孩子、右孩子的右孩子……沿分支找到的所有右孩子，都与p的双亲用线连接起来 　　抹线：抹掉原二叉树中双亲与右孩子之间的连线 　　调整：将结点按层次排列，形成树结构 　　森林与二叉树的转换： 　　森林转换成二叉树思路：（口诀：树变二叉根相连） 　　将各棵树分别转换成二叉树 　　将每棵树的根结点用线相连 　　以第一棵树根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构 　　二叉树转换成森林思路：（口诀：去掉全部右孩线，孤立二叉再还原） 　　抹线：将二叉树中根节点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 　　还原：将孤立的二叉树还原 　　树和森林的遍历： 　　树的遍历： 　　先根(次序)遍历：若树不空，则先访问根节点，然后依次先根遍历各棵子树 　　后根(次序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根节点 　　按层次遍历：若树不空，则自上而下自左至右访问树中每个结点 　　将森林看作三部分构成： 　　森林中第一棵树的根节点 　　森林中第一棵树的子树森林 　　森林中其它树构成的森林 　　森林的遍历： 　　先序遍历：若森林不空，则访问森林中第一棵树的根节点；然后先序遍历森林中第一棵树的子树森林；最后先序遍历森林中（除第一棵树之外）其余树构成的森林（即从左至右对森林中的每一棵树进行先根遍历） 　　中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；然后访问森林中第一棵树的根节点；最后中序遍历森林中（除第一棵树之外）其余树构成的森林 （依次从左至右对森林中的每一棵树进行后根遍历） 　　哈夫曼树： 　　路径:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 　　路径长度:路径上的分支数目称作路径长度。 　　树的路径长度:从树根到每一结点的路径长度之和。 　　权：将树中结点赋给一个有着某种含义的数值，则称这个数值称为该结点的权 　　结点的带权路径长度：从该结点到树根之间的路径长度与节点上权的乘积。 　　树的带权路径长度：树中所有叶子结点的带权路径长度之和 　　哈夫曼树：又称作最优树；是带权路径长度最短的树（“带权路径长度最短”是在“度相同”的树中比较而得到的结果，因此有最优二叉树、最优三叉树等等） 　　提醒：满二叉树不一定是哈夫曼树；在节点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树；注意区分树的路径长度和树的带权路径长度是完全不一样的 　　哈夫曼树的构造方法： 　　1.根据n个给定的权值{W1,W2,W3……Wn}构成n棵二叉树的森林，其中森林中的每一棵树都是一个根节点 　　2.在森林中选取两棵根结点的权值最小的成为左右子树，构造一棵新的二叉树，且设置新的二叉树的根节点的权值为其左右子树上根结点的权值之和。 　　3.在F中删除这两棵树，同时将新得到的二叉树加入森林中 　　4.重复第2步和第3步，直到森林中只有一棵树为止，这棵树即为哈夫曼树 　　口诀：构造森林全是根；选用两小造新树；删除两小添新人；重复2、3剩单根 　　总结：初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树；经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点；所以，哈夫曼树共有2n-1个结点，因为每次合并都会产生一个新的结点；且其所有的分支节点的度均不为1.