《特殊二叉树》PPT课件.ppt

第六章 特殊二叉树,6.1 二叉搜索树,二叉搜索树的定义 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有如下特征的非空二叉树:若它的左子树非空,则左子树上所有结点的关键字均小于根结点的关键字;若它的右子树非空,则右子树上所有结点的关键字均大于(若允许具有相同关键字的结点存在,则大于等于)根结点的关键字;左、右子树本身又各是一棵二叉搜索树。,52,63,30,12,15,23,74,18,26,一棵二叉排序数,对该树中序遍历得到一有序序列：12，15，18，23，26，30，52，63，74非递减序列,6.1.3 二叉搜索树的运算,查找 从二叉搜索树中查找其值等于给定值item的结点，其过程为：(1)若二叉搜索树为空，则表明查找失败，应返回假(2)若item等于当前树根结点的值，则表明查找成功，应由引用参数item带回根结点的完整值并返回真(3)若item小于当前树根结点的值，则继续在它的左子树上查找，若item 大于当前树根结点的值，则继续它的右子树上查找。,bool Find(BTreeNode*BST,ElemType,进行二叉排序树查找的非递归算法bool Find1(BTreeNode*BST,ElemType,2.二叉排序树的更新,二叉排序树的更新算法与查找算法基本相同，区别在于：在更新算法中查找到待更新元素时，应将item的值赋给该元素，而查找算法中则是将该元素的值赋给item带回更新算法中item可为变参，也可为值参，在参数说明前可以加或不加const,而在查找算法中item只可为变参，且不能加常量标识符const,3.二叉排序树的插入,向二叉搜索树中插入其值为item的结点的过程为:(1)若当前二叉树为空，则由item元素生成的新结点将作为树根结点插入；(2)否则，若item 小于当前树根结点的值，则将新结点插入到它的左子树上，若item大于当前树根结点的值，则将新结点插入到它的右子树上。,递归算法描述为：void Insert(BTreeNode*,非递归算法描述为：void Insert1(BTreeNode*,利用二叉排序树插入算法生成二叉排序树void CreateBSTree(BTreeNode*,例：假定待建立二叉排序树的一组元素为：（38，26，62，94，35，50，28，55）,4.二叉排序树的删除,删除叶子结点将其双亲结点链接到它的指针去掉(即置为空)。,删除单支结点将后继指针链接到它所在的链接位置。,L,D,S,(c),G,A,W,P,删除双支结点一种方法是：首先把它的右子树链接到它的中序前驱结点的右指针域，然后把它的左子树链接到它所在的链接位置。,第二种方法是：首先把它的中序前驱结点的值赋给该结点的值域，然后再删除它的中序前驱结点。,练习：P247 习题6-1中1，2两题1.,46,25,78,37,12,70,62,29,广义表：46（25（12，37（29），78（62（，70）,2.,49,63,28,30,12,16,72,34,49,28,30,12,16,63,34,删除72,广义表：28（12（，16），49（34（30），63）,49,28,30,12,16,63,34,删除12,49,28,30,16,63,34,广义表：28（16，49（34（30），63）,49,28,30,16,63,34,34,28,16,63,30,删除49,广义表：28（16，34（30，63）,34,28,16,63,30,34,16,63,30,删除28,广义表：16（，34（30，63）,6.2 堆,6.2.1 堆的定义 堆分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二叉树。(1)若树根结点存在左孩子，则树根结点的值小于等于左孩子结点的值；(2)若树根结点存在右孩子，则树根结点的值小于等于右孩子结点的值；(3)以左、右孩子为根的子树又同样各是一个堆。大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。,6.2.1 堆的定义,6.2.3 堆的存储结构,struct Heap ElemType*heap;int len;int MaxSize;,0 1 2 3 4 5 6 7 8 9,6.2.3 堆的存储结构,6.2.4 堆的运算,（1）向堆中插入一个元素 将该元素写入到堆尾，即堆中最后一个元素位置的后面，如果不满足对的特征，向上逐层调整。,插入15,（2）从堆中删除元素（删除堆顶元素）将栈顶结点删除后，将堆尾结点移至堆顶，若破坏了堆的特征，从上往下逐层调整,6.2.4 堆的运算,练习：P247 习题6-1中3，43.,40,64,12,38,15,26,48,52,55,73,（12 15 40 38 26 52 48 64 55 73）,4.,40,64,12,38,15,26,48,52,删除12,40,15,38,26,64,48,52,40,15,38,26,64,48,52,删除15,40,26,48,38,64,52,40,26,48,38,64,52,删除26,40,38,52,48,64,64,40,52,48,40,38,52,48,64,删除38,练习：1.一棵二叉树的前序遍历序列为ABCDEFG，其中序遍历序列可能是 A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEGB,BD,2.一棵高为h的二叉树中无单分支结点，问此树所包含的结点数至少为3.任何一棵二叉树的叶子结点在前、中、后序遍历序列中的相对次序 A.不发生改变 B.发生改变 C.不能确定 D.以上均错,2h-1,A,6.3 哈夫曼树,6.3.1 基本术语路径和路径长度若在一棵树中存在一个结点序列k1,k2,kj,使得ki是ki+1的双亲(1ij),则称此结点序列是从k1到kj的路径。从k1kj所经过的分支数称为这两结点间的路径长度。结点的权和带权路径长度在许多应用中，常为树中的结点赋上一有意义的实数，该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。,树的带权路径长度树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为 WPL=,WPL=92+42+52+22=40,哈夫曼树哈夫曼(Huffman)树又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。,例:有四个叶结点 a,b,c,d,分别带权为9、4、5、2,由它们构成的三棵不同的二叉树：,WPL=92+42+52+22=40,WPL=91+52+43+23=37,其中图(c)树的WPL最小，可以验证，此树就是哈夫曼树。,特点：权值大的叶子结点距离根结点近 权值小的叶子结点距离根结点远,6.3.2 构造哈夫曼树,构造算法如下：(1)根据与n个权值w1,w2wn对应的n个结点构成具有n棵二叉树的森林F=T1,T2Tn,其中第i棵二叉树Ti(1 i n)都只有一个权值为wi的根结点，其左、右子树均为空,(2)在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和(3)从F中删除构成新树的那两棵，同时把新树加入F中,a,(b),c,b,d,4,2,5,9,6,(4)重复第(2)和第(3)步，直到F中只含有一棵为止，此树便为哈夫曼树,(c),c,b,d,4,2,5,6,11,9,a,(b),c,b,d,4,2,5,9,6,6.3.3 哈夫曼编码,在电报通讯中，电文以二进制的0、1序列传送。在发送端将电文中的字符转换成二进制序列，称为编码。在接收端将接收的0、1序列转换为对应的字符序列，称为译码。最简单的二进制编码方式是等长编码。即各字符编码长度相等。例：设电文中有A、B、C、D、E、F六个字符的等长编码可为000、001、010、011、100、101缺点：使传送电文总长度很长 设在一份电文中，这六个字符的出现频率依次为4，2，6，8，3，2 采用等长编码，编码后总长度 L=3(4+2+6+8+3+2)=75,电文中每个字符出现的频率一般是不同的，若采用不等长编码，可使出现频率高的字符具有较短的编码，使出现频率低的字符具有较长的编码。可能出现的问题：译码的二义性或多义性例：设在一份电文中，这六个字符的出现频率依次为4，2，6，8，3，2 采用不等长编码，为D编码0，为C编码1，为A编码01,这样码长较短，但译码时如有01，出现了二义性,对某一字符集进行不等长编码时，任一字符编码都不是其它字符编码的前缀，这就是无前缀编码。由编码哈夫曼树所得到的字符编码称为哈夫曼编码。规则：每个结点左孩子的权小于等于右孩子结点的权 二叉树中每个分支结点的左、右分支分别用0、1编码，从树根到各叶子结点的路径上所经分支的0、1编码序列构成该叶结点的哈夫曼编码,练习：P247 习题6-1中第5题，第6题5.解：WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=1316.解：编码a:011 b:10 c:00 d:010 e:11 WPL=(2+4)*3+(5+7+9)*2=60,练习：若一棵Huffman树有n0个叶子结点，问它有多少个结点（总数）根据使用频率为5个字符设计的Huffman编码不可能是 A.000,001,010,011,1 B.0000,0001,001,01,1 C.000,001,01,10,11 D.00,100,101,110,111,2 n0-1,D,3.根据使用频率为5个字符设计的Huffman编码不可能的是 A.111,110,10,01,00 B.000,001,010,011,1 C.100,11,10,1,0 D.001,000,01,11,10,C,6.4 线索二叉树,6.4.1 二叉树的线索化线索：在结点的空指针域中存放的该结点在某次遍历次序下的前驱结点或后继结点的指针。前驱线索：在结点的空指针域中存放的该结点在某次遍历次序下的前驱结点的指针。后继线索：在结点的空指针域中存放的该结点在某次遍历次序下的后继结点的指针。线索化：对一棵二叉树中所有结点的空指针域按某种遍历次序加线索的过程。线索二叉树：被线索化了的二叉树。,增加线索标志域后的结点结构为：,该结点结构的类型定义为,Struct TTreeNode/定义线索二叉树的结点类型 ElemType data;/值域 int ltag,rtag;/线索标志域 TTreeNode*left;/左指针域 TTreeNode*right;/右指针域,NULL,中序线索二叉树,BGDAEHCF,G,A,E,B,C,D,F,H,后序线索二叉树,ABDGCEHF,GDBHEFCA,NULL,6.4.2 利用线索进行遍历,例：如何在中序线索二叉树上寻找一个结点p的中序后继结点,(1)若p结点的右线索标志域为1,则p-right直接指向p的中序后继结点(2)若p结点的右线索标志域为0,p的中序后继结点必是其右子树中第一个中序遍到的结点,也就是p的右子树中“最左下”结点.,练习：已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa，画出其前序线索二叉树二叉树在线索后，仍不能有效求解的问题是 A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D.后序线索二叉树中求后序后继,D,6.5 平衡二叉树,一、定义 平衡二叉树是对二叉搜索树的一种改进，简称平衡树，又称AVL树。平衡二叉树：若一棵二叉树中每个结点的左、右子树的高度至多相差1 平衡因子：二叉树中每个结点的左子树高度减去右子树高度定义为该结点的平衡因子。平衡树中每个结点的平衡因子只能是1、0或-1。,6.5 平衡二叉树,二、最小不平衡二叉树,若插入后某些结点的左子树高度增加1，具体分为以下三种情况：(1)若插入前，一些结点的左子树高度hL与右子树高度hR相等，即平衡因子为0，则插入后将使平衡因子变为1，但仍符合平衡的条件，不必对它们加以调整,(2)若插入前一些结点的hL小于hR，即平衡因子为-1，则插入后将使平衡因子变为0，平衡更加理想，更不必进行调整,(3)若插入前一些结点的hL大于hR，即平衡因子为1，则插入后将使平衡因子变为2，破坏了平衡树的限制条件，需对它们加以调整，使整个二叉搜索树恢复为平衡树。,最小不平衡子树：指以离插入结点最近、且平衡因子绝对值大于1的结点做根的子树。,