数据结构第5章树与二叉树.pptVIP

1,第5章 树和二叉树（ Tree & Binary Tree ）,特点：非线性结构，一个直接前驱，但可能有多个直接后继。,（一对多或1:n）,5.1 树的概述,5.2 二叉树定义和性质,5.3 遍历二叉树,5.4 线索二叉树,5.5 树和森林,5.6 哈夫曼及其应用,2,5.1 树的基本概念,1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,3,1. 树的定义,注1：树的定义具有递归性，即“树中还有树”。,由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树 。,4,树的表示法主要有5种：,图形表示法 嵌套集合表示法 广义表表示法 凹入表示法 左孩子右兄弟表示法,5,图形表示法：,华科大武昌分校,叶子,根,子树,6,嵌套集合表示法,7,广义表表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边,麻烦问题：应当开设多少个链域?,8,凹入表示法 (又称目录表示法),9,左孩子右兄弟表示法,10,2. 若干术语,即树的数据元素 结点挂接的子树数,结点 结点的度 结点的层次 终端结点 分支结点,树的度 树的深度 (或高度),从根到该结点的层数（根结点算第一层） 即度为0的结点，即叶子 即度不为0的结点（也称为非终端结点）,所有结点度中的最大值（Max各结点的度） 指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数 ；树的度 ；树的深度,13,3,4,（有几个直接后继就是几度，亦称“次数”）,11,3. 树的逻辑结构,一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,4. 树的存储结构,讨论1：树是非线性结构，该怎样存储？,特点：,仍然有顺序存储、链式存储等方式。,12,5.2 二叉树,为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构,（二叉树的运算见5.3节）,13,1. 二叉树的定义,定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1:2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒。,问：具有3个结点的二叉树可能有几种不同形态？,有5种,基本形态：,一般的树有几种？,14,2. 二叉树的性质 (3+2),讨论1：第i层的结点数最多是多少？ （利用二进制性质可轻松求出）,性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。,性质2: 深度为k的二叉树至多有2k-1个结点（k0）。,再提问：第i层上至少有 个结点？,1,讨论2：深度为k的二叉树，最多有多少个结点？ （利用二进制性质可轻松求出）,2i-1个,2k-1个,15,讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？,性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+1）,证明： 二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数) 又二叉树中全部结点数nB+1 ( 总分支数根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1,物理意义：叶子数2度结点数1,16,2.深度为的二叉树的结点总数，最多为 个。 )k-1 ) log2k ) k )k,1. 树中各结点的度的最大值称为树的 。 ) 高度 ) 层次 ) 深度 ) 度,D,C,C,3. 深度为9的二叉树中至少有 个结点。 )9 )8 ) )91,课堂练习：,17,满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）,完全二叉树：深度为k 的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。,为何要研究这两种特殊形式？,完全二叉树的特点是只有最后一层叶子不满，且全部集中在左边。但这其实是顺序二叉树的含义。而图论中的“完全二叉树”是指n1=0的情况。,因为它们在顺序存储方式下可以复原！,18,对于两种特殊形式的二叉树（满二叉树和完全二叉树）,还特别具备以下2个性质：,性质4: 具有n个结点的完全二叉树的深度必为log2n1,性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i1；其双亲的编号必为i/2（i1 时为根,除外）。,证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间， 即2k-1-1n2k-1 或2k-1n2k 三边同时取对数，于是有：k-1log2nk 因为k是整数，所以k=log2n +1,可根据归纳法证明。,19,5.2.3 二叉树的存储结构,一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,A B C D E F G H I,问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5） 例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,20,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,A B C D E,缺点：浪费空间；插入、删除不便,21,二、链式存储结构 用二叉链表即可方便表示。,二叉树结点数据类型定义： typedef struct node *tree_pointer; typedef struct node int data; tree_pointer left_child, right_child; node;,一般从根结点开始存储。 （相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,22,例：,23,5.3 遍历二叉树,一、遍历二叉树（Traversing Binary Tree）,遍历定义 遍历用途 遍历方法,指按某条搜索路线遍访每个结点且不重复（又称周游）。,它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。,对每个结点的查看通常都是“先左后右” 。,24,遍历规则,二叉树由根、左子树、右子树构成，定义为D、 L、R,以根结点为参照系,注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，则有三种实现方案：,DLR LDR LRD 先根遍历 中根遍历 后根遍历,25,例1：,先根遍历的结果是： 中根遍历的结果是： 后根遍历的结果是：,D B E A C D E B C A,口诀： DLR先根遍历，即先根再左再右 LDR中根遍历，即先左再根再右 LRD后根遍历，即先左再右再根,A,B,D,E,C,26,先根遍历结果 + * * / A B C D E 前缀表示法 中根遍历结果 A / B * C * D + E 中缀表示法 后根遍历结果 A B / C * D * E + 后缀表示法 层次遍历结果 + * E * D / C A B,例2：用二叉树表示算术表达式,27,遍历的算法实现：,typedef struct node *tree_pointer; typedef struct node int data; tree_pointer left_child, right_child; node;,回忆2：递归函数,long int fact(n) /求n! int n; long f; if(n1)f=n*fact(n-1); else f=1; return(f); ,用递归形式格外简单！,回忆1：二叉树结点的数据类型定义：,则三种遍历算法可写出:,28,中根遍历算法 LDR(node *root) if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);,后根遍历算法 LRD (node *root) if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);,结点数据类型自定义 typedef struct node int data; struct node *lchild,*rchild； node; node *root;,先根遍历算法 DLR( node *root ) if (root !=NULL) /非空二叉树 printf(“%d”,root-data); /访问D DLR(root-lchild); /递归遍历左子树 DLR(root-rchild); /递归遍历右子树 return(0); ,29,对遍历的分析：,1. 从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径 上，每个结点经过3次。,第1次经过时访问，是先根遍历 第2次经过时访问，是中根遍历 第3次经过时访问，是后根遍历,2. 二叉树遍历的时间效率和空间效率 时间效率:O(n) /每个结点只访问一次 空间效率:O(n) /栈占用的最大辅助空间,精确值：树深为k的递归遍历需要k+1个辅助单元,30,用空格字符表示无孩子或指针为空,注：要实现遍历运算，必须先把二叉树存入电脑内,怎样建树？,例：将下面的二叉树以二叉链表形式存入计算机内。,考虑1：输入结点时怎样表示“无孩子”？ 考虑2：以何种遍历方式来输入和建树？,将二叉树按先序遍历次序输入： A B C D E G F ,以先序遍历最为合适，让每个结点都能及时被连接到位。,31,建树算法： Status CreateBiTree( BiTree /CreateBiTree,输入序列： A B C D E G F ,32,问：用二叉链表法（l_child, r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？,思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？ 我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。,所以， 空指针数目2n(n-1)=n+1个。,n+1个,分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说明）。,除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n1个结点的链域存放指针，指向非空子女结点（即直接后继）。,线索二叉树,33,思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？ 我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。,用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。,这就是线索二叉树（Threaded Binary Tree）,34,5.4 线索二叉树（Threaded Binary Tree）,二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。 先依遍历规则把每个结点对应的前驱和后继线索预存起来，这叫做“线索化”。 意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。,对二叉树进行某种遍历之后，将得到一个线性有序的序列。 例如对某二叉树的中序遍历结果是B D C E A F H G，意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。在此前提下，那n+1个空链域才可能装得下“线索”。,讨论1：二叉树是1:2的非线性结构，其直接后继可能不止一个，如何存放？,讨论2.如何获得这种“直接前驱”或“直接后继”？有何意义？,35, 每个结点增加两个域：fwd和bwd；,存放前驱指针,存放后继指针,如何预存这类信息？有两种解决方法：, 与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。,规 定：,1）若结点有左子树，则lchild指向其左孩子； 否则， lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子； 否则，rchild指向其直接后继(即线索) 。,缺点：空间效率太低！,问题：计算机如何判断是孩子指针还是线索指针？,如何区别？,36,约定:,当Tag域为0时,表示正常情况;,当Tag域为1时,表示线索情况.,前驱(后继),左(右)孩子,为区别两种不同情况，特增加两个标志域：,问：增加了前驱和后继等线索有什么好处？,能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。,37,1. 有关线索二叉树的几个术语：,线索链表： 线 索： 线索二叉树： 线 索 化：,用含Tag的结点样式所构成的二叉链表 指向结点前驱和后继的指针 加上线索的二叉树 对二叉树以某种次序遍历使其变为线索二叉树的过程,yyy,线索化过程就是在遍历过程中修改空指针的过程： 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为“正常情况”）,38,A,G,E,I,D,J,H,C,F,B,例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。,A,39,悬空？ NIL,悬空？ NIL,解：对该二叉树中序遍历的结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：,为避免悬空态，应增设一个头结点,例1：画出以下二叉树对应的中序线索二叉树。,2. 线索二叉树的生成线索化,线索化过程就是在遍历过程中修改空指针的过程,40,注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G,对应的中序线索二叉树存储结构如图所示：,41,线索二叉树的生成算法（递归算法见教材）,实质：在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。,为了记下遍历过程中访问结点的先后次序，需要设置两个指针： p指针当前结点之指针；pre指针当前结点的前趋结点指针。,设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前驱结点的右指针是否为空。,每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱），参见算法。,若p-lchildNULL,则p-Ltag=1;p-lchildpre; /p的前驱线索应存p结点的左边 若pre-rchildNULL, 则pre-Rtag1;pre-rchild=p; /pre的后继线索应存pre结点的右边,42,3. 线索二叉树的遍历（无需堆栈）,对于线索二叉树的遍历，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空为止。 （因为建立线索时已遍历一次，相当于线性化了！）,难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。,以中根线索二叉树为例： 当RTag=1时，直接后继指针就在其rchild域内； 当RTag=0时，直接后继是当前结点右子树最左下方的结点；,请注意中序遍历规则是LDR，先左再根再右,43,5.5 树和森林,1.树和森林的存储方式 2.树和森林与二叉树的转换 3. 树和森林的遍历,44,1. 树和森林的存储方式,树有三种常用存储方式： 双亲表示法 孩子表示法 孩子兄弟表示法,1、用双亲表示法存储,思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。,45,-1,0,0,0,例1: 双亲表示法,缺点：求结点的孩子时需要遍历整个结构,1 1 3 6 6 6,46,思路：对n个结点分别设立n个孩子链表，结点为表头； 再将n个表头用数组存放起来，形成一个混合结构。,例如：,2、用孩子表示法存储,47,思路：用二叉链表来表示树，但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。,3、用孩子兄弟表示法存储,指向左孩子,指向右兄弟,48,问：树二叉树的“连线抹线旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。,例如：,49,2. 树和森林与二叉树的转换,转换步骤： step1: 将树中同一结点的兄弟相连;,加线,抹线,旋转,讨论1：树如何转为二叉树？,孩子兄弟表示法,step2: 保留结点的最左孩子连线，删除其它孩子连线；,step3: 将同一孩子的连线绕左孩子旋转45度角。,50,方法：加线抹线旋转,树转二叉树举例：,兄弟相连,长兄为父,孩子靠左,根结点肯定没有右孩子！,51,讨论2：二叉树怎样还原为树？,要点：逆操作，把所有右孩子变为兄弟！,52,法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。,讨论3：森林如何转为二叉树？,法二：森林直接变兄弟，再转为二叉树,（参见教材，两种方法都有转换示意图）,法一和法二得到的二叉树是完全相同的、惟一的、,53,森林转二叉树举例：（采用法二）,兄弟相连 长兄为父 头树为根 孩子靠左,A,54,讨论4：二叉树如何还原为森林？,要点：把最右边的子树变为森林，其余右子树变为兄弟,55,5.6 Huffman树及其应用,一、Huffman树 二、Huffman编码,最优二叉树,Huffman树,Huffman编码,带权路径长度最短的树,不等长编码,是通信中最经典的压缩编码,56,一、最优二叉树（Huffman树）,路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： Huffman树：,由一结点到另一结点间的分支所构成。,路径上的分支数目。,从树根到每一结点的路径长度之和。,结点到根的路径长度与结点上权的乘积（WPL）,若干术语：,树中所有叶子结点的带权路径长度之和,带权路径长度最小的树。,ae的路径长度,树长度,2,10,Huffman常译为赫夫曼、霍夫曼、哈夫曼等,Weighted Path Length,57,树的带权路径长度如何计算？,经典之例：,WPL=,WPL=,WPL=,Huffman树是WPL 最小的树,树中所有叶子结点的带权路径长度之和,36,46,35,58,1. 构造Huffman树的基本思想：,例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？,法1：等长编码（如二进制编码） 令d=00，i=01，a=10，n=11，则： WPL12bit(7524）36 法2：不等长编码（如Huffman编码） 令d=0;i=10,a=110,n=111，则：,明确：要实现Huffman编码，就要先构造Huffman树,讨论：Huffman树有什么用？,权值大的结点用短路径，权值小的结点用长路径。,WPL最小的树,频度高的信息用短码，反之用长码，传输效率肯定高！,信息高效传输,WPL2=1bit72bit5+3bit(2+4)=35,59,2. 构造Huffman树的步骤（即Huffman算法）：,(1) 由给定的 n 个权值 w1, w2, , wn 构成n棵二叉树的集合F = T1, T2, , Tn （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。 (2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。 (3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。 (4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。,怎样证明它就是WPL最小的最优二叉树？ 参考信源编码,60,s