《第六章树和二叉树1.ppt》由会员分享，可在线阅读，更多相关《第六章树和二叉树1.ppt（52页珍藏版）》请在三一办公上搜索。
1、1,数据结构课程的内容,2,第6章 树和二叉树（Tree&Binary Tree）,6.1 树的基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用,特点：非线性结构，一个直接前驱，但可能有多个直接后继。,（一对多，或称1:n）,3,6.1 树的基本概念,6.1.1 树的定义6.1.2 若干术语6.1.3 逻辑结构6.1.4 存储结构6.1.5 树的运算,数据关系：若 D 为空集，则称为空树；(n=0)若 D 中仅含一个数据元素，则关系R为空集；(n0)否则 R=H，(1)在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱；(2)当n1时，其
2、余数据元素可分为 m(m0)个互不相交的(非空)有限集 T1,T2,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 H,i=1,2,m。,树的抽象数据类型的定义如下：数据对象：D是具有相同特性的数据元素的集合。,在这13 个数据元素之间存在下列关系：R=,。,5,6.1.1 树的定义,注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即“树中还有树”。,由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m
3、(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。,6,6.1.2 若干术语,即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点,根 叶子 森林有序树无序树,即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数),双亲孩子兄弟堂兄弟祖先子孙,结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。,7,即树的数据元素结点挂接的子树数,结点结点的度结点的层次终端结点
4、分支结点,树的度树的深度(或高度),从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）,所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数；树的度；树的深度,13,3,4,（有几个直接后继就是几度，亦称“次数”）,8,树的抽象数据类型定义,（见教材P118-119）,ADT Tree数据对象D:数据关系R:基本操作 P：ADT Tree,D是具有相同特性的数据元素的集合。若D为空集，则称为空树；/允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：root 唯一/关于根的说明
5、 DjDk=/关于子树不相交的说明/关于数据元素的说明/至少有15个，如求树深，求某结点的双亲,9,6.1.3树的逻辑结构,一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,6.1.4树的存储结构,讨论1：树是非线性结构，该怎样存储？,特点：,仍然有顺序存储、链式存储等方式。,10,讨论3：树的链式存储方案应该怎样制定？,复原困难,可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。,可否
6、规定为：,从上至下、从左至右将树的结点依次存入内存。,有重大缺陷：,不能唯一复原就没有实用价值！,讨论2：树的顺序存储方案应该怎样制定？,困惑：到底应当开多少个链域?,补充：树的5种表示法：,图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子右兄弟表示法,意义：把一般的树转化为最简单、最有规律的二叉树再研究，然后设法从二叉树再转回多叉树。,12,图形表示法,福州大学,叶子,根,子树,13,嵌套集合表示法,14,(A(B(E(K,L),F),C(G),D(H(M),I,J)约定：根作为由子树森林组成的表的名字写在表的左边,广义表表示法,15,凹入表示法,又称目录表示法,16,左孩子右兄弟表示法
7、,意义：多叉树转为二叉树！,将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,树转二叉树举例：,将二叉树还原成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,要点：逆操作，把所有右孩子变为兄弟！,19,6.1.5树的运算,要明确：1.普通树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是插入、删除、修改、
8、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！,本章重点：二叉树的表示和实现,遍历指每个结点都被访问且仅访问一次，不遗漏不重复,20,6.2 二叉树,为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3 二叉树的存储结构,注：二叉树最重要的运算是：遍历！,21,6.2.1二叉树的定义,定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:每个结点最多只有两
9、棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒。,问：具有3个结点的二叉树可能有几种不同形态？,有5种,基本形态：,22,二叉树的抽象数据类型定义（见教材P121-122）,ADT BinaryTree数据对象D:数据关系R:基本操作 P：ADT BinaryTree,D是具有相同特性的数据元素的集合。若D=，则R=；若D，则R=H；存在二元关系：root 唯一/关于根的说明 DjDk=/关于子树不相交的说明/关于数据元素的说明/关于左子树和右子树的说明/至少有20个，如返回某结点的左孩子，或中序遍历，等等,几种特殊形式的二叉树,满二叉树定义：,特点：每一层上的结点数都是最大结点数
10、完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1,25,6.2.2二叉树的性质(3+2),讨论1：第i层的结点数最多是多少？（利用二进制性质可轻松求出）,性质1:在二叉树的第i层上至多有2i-1个结点（i0）。,性质2:深度为k的二叉树至多有2k-1个结点（k0）。,再提问：第i层上至少有 个结点？,1,讨论2：深度为k的二叉树，最多有多少个结点？（利用二进制性质可轻松求出）,2i-1个
11、,2k-1个,26,6.2.2二叉树的性质(3+2),性质1:在二叉树的第i层上至多有2i-1个结点（i0）,性质2:深度为k的二叉树至多有2k-1个结点（k0）,性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21（即n0=n2+1）,性质4:具有n个结点的完全二叉树的深度必为log2n1,性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i1；其双亲的编号必为i/2（i1 时为根,除外）。,27,3.深度为9的二叉树中至少有 个结点。)9)8)91,2.深度为的二叉树的结点总数，最多为 个。)k-1)log
12、2k)k)k,1.树中各结点的度的最大值称为树的。)高度)层次)深度)度,D,C,C,课堂练习：,28,性质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,讨论：二叉树的叶子数和度为2的结点数之间有关系吗？,
13、29,完全二叉树：深度为k 的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。,为何要研究这两种特殊形式？,因为它们在顺序存储方式下可以复原！,讨论：满二叉树：一棵深度为k 且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）,解释：完全二叉树的特点是只有最后一层叶子不满，且全部集中在左边。但这其实是顺序二叉树的含义。,满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。,30,性质4:具有n个结点的完全二叉树的深度必为l
14、og2n1,性质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,可根据归纳法证明。,对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：,一棵完全二叉树有1000个结点，则它必有 个
15、叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。,例：,1,0,分析题意：已知n=1000,求n0和n2,还要判断末叶子是挂在左边还是右边？,正确答案：全部叶子数1000/2=500个。度为2的结点叶子总数1=499个。因为最后一个结点坐标是偶数，所以必为左子树。,请注意：叶子结点总数末层叶子数！,32,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,ABCDE,缺点：浪费空间；插入、删除不便,33,二、链式存储结构用二叉链表即可方便表示。,二叉树结点数据类型定义：typedef struct n
16、ode*tree_pointer;typedef struct node int data;tree_pointer left_child,right_child;node;,一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,34,二叉树链式存储举例：,优点：不浪费空间；插入、删除方便,35,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树,遍历定义遍历用途遍历方法,指按某条搜索路线遍访每个结点且不重复（又称周游）。,它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算
17、的基础和核心。,对每个结点的查看通常都是“先左后右”。,Traversing Binary Tree,36,遍历规则,二叉树由根、左子树、右子树构成，定义为D、L、R,以根结点为参照系,注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD 若限定先左后右，则有三种实现方案：,DLR LDR LRD先序遍历 中序遍历 后序遍历,D L R,先序遍历序列：A B D C,先序遍历:先访问根结点,然后分别先序遍历左子树、右子树,L D R,中序遍历序列：B D A C,中序遍历:先中序遍历左
18、子树，然后访问根结点，最后中序遍历右子树,L R D,后序遍历序列：D B C A,后序遍历:先后序遍历左、右子树，然后访问根结点,40,例1：,先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：,D B E A CD E B C A,口诀：DLR先序遍历，即先根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根,A,B,D,E,C,41,先序遍历结果+*/A B C D E前缀表示法中序遍历结果A/B*C*D+E中缀表示法后序遍历结果A B/C*D*E+后缀表示法层次遍历结果+*E*D/C A B,例2：用二叉树表示算术表达式,void PreOrder(BiTree
19、bt)if(bt=NULL)return；printf(%dt,bt-data);PreOrder(bt-lchild);PreOrder(bt-rchild);,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,43,对遍历的分析：,1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径上，每个结点经过3次。,第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历,2.二叉树遍历的时间效率和空间效率时间效
20、率:O(n)/每个结点只访问一次空间效率:O(n)/栈占用的最大辅助空间,44,中序遍历算法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 nodeint data;struct node*lchild,
21、*rchild；node;node*root;,先序遍历算法DLR(node*root)if(root!=NULL)/非空二叉树 printf(“%d”,root-data);/访问DDLR(root-lchild);/递归遍历左子树DLR(root-rchild);/递归遍历右子树 return(0);,45,例：【严题集6.42】编写递归算法，计算二叉树中叶子结点的数目。,思路：若左右指针均空，必为叶子。可选用任何一种遍历算法查找叶子，将其统计并打印出来。,DLR(node*root)/采用先序遍历的递归算法 if(root!=NULL)/非空二叉树条件，等效于 if(root)if(!r
22、oot-lchild,求二叉树的深度,void BiTreeDepth(BiTree T,int level,int,在二叉树上查询某个结点,void locate(BiTree T,ElemType x,BiTree,48,用空格字符表示无孩子或指针为空,如何把二叉树存入电脑内？,怎样建树？见教材P131例,例：将下面的二叉树以二叉链表形式存入计算机内。,考虑1：输入结点时怎样表示“无孩子”？考虑2：以何种遍历方式来输入和建树？,将二叉树按先序遍历次序输入：A B C D E G F(/n),以先序遍历最为合适，让每个结点都能及时被连接到位。,49,建树算法：Status CreateBiT
23、ree(BiTree/CreateBiTree,输入序列：A B C D E G F,50,特别讨论：若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？,例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。分析：由后序遍历特征，根结点必在后序序列尾部（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。,51,已知中序遍历：B D C E A F H G已知后序遍历：D E C B H G F A,（B D C E）,（F H G）,A,（D C E）,A,B,B,A,C,C,D C E,详细说明：,52,例：试写出如图所示的二叉树按中序遍历时得到的结点序列。,答：LDR：B F J D G K A C H E L I M,例：由1001个结点构成的二叉树，何种型态叶子结点最多，何种叶子最少？分别给出叶子结点个数和度为1结点的个数。答：因为 n=n0+n1+n2n=2*n2+1+n1 完全二叉树叶子最多-叶子结点501个,度为1结点的个数为0；单支树的叶子最少-叶子结点个数为1，度为1结点的个数1000,
