树和二叉树课件

《树和二叉树课件》由会员分享，可在线阅读，更多相关《树和二叉树课件（99页珍藏版）》请在金锄头文库上搜索。

1、第6章 树和二叉树,本章主要内容 树结构广泛存在,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 赫夫曼树及其应用,6.1 树的定义和基本术语,一、树的定义P118树(Tree)是n(n=0)个结点的有限集，在任意一棵非空树中(1)有且仅有一个特定的称为根（Root）的结点；（2）当n1时，其余结点棵分为m(m0)个互不相交的有限集T1,T2,Tm,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。基本术语P120 二、树的表示法P120 三、树的逻辑结构：非线性结构-层次结构 四、树的基本操作：初始化、建树、清空、求树的深

2、度、找双亲、找孩子、插入、删除、遍历等 五、ADT示,张源,族普,子树T1,子树T2,子树T3,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径：,孩子结点、双亲结点、 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,任何一棵非空树是一个二元组Tree = （root，F） 其中：root 被称为根结点，F 被称

3、为子树森林,森林：,是 m（m0）棵互 不相交的树的集合,A,root,F,(1) 有确定的根(2) 树根和子树根之间为有向关系,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (开始结点)(无前驱),根结点(无前驱),最后一个数据元素(终端结点)(无后继),多个叶子结点(无后继),其它数据元素 (一个直接前驱、一个直接后继),其它数据元素 (一个直接前驱、多个直接后继),树的表示法,1、树型图表示法： 2、嵌套集合表示法： 3、凹入表表示法： 4、广义表表示法：,广义表表示法,数

4、据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树；否则:(1) 在D中存在唯一的称为根的数据元素root,(2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm, 其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,基本操作：,查 找 类,插 入 类,删 除 类,Root(T) / 求树的根结点,查找类：,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e) / 求当前结点的双亲结点,LeftChild(T, cur_e) / 求当前结点的最左孩子,RightSibling

5、(T, cur_e) / 求当前结点的右兄弟,TreeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( T, Visit() ) / 遍历,InitTree(&T) / 初始化置空树,插入类：,CreateTree(&T, definition) / 按定义构造树,Assign(T, cur_e, value) / 给当前结点赋值,InsertChild(&T, &p, i, c) / 将以c为根的树插入为结点p的第i棵子树,ClearTree(&T) / 将树清空,删除类：,DestroyTree(&T) / 销毁树的结构,Dele

6、teChild(&T, &p, i) / 删除结点p的第i棵子树,6.2 二叉树,本节主要内容,6.2.1 二叉树的定义,6.2.2 二叉树的性质,6.2.3 二叉树的存储结构,6.2.1 二叉树的定义,一、二叉树的定义P121 二、二叉树的基本形态P123 三、二叉树的逻辑结构：非线性结构-层次结构 四、二叉树的基本操作：初始化、建树、清空、求树的深度、找双亲、找孩子、插入、删除、遍历等 五、ADTP121122,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,由二叉树的定义知:二叉树只有五种基本形态,N,空树,只含根结

7、点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,6.2.2 二叉树的性质,性质1、在二叉树的第i层上至多有2i-1个结点（i1）。 性质2、深度为k的二叉树至多有2k-1个结点（k1）。 性质3、对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则：n0=n2+1分析 例 满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。P124 完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且，最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。例 注,性质4、具有n个结点的完全二叉树的深度为：,log

8、2n +1,分析：令二叉树的深度为k，从而，2k-1-1n 2k-1,深度为k-1 的满二叉 树的结点数,深度为k的 满二叉树 的结点数, 2k-1 n 2k, k-1 log2n1，则其双亲PARENT(i)是结点i/2。 (2)如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。 (3)若2i+1n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。 注：可以用数学归纳法证明之，学生自己证明，我们用其结论。,1,2,3,4,5,6,7,8,9,10,11,12,对有n个结点的完全二叉树T从上到下且每层从左至右进行1至n的连续编号,观察编

9、号为i的结点的双亲、左孩子、右孩子的编号情况,注：,由完全二叉树的定义有以下结论： （1）叶子结点只可能在层次最大的两层上出现（最下两层）； （2）满二叉树一定是完全二叉树，反之不然； （3）完全二叉树中，若某结点无左孩子，则该结点一定无右孩子； （4）对任一结点，若其右分支下的子孙的最大层次为k，则其左分支下的子孙的最大层次必为k或k+1。,例、判定以下树中，哪些是满二叉树，哪些是完全二叉树。,是：完全二叉树，且是满二叉树,不是完全二叉树,不是完全二叉树,是完全二叉树,例1、设高度为h的二叉树T无度为1的结点，则二叉树T至少有多少个结点？至多有多少个结点？若二叉树T的叶子总数为m，则二叉树T

10、的结点总数为多少？,分析： （1）由于二叉树T无1度结点，从而当从第二层至第h层每层只有两个结点时，T的总结点数最少，而第一层只有树根，从而，T至少有：2(h-1)+1=2h-1个结点； （2）由二叉树的性质2知，T至多有2h-1个结点； （3）设n0、n1、n2、n分别为T的叶子结点数、1度结点数、2度结点数、结点总数，则有：n0=m，n1=0由二叉树的性质3有：n0=n2 +1，有n2= n0-1从而，n=n0+n1+n2=n0+0+n0-1=2n0-1=2m -1,分析：,分别用n0、n1、n2表示二叉树T中的度为0、1、2的结点数，依题意知n0=n，又二叉树T中所有非叶子结点都有左、右

11、子树，从而T中无度为1的结点，即n1 =0，由性质3有n2= n0-1= n-1 ，从而二叉树的结点总数为：n0+n1+n2=n+0+n-1=2n-1,用数学归纳法证明之（1）当n=1时，L1=1，显然有：,（2）设n=m-1时结论成立，即,下面证明n=m时结论成立不失一般性，设在hi层的叶子结点上加上两个孩子结点，则叶子结点总数加1，此时有：,成立,=,从而结论成立,=1,设n1为二叉树T度为1的结点数，n为结点总数，则有：n=n0+n1+n2考察二叉树的分支数：除了根结点外，其余每个结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点发出的，所以有B=n1+

12、2n2，于是得： n=n1+2n2+1于是有： n0+n1+n2=n1+2n2+1化简得： n0=n2 +1,分析：,6.2.3 二叉树的存储结构二种,一、顺序存储结构：P126 优、缺点 二、链式存储结构：P1261、结点结构：示2、 C语言形式描述P127,二叉树的二叉链表存储表示 -定义结点结构,用C语言形式描述为:,即,Typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;,有了存储结构，便可以讨论基本操作的实现了，进入下一节内容,（c）,二叉树的顺序存储结构,对于完全

13、二叉树，可对其结点按层序从上到下每层从左到右依次进行0至n-1的连续编号，并用一数组进行存储：将编号为i的结点存储于下标为i的存储单元中。,（d）,对于非完全二叉树，可先为其添加若干虚结点，将其补充为完全二叉树后，再按完全二叉树的方式进行顺序存储。,单支树,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况,左指针域,右指针域,数据域,存储指向左 孩子的指针,存储指向右 孩子的指针,存储结点 本身信息,左指针域,右指针域,数据域,双亲指针域,三叉链表树结点结构,lchild,data,rchild,示,二叉链表树结点结构,示意图见P127,二叉链表树直观示

14、意图,T,A,B,D,E,G,H,I,C,F,注,二叉链表树T为空的条件:T= =NULL,注：在含n个结点的二叉链表树中有n+1个空链域,分析：设n0、n1、n2、n分别为T的叶子结点数、1度结点数、2度结点数、结点总数，则有：n=n0+n1+n2， n0=n2 +1又，在二叉链表树中，每个叶子结点提供两个空链域，每个1度结点提供一个空链域，而2度结点不提供空链域，从而，空链域数= 2n0+n1=(n0+n1+n2)+(n0-n2 )=n +1,对完全二叉树较为适用，它存储简单、访问方便，但对于一般的二叉树在空间上浪费较大,二叉树的顺序存储结构的优、缺点：,6.3 遍历二叉树和线索二叉树,本

15、节主要内容:,6.3.1 遍历二叉树,6.3.2 线索二叉树,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次,问题的提出,“访问”的含义可以很广，如：输出结点的信息等,6.3.1 遍历二叉树,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题,对“二叉树”而言，可以有三条搜索路径,1先上后下的按层次遍历 2先左（子树）后右（子树）的遍历 3先右（子树）后左（子树）的遍历,设 访问根结点 记作 V遍历根的左子树 记作 L遍历根的右子树 记作 R则可能的遍历次序有前序 VLR 逆前序 VRL中序 LVR 逆中序 RVL后序 LRV 逆后序 RLV层次遍历：从上到下，从左到右,