第4章树结构介绍ppt课件.ppt

《第4章树结构介绍ppt课件.ppt》由会员分享，可在线阅读，更多相关《第4章树结构介绍ppt课件.ppt（100页珍藏版）》请在三一办公上搜索。

1、第4章 树结构,2023年1月10日,1教学内容 二叉树和树的概念、二叉树的遍历及其应用、线索二叉树、哈夫曼树及哈夫曼编码、树和森林与二叉树之间的转换、树或森林的遍历。教学目的 深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；掌握二叉树的三种遍历算法；了解二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题;掌握森林与二叉树间的相互转换；掌握树和森林的遍历方法。,2023年1月10日,教学重点：二叉树的定义、逻辑特点及性质；二叉树的存储结构；二叉树的遍历方法及其算法；以遍历为基础在二叉树上实现的几种运算；哈夫曼树和哈夫曼算法；树的存储结构

2、；森林与二叉树的转换。教学难点：二叉树的递归定义；二叉树链式存储结构的组织方式；三种遍历的算法；二叉树上的复杂运算；哈夫曼算法及其应用；,2023年1月10日,4.1 引言,4.1.1 问题提出问题1：组织结构层次关系的存储与查找。问题2：家族族谱中家族成员之间的关系表示与查找。问题3：图书馆中图书的分类关系的建立。,2023年1月10日,1树的定义,树（Tree）是n（n0）个有限数据元素的集合。当n0时，称这棵树为空树。在一棵非空树T中：(1)有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。(2)若n1，除根结点之外的其余数据元素被分成m（m0）个互不相交的集合T1,T2,Tm，其

3、中每一个集合Ti（1im）本身又是一棵树。树T1,T2,Tm称为这个根结点的子树。,4.1.2 相关概念,2023年1月10日,2023年1月10日,树具有下面两个特点：树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。树中所有结点可以有零个或多个后继结点。由此特点可知，下图所示的都不是树结构。,2023年1月10日,3相关术语(1)结点的度(2)叶结点(3)分支结点(4)左孩子、右孩子、双亲、兄弟,(5)路径、路径长度(6)祖先、子孙(7)结点的层数(8)树的深度,2023年1月10日,（9）树的度（10）有序树和无序树（11）森林,2023年1月10日,1二叉树的定义,4

4、.2.1 二叉树的概念,4.2 二叉树,2023年1月10日,2二叉树的相关术语(1)满二叉树。,2023年1月10日,(2)完全二叉树。,2023年1月10日,3.二叉树的基本操作(1)Initiate(bt)(2)Create(x,lbt,rbt)(3)InsertL(bt,x,parent)(4)InsertR(bt,x,parent)(5)DeleteL(bt,parent)(6)DeleteR(bt,parent)(7)Search(bt,x)(8)Traverse(bt),2023年1月10日,4.2.2 二叉树的主要性质,性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i1

5、）。性质2 一棵深度为k的二叉树中，最多具有2k1个结点。性质3 对于一棵非空的二叉树，若叶子结点数为n0，度数为2的结点数为n2，则有：n0n21。性质4 具有n个结点的完全二叉树的深度k为：log2n+1,2023年1月10日,性质5:对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：如果i1，则序号为i的结点的双亲结点的序号为i/2；如果i1，则序号为i的结点是根结点，无双亲结点。如果2in，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。如果2i1n，则序号为i的结点的右孩

6、子结点的序号为2i1；如果2i1n，则序号为i的结点无右孩子。此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为(i1)/2，左孩子的编号为2i1，右孩子的编号为2i2。,2023年1月10日,4.2.3 二叉树的存储,1顺序存储结构 所谓二叉树的顺序存储，是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。,2023年1月10日,下面给出一棵完全二叉树的顺序存储示意。,2023年1月10日,对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关

7、系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。,2023年1月10日,极端情况是单支树，如一棵深度为k的右单支树，只有k个结点，却需分配2k1个存储单元。,显然，对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。,2023年1月10日,二叉树的顺序存储结构可描述为：#define MAXNODE 1024/二叉树的最大结点数，可根据实际情况进行修改 typedef datatype SqBiTreeMAXNODE;/0号单元存放根结点 定义一个顺序存储的二叉树变量：SqBiTree bt;即

8、将bt为含有MAXNODE个datatype类型元素的一维数组。,2023年1月10日,2链式存储结构(1)二叉链表存储,2023年1月10日,下图(a)给出一棵二叉树的二叉链表存储表示。二叉链表也可以带头结点的方式存放，如图(b)所示。,2023年1月10日,二叉树的二叉链表存储结构可描述为：typedef struct bitnode datatype data;struct bitnode*lchild;*rchild;/左右孩子指针 BiTNode,*BiTree;定义一个指向二叉树的指针变量：BiTree t;,2023年1月10日,(2)三叉链表存储 每个结点由四个域组成，具体结构

9、为：,2023年1月10日,下图给出一棵二叉树的三叉链表存储示意图。,2023年1月10日,4.2.4 二叉树基本运算的实现,算法的实现依赖于具体的存储结构，当二叉树采用不同的存储结构时，上述各种操作的实现算法是不同的。下面讨论基于二叉链表存储结构的上述操作的实现算法。,2023年1月10日,(1)Initiate(bt)：建立一棵空的二叉树bt，并返回bt。,2023年1月10日,(2)Create(x，lbt，rbt)：生成一棵以x为根结点的数据域值以lbt和rbt为左右子树的二叉树。,2023年1月10日,(3)InsertL(bt,x,parent)：在二叉树bt中的parent所指结

10、点和其左子树之间插入数据元素为x的结点,(4)InsertR(bt，x，parent)：功能类同于(3)，算法略。,2023年1月10日,(5)DeleteL(bt，parent)：在二叉树bt中删除parent的左子树,(6)DeleteR(bt，parent)：算法略。,2023年1月10日,4.3 二叉树的遍历,二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。二叉树遍历是二叉树中最重要最基本的运算。,2023年1月10日,4.3.1 递归方法实现二叉树的三种遍历,若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，如果限定先左

11、后右，则有三种方式，即：DLR（称为先序遍历)LDR（称为中序遍历)LRD（称为后序遍历)。,2023年1月10日,1先序遍历先序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)访问根结点；(2)先序遍历根结点的左子树；(3)先序遍历根结点的右子树。,2023年1月10日,对于上图所示的二叉树，按先序遍历所得到的结点序列为：A B D G C E F,2023年1月10日,2中序遍历中序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)中序遍历根结点的左子树；(2)访问根结点；(3)中序遍历根结点的右子树。,2023年1月10日,对于上图所示的二叉树，按中序遍历所得到的结点序列为：D

12、 G B A E C F,2023年1月10日,3后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)后序遍历根结点的左子树；(2)后序遍历根结点的右子树；(3)访问根结点。,2023年1月10日,对于上图所示的二叉树，按后序遍历所得到的结点序列为：G D B E F C A,2023年1月10日,4.3.2 非递归方法实现二叉树的三种遍历,1、包络线 下图中所示的从根结点左外侧开始，由根结点右外侧结束的曲线，称其为该二叉树的包络线，二叉树的遍历是沿着该线路进行的。沿着该路线按标记的结点读得的序列为先序序列，按*标记读得的序列为中序序列，按标记读得的序列为后序序列。,2023年1

13、月10日,2、栈的使用 先序遍历是沿着包络线深入时遇到结点就访问；中序遍历是在从左子树返回时遇到结点访问；后序遍历是在从右子树返回时遇到结点访问。,2023年1月10日,3、遍历算法(1)先序遍历的非递归实现,2023年1月10日,(2)中序遍历的非递归实现 中序遍历的非递归算法的实现，只需将先序遍历的非递归算法中的Visit(p-data)移到p=stacktop和p=p-rchild之间即可。,2023年1月10日,(3)后序遍历的非递归实现 特点：每一个结点两次入栈两次出栈。,2023年1月10日,2023年1月10日,4.3.3 按层次遍历二叉树 所谓二叉树的层次遍历，是指从二叉树的第

14、一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于下图所示的二叉树，按层次遍历所得到的结果序列为：A B C D E F G,2023年1月10日,1、队列的使用 在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：访问该元素所指结点；若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。,2023年1月10日,2023年1月10日,4.4 二叉树遍历的应用,4.4.1 构造二叉

15、树的二叉链表存储 构建一棵二叉树的二叉链表也是基于遍历的过程进行的。这里按照先序遍历的过程构建。首先建立二叉树带空指针的先序次序，依此作为构建时结点的输入顺序，如对于下图所示的二叉树，输入序列为：ABD0G000CE00F00（0表示空，为了简化问题，设数据元素的类型为字符型）。,2023年1月10日,2023年1月10日,4.4.2 在二叉树中查找值为x的数据元素,2023年1月10日,4.4.3 统计给定二叉树中叶子结点的数目,2023年1月10日,4.4.4 由遍历序列恢复二叉树,从前面讨论的二叉树的遍历知道，任意一棵二叉树结点的先序序列和中序序列都是唯一的。反过来，若已知结点的先序序列

16、和中序序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？,2023年1月10日,2、分隔过程：已知一棵二叉树的先序序列与中序序列分别为：A B C D E F G H I，B C A E D G H F I，试恢复该二叉树。,1、依据遍历定义：由二叉树的先序序列和中序序列可唯一地确定该二叉树。由二叉树的后序序列和中序序列也可唯一地确定该二叉树。由二叉树的先序序列和后序序列不能唯一地确定该二叉树。,2023年1月10日,2023年1月10日,4.5 线索二叉树,4.5.1 线索二叉树的定义及结构1线索二叉树的定义利用二叉链表中左、右空指针建立起指向前驱后继的指针，称之为线索。,2023

17、年1月10日,2线索二叉树的结构图中实线表示指针，虚线表示线索。,2023年1月10日,指向孩子的指针和线索都是地址，如何区别某结点的指针域内存放的是指针还是线索？方法是为每个结点增设两个标志位域ltag和rtag，令：ltag rtag 结点结构为：,2023年1月10日,线索二叉树的结点定义如下：typedef struct BiThrNode datatype data;struct BiThrNode*lchild;struct BiThrNode*rchild;unsigned ltag;unsigned rtag;BiThrNodeType,*BiThrTree;,2023年1月1

18、0日,4.5.2 线索二叉树的构建,2023年1月10日,1在中序线索树上查找任意结点的中序前驱结点,4.5.3 线索二叉树的遍历,2023年1月10日,2在中序线索树上查找某结点的中序后继结点,2023年1月10日,3线索树的遍历,2023年1月10日,4在中序线索二叉树上的更新 线索二叉树的更新是指，在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。讨论一种比较简单的情况，即在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。,2023年1月10日,2023年1月10日,4.6 最优二叉树,4.6.

19、1问题的引入 一个将百分制转换为五级分制的判定程序可以用以下条件语句完成：if(a60)b=”bad”;else if(a70)b=”pass”else if(a80)b=”general”else if(a90)b=”good”else b=”excellent”;判定过程如下图所示。,2023年1月10日,判定方法是多样的，也可以采用下面的判定过程来完成。,2023年1月10日,假设有10000个输入数据，若按图(a)的判定过程进行操作，则总共需进行31500次比较；而若按图(c)的判定过程进行操作，则总共仅需进行22000次比较。,如果输入量很大，则应考虑上述程序的质量问题，即其操作所需

20、要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示：分数 059 6069 7079 8089 90100比例数 0.05 0.15 0.40 0.30 0.10,2023年1月10日,几个基本概念:1结点的权2带权路径长度设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度。记为：WPL WkLk 其中Wk为第k个叶结点的权值，Lk 为第k个叶结点的路径长度。,2023年1月10日,在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。下图中的每棵二叉树都有4个结点，且权值相同，但其带权

21、路径长度不同，分别为：（a）WPL1232527232（b）WPL1333527129（c）WPL1233537133（d）WPL7353321143（e）WPL7152331329,2023年1月10日,3哈夫曼（Haffman）树：哈夫曼树也称最优二叉树。由上面的例子可见，由相同权值的一组叶子结点所构成的二叉树可能有不同的形态和不同的带权路径长度，具有最小带权路径长度的二叉树称为哈夫曼（Haffman）树，也称最优二叉树。最优二叉树在实际问题中有很重要的应用。,2023年1月10日,4.6.2 最优二叉树的构造1、构造方法 哈夫曼（Haffman）依据这一特点提出了一种方法，这种方法的基本

22、思想是：（1）由给定的n个权值W1，W2，Wn构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合FT1，T2，Tn；（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；（4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。,2023年1月10日,下图给出前面提到的叶结点权值集合为W1，3，5，7的哈夫曼树的构造过程。可以计算出其带权路径长度为29。,2023年1月10日,2、算法实现,2

23、023年1月10日,4.6.3 最优二叉树的应用-哈夫曼编码,利用哈夫曼树可以对字符编出效率最高的编码，称为的哈夫曼码。1、编码方法(1)设需要编码的字符集合为d1，d2，dn，它们在电文中出现的次数或频率集合为w1，w2，wn，以d1，d2，dn作为叶结点，w1，w2，wn作为它们的权值，构造一棵哈夫曼树。(2)规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。,2023年1月10日,2、哈夫曼编码的算法实现,2023年1月10日,4.7 树和森林,4.7.1树的基本操作与表示1.树的基本操作(

24、1)Initiate(t)：初始化一棵空树t。(2)Root(x)：求结点x所在树的根结点。(3)Parent(t,x)：求树t中结点x的双亲结点。(4)Child(t,x,i)：求树t中结点x的第i个孩子结点。(5)RightSibling(t,x)：求树t中结点x的第一个右 边兄弟结点。(6)Insert(t,x,i,s)：把以s为根结点的树插入到树t中作为结点x的第i棵子树。(7)Delete(t,x,i)：在树t中删除结点x的第i棵子树。(8)Tranverse(t)：是树的遍历操作，即按某种方式访问树t中的每个结点，且使每个结点只被访问一次。,2023年1月10日,2.树的四种表示方

25、法(1)直观表示法 树的直观表示法就是以倒着的分支树的形式表示，下图就是一棵树的直观表示。其特点就是对树的逻辑结构的描述非常直观。是数据结构中最常用的树的描述方法。,2023年1月10日,(2)嵌套集合表示法,2023年1月10日,(3)凹入表示法,(4)广义表表示法(A(B(D,E(H,I),F),C(G),2023年1月10日,4.7.2 树的存储,1双亲链表存储方法#define MAXNODE 1024/树中结点的最大个数，可根据实际情况进行修改typedef struct datatype data;int parent;PNode;PNode tMAXNODE;,2023年1月10

26、日,下图所示为树的双亲表示。图中用parent域的值为-1表示该结点无双亲结点，即该结点是一个根结点。,2023年1月10日,2指向孩子的链表存储方法 多重链表法 令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法又常称为多重链表法。,2023年1月10日,孩子链表表示法,2023年1月10日,3双亲孩子链表存储方法,2023年1月10日,4孩子兄弟链表存储方法,从树的孩子兄弟表示法可以看到，如果设定一定规则，就可用二叉树结构表示树和森林，这样，对树

27、的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。,2023年1月10日,4.7.3 树和森林与二叉树之间的转换,转换的方法依据树的孩子-兄弟存储方法，将一棵树转换为二叉树的方法是：(1)树中每个结点的第一个孩子留作该结点的左孩子；(2)从结点的第二个孩子起，将作为原左兄弟的右孩子。之间的连线，删去它与其它孩子结点之间的连线。,1.树转换为二叉树,2023年1月10日,由上面的转换可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。,2023年1月10日,2.森林转换为

28、二叉树,森林转换为二叉树的方法如下：(1)将森林中的每棵树转换成相应的二叉树。(2)第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。,2023年1月10日,下图给出森林及其转换为二叉树的过程。,2023年1月10日,3.二叉树转换为树和森林,树和森林转换为二叉树的过程是可逆的，具体方法如下：若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子都与该结点的双亲结点用线连起来；删去原二叉树中所有的双亲结点与右孩子结点的连线；整理由、两步所得到的树或森林，使之结构层次分明。,2

29、023年1月10日,下图给出一棵二叉树还原为森林的过程示意。,2023年1月10日,1.树的遍历,（1）先序遍历 先序遍历的定义为：若树为空，遍历结束；否则:(1)访问根结点；(2)按照从左到右的顺序先序遍历根结点的每一棵子树。,按照树的先根遍历的定义，对上图所示的树进行先根遍历，得到的结果序列为：A B E F C D G,4.7.4 树和森林的遍历,2023年1月10日,2后序遍历 后序遍历的定义为：若树为空，遍历结束；否则:(1)按照从左到右的顺序后序遍历根结点的每一棵子树；(2)访问根结点。按照树的后序遍历的定义，对下图所示的树进行后根遍历，得到的结果序列为：E F B C G D A

30、,2023年1月10日,2.森林的遍历,（1）先序遍历 先序遍历的定义为：若森林为空，遍历结束；否则：(1)访问森林中第一棵树的根结点；(2)先序遍历第一棵树的根结点的子树；(3)先序遍历去掉第一棵树后的子森林。对于下图所示的森林进行前序遍历，得到的结果序列为：A B C D E F G H J I K,2023年1月10日,（2）后序遍历 后序遍历的定义为：若森林为空，遍历结束；否则：(1)后序遍历第一棵树的根结点的子树；(2)访问森林中第一棵树的根结点；(3)后序遍历去掉第一棵树后的子森林。对于下图所示的森林进行中序遍历，得到的结果序列为：B A D E F C J H K I G,202

31、3年1月10日,4.7.5 树的应用,1、集合的表示 集合是一种常用的数据表示方法，对集合可以作多种操作，假设集合S由若干个元素组成，可以按照某一规则把集合S划分成若干个互不相交的子集合，例如，集合S1，2，3，4，5，6，7，8，9，10，可以被分成如下三个互不相交的子集合：S11，2，4，7 S23，5，8 S36，9，10 集合S1，S2，S3就被称为集合S的一个划分。此外，在集合上还有最常用的一些运算，比如集合的交、并、补、差以及判定一个元素是否是集合中的元素，等等。,2023年1月10日,用树中的一个结点表示集合中的一个元素，树结构采用双亲表示法存储。例如，集合S1、S2和S3可分别表示为图(a)、(b)、(c)所示的结构。将它们作为集合S的一个划分，存储在一维数组中，如下图所示。,2023年1月10日,2.集合的运算,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,