自考数据结构第四章ppt课件.ppt

《自考数据结构第四章ppt课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构第四章ppt课件.ppt（65页珍藏版）》请在三一办公上搜索。

1、第四章 树和二叉树,第四章 树和二叉树,4.1 树的基本概念4.2 二叉树4.3 二叉树的存储结构4.4 二叉树的遍历4.5 树和森林4.6 判定树和哈夫曼树,树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。,4.1 树的定义和基本术语,树（Tree）是n(n=0)个结点的有限集合T，满足： (1)当n

2、=0时，称为空树； (2)当n0时，有且仅有一个特定的称为根的结点,其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集Ti又是一棵树，并称为根的子树。,一、树的定义,递归是树的固有特性,二、树的逻辑表示 一般表示法(直观表示法)：,b、嵌套括号法： (根(子树,子树子树)( A ( B ( E, F ), C , D ( G ) ),c、凹入法表示：,另三种表示法,a、文氏图法：,三、树的基本术语,度,结点的度：该结点的子树数（即分支数）。,树的度：树中结点的度最大值。,结点由一个数据元素及若干指向其它结点的分支所组成。,叶子（终端结点）度为零的结点。,孩子（子结点

3、）结点的子树的根称为该结点的孩子。,相应的该结点称为孩子的双亲（父结点）。,非终端结点度不为零的结点。,祖先结点祖先指根到此结点的一条路径上的所有结点。,子孙从某结点到叶结点的分支上的所有结点称为该结 点的子孙。,兄弟父结点相同的结点互称兄弟。,结点的层次从根算起，根为第一层，其孩子在第二层, .， L层上任何结点的孩子都在L+1层上。,树的深度树中结点的最大层次数。,森林是m（0）棵互不相交的树的集合。,有序树若树中各结点的子树从左到右是有次序的， 不能互换，称为有序树。,无序树若树中各结点的子树是无次序的， 可以互换，则成为无序树。,求根Root(T):求树T的根结点；求双亲Parent(

4、T,X):求结点X在树T上的双亲结点；若X是树T的根或X不在T上，则结果为一特殊标志；求孩子Child(T,X,i):求树T上结点X的第i个孩子结点；若X不在T上或X没有第i个孩子，则结果为一特殊标志；建树Create(X,T1,Tk),k1:建立一棵以X为根，以T1,Tk为第1,k棵子树的树；剪枝Delete(T,X,i):删除树T上结点X的第i棵子树；若T无第i棵子树，则为空操作；遍历Traverse Tree(T):遍历树，即访问树中每个结点，且每个结点仅被访问一次。,四、树的基本操作,二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理表示，而任何树都可以与

5、二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。,4.2 二叉树,1、定义： 二叉树是n(n=0)个结点的有限集合，它或为空(n=0)，或是由一个根结点及两棵互不相交的左、右子树组成，且每棵子树都是二叉树。,4.2.1 二叉树的基本概念,这是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。,2、特点： 二叉树可以是空的，称空二叉树； 每个结点最多只能有两个孩子； 子树有左、右之分且次序不能颠倒。,、二叉树与树的比较：,二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的5

6、种基本形态，图(c) 和（d）是不同的两棵二叉树。,(a) 空二叉树,A,(b) 左右子树均为空的二叉树,A,(c) 右子树为空 的二叉树,A,(d)左子树为空的二叉树,A,(e)左右子树非空的二叉树,二叉树的5种形式,初始化Initiate(BT):建立一棵空二叉树，BT=。求双亲Parent(BT,X):求出二叉树BT上结点X的双亲结点，若X是BT的根或X根本不是BT上的结点，运算结果为NULL。求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X不在BT上，运算结果为NULL。建二叉树Create(BT):建立一

7、棵二叉树BT。先序遍历PreOrder(BT)(根、左、右):按先序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。,4、二叉树的基本运算（见P96）,中序遍历InOrder(BT)（左、根、右）:按中序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。后序遍历PostOrder(BT)（左、右、根）:按后序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。层次遍历LevelOrder(BT):按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，若

8、BT为空，则运算为空操作。,1、性质1： 在二叉树的第i(i=1)层上至多有2i-1个结点。,二叉树具有下列重要性质：,4.2.2 二叉树的性质,2、性质2：深度为k(k=1)的二叉树至多有2k1个结点。,3、性质3：对任何一棵二叉树，如果其终端结点 数为n0，度为2的结点数为n2，则n0n21。 即：叶结点数n0=度为2的结点数n2+1,满二叉树中结点顺序编号：即从第一层结点开始自上 而下，从左到右进行连续编号。,满二叉树深度为k(k=1)且有2k-1个结点的二叉树。,1,2,3,4,5,6,7,注：满二叉树是完全二叉树的特例。,完全二叉树深度为K的二叉树中，K-1层结点数是满的(2k-2

9、)，K层结点是左连续的(即结点编号是连续的)。如下图（a）,符号x表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1 或 2k-1=n2k取对数得到：k1log2nk 因为k是整数。所以：klog2n1。,4、性质4：具有n个结点的完全二叉树的深 度为log2n1。,5、性质5： 对有n个结点的完全二叉树的结点按层编号 （从第1层到第log2n+1层，每层从左到右), 则对任一结点i（1in),有：（1）如果i1，则结点i无双亲，是二叉树的根； 如果i1，则i的双亲Parent(A)是结点i/2;（2）如果2*in，则其左孩子是结点2*

10、i, 否则，结点i无左孩子且为叶子结点；（3）如果2*i1n，则其右孩子是结点2*i1， 否则，结点i无右孩子。,思考题:,5,31,16,31,1. 树最适合用来表示( ) A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 2. 根据定义，树的叶子结点其度数（） A. 必大于0 B. 必等于0 C.必等于1 D.必等于2 3. 对一棵有100个结点的完全二叉树按层序编号，则编号为49的结 点，它的左孩子的编号为（ ） A. 99 B. 98 C. 97 D. 50 4. 树形结构中，若结点有3个兄弟，是的双亲，则的度为 _。 5. 深度为15的

11、满二叉树上，第11层有 个结点。6. 三个结点可构成 种不同形态的二叉树。,想一想,C,B,B,4,210=1024,5,它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，可用编号的方法。二叉树的顺序存储结构即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中编号为i的结点存储在数组中下标为i的分量中。 该方法称为“以编号为地址”策略,4.3.1 二叉树的顺序存储结构,4.3 二叉树的存储结构,对于完全二叉树来说，采用以编号作为数组的下边的方法将结点存入一位数组中，也就是将编号为i的结点存

12、入一维数组的以i为下标的数组元素中。对于非完全二叉树，则用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。,1 2 3 4 5 6 7 8 9 10 11 12,1,2,3,4,5,6,7,8,9,10,11,12,0,Btree：,1 2 3 4 5 6 7 8 9 10 11 12,此方法用于完全二叉树，则： 节省内存 结点位置确定方便,A,B,C,D,E,F,G, 表示该处没有元素存在,用于一般二叉树：（浪费空间）,用于单分支二叉树则存储空间浪费极大。,1 2 3 4 5 6 7 8 9 10 11,1,2,3,4,5,6,7,8,9,10,11,从树根起，自上层至下层，每层自左

13、至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树却需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！,二叉树的顺序存储结构的缺点,结点形式：,左孩指针指向其左孩结点；,右孩指针指向其右孩结点；,二叉链表类型定义typedef struct btnode Datatype data; struct btnode *lchild,*rchild; *Bintree;二叉链表类型,4.3.2 二叉树的链式存储结构,二叉链表表示法：,例：,三叉链表表示法：,结点形式：,指向双亲,注：在含n个结点的二叉链

14、表中有2n个指针域，其中n-1个用来指向结点的左右孩子，其余n+1个空链域.,一、遍历含义 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题。遍历二叉树是指按一定规律对二叉树中的每个结点访问且仅访问一次即访遍树中每一结点（只一次），打印或处理结点。 遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律（或次序），能把二叉树上的各结点都访问一次且只访问一次。二、遍历规则,b,c,(根结点D),(右子树R),(左子树L),由二叉树的递归定义知，二叉树的三个基本组成单元是：根结点、左子树和右子树。,a,4.4

15、二叉树的遍历,令：L 遍历左子树 D 访问根结点 R 遍历右子树,组合,LDR、LRD、DLR、RDL、RLD、DRL,先左 后右,DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。,1、先序遍历DLR 首先访问根结点，其次遍历根的左子树，最后遍历根右子树，对每棵子树同样按这三步（先根、后左、再右）进行。,2、中序遍历LDR 首先遍历根的左子树，其次访问根结点，最后遍历根右子树，对每棵子树同样按这三步（先左、后根、再右）进行。,3、后序遍历LRD 首先遍历根的左子树，其次遍历根的右子树，最后访问根结点，对每棵子树同样按这三步（先左、后右、最后根）进行。,三、遍历算法1、先序

16、遍历（递归算法）： 步骤：若二叉树为空，则退出； 否则: （1）访问根结点； （2）先序遍历根的左子树； （3）先序遍历根的右子树。 算法：,void preorder ( BinTree bt ) /*先序遍历根指针为bt的二叉树*/ if (bt!=NULL) visit ( bt ) ; /*访问根结点*/ preorder ( bt-lchild ) ； preorder ( bt-rchild ) ; /*先序遍历以右子树*/ ；,2、中序遍历运算（递归算法） 步骤：若二叉树为空，则退出； 否则: （1）中序遍历根的左子树； （2）访问根结点； （3）中序遍历根的右子树。 算法：,v

17、oid inorder ( BinTree bt) /*中序遍历以bt为根的二叉树*/ if (bt!=NULL) inorder ( bt-lchild ) ； /*中序遍历以bt的左孩子为根的左子树*/ visit ( bt ) ; /*访问根结点*/ inorder (bt-rchild ) ; /*.*/ ,3、后序遍历运算（递归算法） 步骤：若二叉树为空，则退出； 否则: （1）后序遍历根的左子树； （2）后序遍历根的右子树。 （3）访问根结点； 算法：,void postorder (BinTree bt) /*后序遍历以bt为根的二叉树*/ if (bt!=NULL) posto

18、rder ( bt-lchild ) ； /*后序遍历以bt的左孩子为根的左子树*/ postorder ( bt-rchild ) ； visit ( bt-data ) ; /*访问根结点*/ ,对于如下图的二叉树，其先序、中序、后序遍历的序列为：,A、B、D、F、G、C、E、H 。 B、F、D、G、A、C、E、H 。F、G、D、B、H、E、C、A 。,先序遍历：中序遍历：后序遍历：,以中序遍历为例来说明中序遍历二叉树的递归过程,A,B,D,C,E,第一次经过,第二次经过,第三次经过,分析P104 例4-1 例4-2,二叉树的层次遍历：从二叉树的根结点的这一层开始，逐层向下遍历，在每一层上

19、按从左到右的顺序对结点逐个访问。,四、二叉树的层次遍历,右图按照层次遍历，所得到的的结点序列为：ABCDEFGH,设立一个队列Q，用于存放结点，以保证二叉树结点按照层次顺序从左往右进入队列。若二叉树bt非空：将根结点插入队列；从队列中删除一个结点，访问该结点，并将该结点的孩子（若有的话）插入队列。若此时队列非空，再从队列中删除一个结点，访问该结点，并将它的孩子结点插入队列。依次重复进行，直到队列为空。,Void levelorder(BinTree bt) LkQue Q; InitQueue( while (!EmptyQueue(Q),p=Gethead( ,五、遍历二叉树的应用,P110

20、 例4-3,一、双亲表示法 以一组连续空间存储树的结点，即一个一维数组构成，数组每个分量包含两个域：数据域和双亲域。数据域用于存储树上一个结点的数据元素值，双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。,4.5 树和森林,例：,双亲表示,每个数组元素含两个成员，即：（结点值和其双亲在表中的位置）,注：找父结点容易，找结点的孩子麻烦，需遍历整张表。,4.5.1 树的存储结构（三种）,根结点没有双亲，双亲域的值为-1。双亲链表的类型定义如下：,#define size=10； /定义结点数typedef struct datatype data; /数据域 int parent; /双亲

21、域 Node;Node slistsize; /用数组实现双亲表,二、孩子链表表示法,树中每个结点的孩子串成一单链表孩子链表,n个结点n个孩子链表,n个头指针用顺序表存储表头数组：数组元素存储结点本身的信息和该结点的孩子链表的头指针。,孩子链表的结点为:,存放孩子结点在表头数组中的序号,指向下一个孩子结点,孩子链表表示法的类型定义：,# define MAXND 20； /树中结点的最大个数typedef struct bnode /表结点类型 int child; struct bnode *next; /表结点指针域 node,*childlink;Typedef struct /头结点类

22、型 DataType data; /结点数据元素 childlink hp; /头结点指针域headnode;Headnode linkMAXND；,注:在孩子链表表示中，找孩子方便，但 求结点的双亲困难，因此可在顺序表中再增加一个域，用于指明每个结点的双亲在表中位置，即将双亲表示法和孩子链表表示法结合起来。,双亲孩子表示法,树中每个结点的孩子串成一单链表孩子链表,n个结点n个孩子链表,同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子链表的头指针之外，还增设一个域，用来存储结点双亲结点在数组中的序号。,parent hp,# define MAXND 20typ

23、edef struct bnodeint child; struct bnode *next;node,*childlink;Typedef struct DataType data; int parent; childlink hp;headnode;Headnode ；linkMAXND；,三、孩子兄弟链表表示法（二叉链表表示）,结点形式：,指向结点的第一个孩子结点,指向该结点的下一个兄弟结点,例：,孩子兄弟链表表示法类型定义：,Typedef struct tnode DataType data; struct tnode *son,*brother;*Tree;,4.5.2 树、森林与

24、二叉树的转换,例：,方法：, 各兄弟之间加连线； 对任一结点，除最左孩子外，抹掉该结点与其余孩子的各枝； 以根为轴心，将连线顺时针转450。,例：,完全一样,一棵树唯一对应一棵二叉树,二叉树,2、森林,森林F转换成二叉树的方法如下：,（1）将每棵树转换成相应的二叉树；（2）将（1）中得到的各棵二叉树的根结点看做是兄弟连接起来。,A,B,C,D,树T1,E,F,树T2,G,H,J,I,树T3,A,B,C,D,E,F,G,H,J,I,G,H,J,I,A,B,C,D,E,F,森林F对应的二叉树,例：,方法：, 从根结点起； 该结点左孩和左孩右枝上的结点依次 作为该结点孩子； 重复 。,根无右孩的二叉

25、树可以转变成一般树。,4.5.3 树和森林的遍历,先序遍历：先访问根结点，然后依次先序 遍历根的每棵子树；,后序遍历：先依次后序遍历每棵子树，最 后访问根结点。,先序遍历次序：？后序遍历次序：？层次遍历次序：？,注：,层次遍历：,ABCDE,BDCEA,ABCED,一、树的遍历,二、森林的遍历,先序遍历森林：访问森林中第一棵树的根结点；先序遍历森林中第一棵树的根结点的子树组成的森林；先序遍历除去第一棵树之外其余的树组成的森林。 对下图中森林进行先序遍历的序列为：ABCDEFGHJI中序遍历森林：中序访问森林中第一棵树的根结点的子树组成的森林；访问第一棵树的根结点；中序遍历除去第一棵树之外其余的

26、树组成的森林； 对下图中森林进行先序遍历的序列为：BCDAFEJHIG,A,B,C,D,E,F,G,H,J,I,问题：n个学生成绩 a1，a2，,an （百分制），现 要转换成五分制。 即 a1，a2，,an 分五类： 一类： 60 不及格 二类： 60， 70 ） 及格 三类： 70， 80 ） 中等 四类： 80， 90 ） 良好 五类： 90 优秀每类出现的概率： 分数 059 6069 7079 8089 90以上 概率 5% 15% 40% 30% 10%,4.6 判定树和哈夫曼树,4.6.1 分类与判定树,若按顺序判，得下列判断过程：,对n个数分类花费时间较多。因为大多数元素属于中

27、和良，这样大多数数据都得通过3至4次判断，这样总的判断次数就多。,改进,判定树用于描述分类过程的二叉树，其中：每个非终端结点包含一个条件，对应一次比较；每个终端结点包含一个种类标记，对应于一种分类结果。,5,10,15,30,40,总的判断次数最少。因为属于中、良的数最多，而检验它们的判断少，因此总的判断次数少。,哈夫曼树,a,4.6.2 哈夫曼树与哈夫曼算法,一、路径长度,叶结点带权的二叉树：,结点ni的带权路径长度： 为结点ni到树根的路径长度(ni的祖先的个数li)结点ni所带的权（pi）,a的路径长度=？,27=14,叶结点带权的二叉树路径长度WPL：,d的路径长度=？ WPL=？,n

28、 WPL=(pklk)， k=1,其中：n叶子数 pk第k个叶子的权 lk从根结点到nk之间的结点数,8,36,例：二叉树有4个叶子，权分别为7，5，2，4,WPL=36,WPL=?,WPL=?,(35),(46),结论：带权路径长最小的二叉树,权大的叶子离根近 权小的叶子离根远,哈夫曼树（最优二叉树）,二、哈夫曼树,其特征是,F=T1，T2，,Tn T1，T2，,Tn 权从小到大排列, 取F中T1和T2(权最小的二棵)生成一棵二叉树T， T为根， T1、T2分别为T的左、右子树， T的权=T1的权+T2的权； T插入到F的余下森林中（按序）；,方法：,三、哈夫曼算法,构造,给定n个权值 p1

29、，p2，, pn n个叶子带的权,森林F=T1，T2，,Tn Ti只有一个带权pi 的根结点，左、右子树为空,排序,重复、，直至F=T为一棵二叉树。,此二叉树T即为哈夫曼树,森林F= ,p= 7，5，2，4 ,例：,森林F= ,不减序列,第一步：,插入F,第二步：,插入F,第三步：,插入F,哈夫曼树,初始森林共有n棵二叉树，每棵树中都仅有一个孤立的结点，要进行n-1次合并才能得到哈夫曼树，每次合并产生一个新结点。最终有2n-1个结点。,采用顺序存储，设置大小为2n-1的数组，每个数组元素由4个域组成：存储权值、双亲指针、左孩子指针和右孩子指针。类型定义如下：,const int n=10;ty

30、pedef struct float w; /w为结点的权值 int parent, lchild,rchild; /指针域 node; typedef node hftree2*n-1；,哈夫曼算法：,1.将表示哈夫曼树的数组T中的2n-1结点初始化；2.读入n个权值到数组T的前n个分量中，它们是初始森林中的n个孤立的根结点的权值；3.对森林中的树进行n-1次合并，共产生n-1个新结点，依次放入数组T的第i个分量重(n=i2*n-1)。每次合并的步骤如下：,从当前森林的所有结点Tj(0=j=i-1)中选取具有最小权值和次小权值的两个根结点，分别用x和y记住这两个根结点在数组T中的下标。将根为

31、Tx和Ty的两棵树合并，使它们分别成为新结点Ti的左右孩子，得到一棵以新结点Ti为根的二叉树。同时修改Tx和Ty的双亲域parent，使其指向新结点Ti,将Tx和Ty的权值相加后作为新结点Ti的权值。类C语言描述的算法见P122。,四、哈夫曼编码 每个字符在电文中出现的次数为wi，其编 码长为mi，电文有n种字符，则电文总长=? 什么是哈夫曼编码？如何设计？ 求哈夫曼编码的算法。 分二步：1）以n个字符的权值，构造哈夫曼树； 2）求n个字符的哈夫曼编码。,n (wimi) i=1, 哈夫曼编码,可利用哈夫曼树构造用于通信的二进制编码称为哈夫曼编码。,树中从根到每个叶子都有一条路径，对路径上的各

32、分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。, 哈夫曼编码的应用,例电文：“CASTTATASA”。其中：C出现1次，A出现4次，S出现2次，T出现3次，出现3次。,哈夫曼编码：C：100 A：11 S：101 T：00 ：01,了解树的定义及基本术语；掌握二叉树的定义、性质及满二叉树、完全二叉树的定义；熟练掌握二叉树的二叉链表表示；熟练掌握二叉树的三种遍历（先序、中序、后序）过程和算法，并能运用遍历算法实现二叉树的其它一些操作；熟悉树的各种存储表示及特点，熟练掌握树与二叉树的转换方法；熟练掌握建立哈夫曼树的方法；理解由二叉树先序序列、中序序列及后序序列和中序序列可唯一的确定一棵二叉树的道理，掌握由此建立二叉树的方法。重点：二叉树遍历过程及算法、哈夫曼树的构造。,第四章树和二叉树小结,