第5章 树与二叉树.ppt

1、第5章 树与二叉数 第 1 页 2007-7-29,第5章 树与二叉树,5.1 树的基本概念 5.2 二叉树及其基本概念 5.3二叉树的存储结构 5.4 遍历二叉树 *5.5 树的存储结构 5.6 森林与二叉树的转换 5.7 赫夫曼树及其应用,第5章 树与二叉树,5.1树的基本概念,树(tree)是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性， 如图5-1所示。 在树的图形表示中，通常用一个圆圈表示一个结点，结点的名字写在圆圈内或是圆圈旁边，以区别于其他的结点并规定在用直线连起来的两端结点中，总是认为上端结点是前件，下端结点是后件。,第5章 树与二叉数 第

2、 3 页 2007-7-29,树这种数据结构在客观世界中大量存在，例如行政组织机构、家谱等都可用树形象表示。,第5章 树与二叉数 第 4 页 2007-7-29,1.树的定义 树（Tree）是n( n0 )个结点的有限集T。当n=0时，称为空树；当 n0 时 ，该集合满足如下条件：,有且仅有一个特定的称为根（root）的结点； 其余的结点可分为m（m 0）个互不相交的子集T1，T2，.，Tm，其中每个子集本身又是一棵树，并称其为根的子树（SubTree）。,例如，图5-1是一棵具有13个结点的树，其中 A是根，余下的12个结点分成3个互不相交的子集：T1= B，E，F，G，K，L ，T2= C

3、，H ，T3= D，I，J，M 。T1、 T2 、T3都是树，而且是根结点A的子树。,第5章 树与二叉数 第 5 页 2007-7-29,2.树的基本术语,1）结点的度：一个结点的子树数称为该结点的度 。,2）树的度：树的所有结点中的最大的度称为树的度。 3）叶子：树中度为0的结点称为叶子结点或终端结点，简称叶子 。 4）分支结点：树中度不为0的结点称为分支结点或非终端结点。 5）双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。,第5章 树与二叉数 第 6 页 2007-7-29,6）结点的层：规定树的根结点的层（Level）为，其余任一结点的层等于它的双亲的层加。

4、7）树的深度：树中各结点的层的最大值称为树的深度（Depth）或高度。 ）兄弟和堂兄弟：同一双亲的孩子之间互称为兄弟（Sibling）。其双亲在同一层的结点互为堂兄弟。 9）祖先和子孙：一个结点的祖先是指从该结点到树的根所经分支上的所有结点。一个结点的子树上的所有结点称为该结点的子孙。 10）有序树和无序树：如果树中任一结点的各棵子树规定从左至右是有次序的，即不能互换位置，则称该树为有序树，否则称为无序树（如图5-3所示）。,第5章 树与二叉数 第 7 页 2007-7-29,11）森林：n（n0）棵互不相交的树的集合称为森林 。删去一棵树的根结点便得到一个森林 。,5.2 二叉树及其基本性质

5、 1.二叉树的定义,第5章 树与二叉数 第 8 页 2007-7-29,二叉树是n（n0）个结点的有限集，它或者是空集（n = 0），或者是由一个根结点和两棵互不相交且分别称为根的左子树和右子树的二叉树组成。这是二叉树的递归定义。,二叉树共有种基本形态，如图5-4所示,第5章 树与二叉数 第 9 页 2007-7-29,2.二叉树的基本性质,性质:在二叉树的第i层上,最多有2i-1个结点（i1） 性质:深度为k的二叉树最多有2k -1个结点。 显然将第1至第i层的最多结点数相加，即可得到此结果20 + 21 + + 2k-1 =2k-1 性质：在任意一棵二叉树中，若度为0的结点（即叶子结点）数

6、为n0 ，度为2的结点数为n2 ，则n0=n2+1。 设n1为二叉树中度为1的结点数 ，n为二叉树的总结点数，因为n= n1+2n2+1 =n0+n1+n2 可得n0=n2+1,第5章 树与二叉数 第 10 页 2007-7-29,满二叉树：一棵深度为 k 且具有 2k-1 个结点的二叉数 。（对满二叉树的结点进行顺序编号，约定编号从根结点起，自上而下，同层的结点从左至右）,完全二叉树 ：深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时。（完全二叉树除最后一层外，每一层上的结点数都达到最大值 ，在最后一层上可能缺少右边的若干结点。显然满二叉

7、树是完全二叉树 ）。,非完全二叉树：除完全二叉树外的其它二叉树。,第5章 树与二叉数 第 11 页 2007-7-29,在图5-5中，(a)为满而叉树 (b)为完全二叉树 (c)为非完全二叉树。,第5章 树与二叉数 第 12 页 2007-7-29,性质：具有 n个结点的完全二叉树的深度为 log2n + 1。 其中log2n表示不超过log2n的最大整数。,事实上，设完全二叉树的深度为k，由完全二叉树的定义知，它的k-1层，是深度为 k-1的满二叉树；由性质2知，一共有2k-1-1个结点；又因第k层上还有若干结点，所以该完全二叉树总的结点数n2k-1-1 ，另外，总结点数n2k-1 ，从而可

8、得2k-11 n 2k1，整理得到 2k-1 n 2k 。对此不等式的各项，同取以2为底的对数后有k-1log2nk 成立，即k-1= log2n 或k=log2n +1。,采用顺序编号的完全二叉树还具有以下性质：,第5章 树与二叉数 第 13 页 2007-7-29, 若i=1，则结点i是二叉树的根，无双亲；如果i1，则该结点的父结点编号为 i/2。 若2in，则结点i的左孩子是结点2i；若2in，则结点i无左孩子。 若2i+1n ，则结点i的右孩子是结点2i+1；若2i+1n ，则结点i无右孩子。,根据完全二叉树的这些性质，很容易确定任一结点的双亲、左孩子和右孩子的位置。,5.3二叉树的存

9、储结构,第5章 树与二叉数 第 14 页 2007-7-29,1.顺序存储结构,该方法是把二叉树的所有结点，按从上至下、从左至右的顺序，存储在一块地址连续的存储单元中。通常，用一维数组作为存储结构。,第5章 树与二叉数 第 15 页 2007-7-29,对于一般的二叉树来说，为了能够用结点在向量中的相对位置来表示结点之间的逻辑关系，也必须按完全二叉树的形式来存储树中的结点。例如，图5-7所示 。,容易看出，一般的二叉树用顺序存储结构容易造成存储空间的浪费。在最坏的情况下，一个深度为k且只有k个结点的右单枝树需要2k-1个结点的存储空间，而其中只有k个位置上存入了结点，空间利用率仅为k/(2k-

10、1)。,第5章 树与二叉数 第 16 页 2007-7-29,右单支二叉树,为克服顺序存储可能浪费存储空间的缺点，二叉树采用链式存储结构。,第5章 树与二叉数 第 17 页 2007-7-29,.链式存储结构,二叉链表结点的结构如图5-8所示。其中data域存储结点的值，lchild 域及rchild域分别存储指向左孩子和右孩子的指针。若不存在左孩子或右孩子，则其相应的指针域为空指针。此外，为每棵二叉树设立一个指向根结点的指针root。,若二叉树为空，则root为空指针 。,第5章 树与二叉数 第 18 页 2007-7-29,如果需要经常寻找二叉树中某个结点的双亲，可以在结点结构中增加一个指

11、向双亲的指针域parent。通常，将每个结点带3个指针域lchild、rchild、parent的链表称为二叉树的三叉链表。三叉链表结点结构如图5-10所示。,例如，图5-7所示二叉树的二叉链表表示可见图 5-9，三叉链表表示可见图5-11二叉链表是二叉树最常用的存储结构，,第5章 树与二叉数 第 19 页 2007-7-29,下面讨论的二叉树的遍历都是以二叉链表作为二叉树的存储结构。,第5章 树与二叉数 第 20 页 2007-7-29,二叉链表是二叉树最常用的存储结构，下面讨论的二叉树的遍历都是以二叉链表作为二叉树的存储结构。二叉链表中结点结构类型定义如下：,*typedef char T

12、elemType; /*TelemType为字符型，若需要可重新定义*/ typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;,第5章 树与二叉数 第 21 页 2007-7-29,如何按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的，每个结点都可能有两个直接后件结点，这将导致存在多条遍历路线。因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。,b,c,a,(根结

13、点),(右子树),(左子树),由二叉树的递归定义， 二叉树的三个基本组成 单元是：根结点、左子 树和右子树。,5.4遍历二叉树,第5章 树与二叉数 第 22 页 2007-7-29,假如以L、N、R分别表示遍历左子树、遍历根结点和 遍历右子树，遍历整个二叉树则有NLR、LNR、LRN、 NRL、RNL、RLN六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： NLR先（根）序遍历， LNR中（根）序遍历， LRN后（根）序遍历。 1、先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 2、中序遍历二叉树的操作

14、定义为： 若二叉树为空，则空操作；否则 （1）中序遍历左子树； （2）访问根结点；,第5章 树与二叉数 第 23 页 2007-7-29,（3）中序遍历右子树。 3、后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,第5章 树与二叉数 第 24 页 2007-7-29,例如图（1）所示的二叉树表达式 (a+b*(c-d)-e/f) 若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为： -+a*b-cd/ef 按中序遍历,其中序序列为： a+b*c-d-e/f 按后序遍历,其后序序列为： abcd-*

15、+ef/-,第5章 树与二叉数 第 25 页 2007-7-29,练习,如图所示二叉树的中序遍历序列是（ ）。 AabcdgefBdfebagcCdbaefcgDdefbagc,第5章 树与二叉数 第 26 页 2007-7-29,补充 根据遍历序列构造二叉树,由一棵给定的二叉树可以获得三种遍历序列，同样，也可以由这些遍历序列来重新构造二叉树。单用一个遍历序列是无法构造二叉树的，因为无法从遍历序列中区分二叉树的左、右子树。但利用中序遍历序列，并结合先序遍历序列或后序遍历序列就能重新构造二叉树。,第5章 树与二叉数 第 27 页 2007-7-29,根据二叉树的遍历定义，先序遍历序列和中序遍历序

16、列的结点分布特点是： 先序遍历序列： 中序遍历序列： ,第5章 树与二叉数 第 28 页 2007-7-29,可以得到二叉树的构造步骤： 1）从先序遍历序列中取出第一个结点，该结点一定是二叉树的根。然后在中序遍历序列中找到根结点，根结点前面的结点序列就是左子树的中序遍历序列，根结点后面的结点序列就是右子树的中序遍历序列。 2）对根的左子树先序遍历序列和中序遍历序列及右子树的先序遍历序列和中序遍历序列，再执行第一步，直到得出所有叶子结点为止。,第5章 树与二叉数 第 29 页 2007-7-29,利用中序遍历序列，并结合先序遍历序列或后序遍历序列重新构造二叉树。 例一 先序：ABCDEFGHIJ

17、 中序：CBDEAFHIGJ 例二 中序：ABCDJEFHGI 后序：BCJDAHIGFE,第5章 树与二叉数 第 30 页 2007-7-29,练习,1)已知一棵二叉树的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为（ ）。 AACFKDBGBGDBFKCACKCFAGDBDABCDFKG,2)已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。 AacbedBdecabCdeabcDcedba,第5章 树与二叉数 第 31 页 2007-7-29,*5.5 树的存储结构,树在计算机内有多种表示方法，下面介绍三种常用双亲表示法、

18、孩子表示法、孩子兄弟表示法。,1.双亲表示法,用一组连续空间存储数的结点，同时在每一个结点中附设一个指示器，指示其双亲结点的位置。图5-12 树的双亲表示法示例,第5章 树与二叉数 第 32 页 2007-7-29,图5-12 树的双亲表示法,第5章 树与二叉数 第 33 页 2007-7-29,2.孩子表示法,由于树中每个结点可能有多个孩子，因此可用多重链表来存储一棵树。链表中的结点由一个数据域和若干个指针域组成，每个指针域指向该结点的一个孩子。由于树中每个结点的度不同，所以链表中的结点可以采用定长表示，也可以采用不定长表示。,假设树的度数为d，则在定长表示中，结点的结构如图5-13所示。,

19、图5-13 孩子表示法的定长结点的结构,第5章 树与二叉数 第 34 页 2007-7-29,在不定长表示中，结点的结构如图5-14所示。,这里，data表示自身的数据，d表示结点的度，而ch1，ch2，chd 表示第1,2,d个孩子的指针。,图5-14 孩子表示法的不定长结点的结构,图5-15 就是图5-12 中树的多重链表表示。,第5章 树与二叉数 第 35 页 2007-7-29,图5-15 树的孩子表示法,第5章 树与二叉数 第 36 页 2007-7-29,如果把孩子链接成一个带表头结点的单链表，表头结点中存放双亲的信息，这些表头结点又组成一个线性表，那么图5-12中的树可用图5-1

20、6所示结构表示。该方法实际上是把双亲表示法和孩子表示法结合起来。,图5-16 树的带双亲的孩子链表表示法,第5章 树与二叉数 第 37 页 2007-7-29,3.孩子兄弟表示法,孩子兄弟表示法又称二叉链表表示法。在这种表示法中，结点的结构如图5-17所示。,图5-17 孩子兄弟表示法的结点结构,这里,data存放结点的有关信息,firstchild指向该结点的第一个孩子,nextbrother指向下一个兄弟结点。图5-18就是图5-12中树的孩子兄弟表示法。,第5章 树与二叉数 第 38 页 2007-7-29,图5-18 树的孩子兄弟表示法,第5章 树与二叉数 第 39 页 2007-7-

21、29,树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。 树和森林的存储结构与算法都很复杂，如果能够将树和森林转换为二叉树，不但可以采用二叉树的存储结构，而且可以利用二叉树的有关算法来实现树的有关操作。,5.6 森林与二叉树的转换,第5章 树与二叉数 第 40 页 2007-7-29,1.树转换为二叉树,将树转换成二叉树的方法为： （1）在兄弟之间加一连线； （2）对每个结点，除了其最左孩子外，去除它与其余孩子之间的联系； （3）将保留下来的边作为左子树的边，兄弟间的连线作为右子树的边（即各兄弟间的

22、连线依左边的兄弟结点为轴，顺时针旋转45度角）。 以图5-19（a）所示的树为例，可转换为如图5-19（d）所示的二叉树。,第5章 树与二叉数 第 41 页 2007-7-29,第5章 树与二叉数 第 42 页 2007-7-29,图5-19 树转换为二叉树示例,第5章 树与二叉数 第 43 页 2007-7-29,【例】下面(a)图所示的树可转换为(c)图所示的二叉树。 动画演示,第5章 树与二叉数 第 44 页 2007-7-29,从树转换为二叉树的过程可知，任何一棵树对应的二叉树，其右子树必空，也就是说，所有的树都可以转化为二叉树，但不是所有的二叉树都可以转化为树。,2.森林转换为二叉树

23、,森林是树的集合。将一个森林转换成二叉树的方法是：先将森林中的每棵树转换为二叉树，然后把各二叉树的根结点看成兄弟，用直线把它们连到一起，经整理后可得到相应的二叉树。,下面图5-20（b）是对图5-20（a）所示的森林进行转换后得到的结果，图5-20（c）是经整理后得到的二叉树。,第5章 树与二叉数 第 45 页 2007-7-29,图5-20(a)森林,图5-20(b)中间形式,第5章 树与二叉数 第 46 页 2007-7-29,对森林转换成二叉树的方法作出以下定义： 设F= T1,T2，Tn ，是一个由树T1,T2，Tn组成的森林，则森林F对应的二叉树B( T1,T2，Tn )（也记作B(

24、F)）如下： （1）若F为空（n=0），则B(F)为空树；,(c )转换结果 图5-20森林到二叉树的转换,第5章 树与二叉数 第 47 页 2007-7-29,（2）若F非空（n0），则B(F)的根就是T1 的根W1 ，B(F)的左子树是B(T11，T12，T1m)，其中T11，T12，T1m 是W1 的子树；B(F)的右子树是B( T2,T3，Tn )。,这是一个递归的定义。由此可知，对树和森林的运算都可以转换为对相应的二叉树的运算来实现。,第5章 树与二叉数 第 48 页 2007-7-29,【例】下图中，左边包含三棵树的森林可转换为右边的二叉树。,动画演示,第5章 树与二叉数 第 49

25、 页 2007-7-29,5.7 赫夫曼树及其应用,赫夫曼（Huffman）树，又称最优二叉树，是一类带权路径长度最短的二叉树。,常用几个基本术语 如下：,路径与路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。,树的路径长度：从树根到树的各个结点的路径长度之和称为树的路径长度，记作 PL 。,第5章 树与二叉数 第 50 页 2007-7-29,结点的权与带权路径长度：在实际应用中，常常给树中结点赋予一个具有某种实际意义的实数，该实数称为这个结点的权。结点的带权路径长度是该结点到树根之间的路径长度与结点的权的乘积。,树的带权路径长度：树中所

26、有叶子结点的带权路径长度之和称为树的带权路径长度，记作 WPL,第5章 树与二叉数 第 51 页 2007-7-29,Wi为叶子的权 ；Li为根结点到叶子之间的路径长度,图5-21 具有不同带权路径的二叉树,第5章 树与二叉数 第 52 页 2007-7-29,例如，上页图5-21中的(a)、(b)、(c)3棵二叉树，都有5个叶子结点，分别带权 2，3，4，6，7， 它们的路径长度及带权路径长度分别为：,PL(a)=1+1+2+2+2+2+3+3=16 PL(b)=1+1+2+2+3+3+4+4=20 PL(c)=1+1+2+2+2+2+3+3=16 WPL(a)=2*(2+3+4)+3*(6

27、+7)=57 WPL(b)=1*7+2*6+3*4+4*(2+3)=51 WPL(c)=2*(4+6+7)+3*(2+3)=49,第5章 树与二叉数 第 53 页 2007-7-29,1.赫夫曼树,在权值为W1，W2，Wn的 n个叶子所构成的所有二叉树中，带权路径长度最小的二叉树称为赫夫曼树。图5-20(c)所示的二叉树就是一棵赫夫曼树。,如何构造权集合W1，W2，Wn 的赫夫曼树呢？赫夫曼提出了如下算法： 1）给定的 n 个权值 为 W1，W2，Wn 构成有n棵二叉树的森林F=T1，T2，Tn，其中每棵二叉树Ti 只有一个权值为Wi的根结点，其左、右子树均为空。,2）森林F中至少还有两棵二叉

28、树时，重复下列步骤,第5章 树与二叉数 第 54 页 2007-7-29, 从森林F中选出两棵根结点的权值最小的二叉树T1和T2，如果这样的二叉树不止两棵，可以从中任选两棵，构造一棵新的二叉树T，使T1和T2分别为T的左子树和右子树，T的根的权值为T1 与T2 的根的权值之和，然后从森林中删去T1 和T2。, 将新二叉树T叉入森林F中。 假设有5棵，均仅有一个结点的二叉树，其权值分别为7，8，2，3，4构成森林F，并依权值从小到大排序的结果，如图5-22(a)所示；,图5-22(a),第5章 树与二叉数 第 55 页 2007-7-29,用根为2和3的二叉树生成根为5的二叉树，并重新排序的结果

29、，如图5-22( b )所示；,图5-22 (b),用根为4和5的二叉树生成根为9的二叉树，并重新排序的结果，如图5-22( c)所示；,图5-22 (c),第5章 树与二叉数 第 56 页 2007-7-29,用根为7和8的二叉树生成根为15的二叉树，并重新排序的结果，如图5-22( d )所示；,图5-22( d ),图5-22( e ),用根为9和15的二叉树生成根为24的二叉树，并重新排序的结果就是一棵哈夫曼树，如图5-22( e)所示；,第5章 树与二叉数 第 57 页 2007-7-29,例如，设给定的权集合为7，8，10，6，3，构成森林F并排序后，如图3（a）所示；用根为3和6

30、的二叉树生成根为9的二叉树，并重新排序后； 如图3（b）所示；重复进行下去，直到F中剩下一棵二叉树为止，便得到哈夫曼树； 如图3（e）所示，其带权路径长度为： WPL = 33 + 63 + 72 + 82 + 102 = 77,第5章 树与二叉数 第 58 页 2007-7-29,第5章 树与二叉数 第 59 页 2007-7-29,注意：在构造Huffman树的过程中，为了规范起见，我们规定集合F= T1，T2，Tn中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；权值相等时，选取深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树

31、的右子树。,第5章 树与二叉数 第 60 页 2007-7-29,练习,设给定权集w=2,3,4,7,8,9,试构造关于W的一棵Huffman树。 由分别带权为4，8，7，3，5的共五个叶子构成一棵哈夫曼树,第5章 树与二叉数 第 61 页 2007-7-29,用赫夫曼算法构造出来的二叉树一定是最优二叉树。从构造过程可以看出，权值最大的叶子离根最近，权值最小的叶子离根最远，所得二叉树必然具有最小的带权路径长度。,2.赫夫曼编码,赫夫曼树在通信、编码和数据压缩等技术领域有着广泛的应用。下面讨论在数据编码中的一个应用，即数据的最小冗余编码问题。,在通信业务中，可以用0和1所组成的编码来表示一个字符，一个字符序列可以用一个编码序列来表示。,第5章 树与二叉数 第 62 页 2007-7-29,假定文本中出现的字符集为26个字母，由242625知，最简单的编码方案是每个字母都用固定长度为5的二进制编码来表示。这种编码不考虑字符在文本中的出现频度(或次数),在实际应用中，字符集中各个字符的出现频度或使用次数是不相同的。有些字符经常出现，有些字符却很少见到。我们设计编码的目标是：希望用短的编码来表示那些出现频度大的字符，用长的编码来表示出现频度小的字符，从而使得所表示的字符序列（文本）