《数据结构第六章(1)ppt课件》由会员分享,可在线阅读,更多相关《数据结构第六章(1)ppt课件(118页珍藏版)》请在金锄头文库上搜索。
1、本章主要内容: 1二叉树的定义、性质和存储结构。 2二叉树的遍历和线索化以及遍历算法的各种描述形式。 3树和森林的定义、存储结构与二叉树的转换、遍历。 4树的应用。 本章学习重点: 1掌握二叉树的存储结构及其各种操作。 2掌握树和森林与二叉树的转换关系。,第六章 树和二叉树,第六章 树和二叉树,6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,第六章 树和二叉树,树型结构是结点之间有分支的、层次的关系的结构,用它们能很好地描述有分支和层次特性的数据集合。它类似于自然界中的树。树型结构是一种非常重要的非线性结构。树型结构在现实
2、世界中广泛存在,如各种社会组织机构的组织关系图就可用树型结构来表示。在计算机领域中有着广泛应用,如在编译系统中,用树表示源程序的语法结构(称为语法树);在数据库系统中,树型结构是数据库层次模型的基础,也是各种索引和目录的主要组织形式;在许多算法中,常用树型结构描述问题的求解过程或表示求解的对策等。,6.1 树的定义和基本术语,一、树的定义 二、树的表示方法 三、基本术语 四、抽象数据类型树的定义,一、树的定义,6.1树的定义和基本术语,1定义树(Tree)是n(n0)个结点的有穷集合T。 在T中: (1)有且仅有一个称为根的结点T0,T0没有前驱; (2)当n1时,其余结点可分为m(m0)个互
3、不相交的有 限集T1,T2,Tm,其中每一个Ti(1im)本身都 是一棵树。称树T1,T2,Tm为T0的子树。 (3)n=0,T是一棵空树。,一、树的定义,图1 树的一般形式,返回,6.1树的定义和基本术语,一、树的定义,2. 特点 (1)树的定义是一个递归定义。由图1(b)看出,A是由三个子树构成的,这三棵子树又分别以B,C,D为根,在以B为根的子树中,又由两棵子树构成,根分别为E,F;C,D以此类推。 (2)树的根结点没有前驱结点,其他结点有且仅有一个前驱结点; (3)树中的任何一个结点,可以有零个或多个后继结点。,6.1树的定义和基本术语,3.树型结构的例子 (1)家族的血缘关系,一、树
4、的定义,6.1树的定义和基本术语,(2)计算机磁盘目录,一、树的定义,6.1树的定义和基本术语,1图形表示法:以图1中的树为例。,二、树的表示方法,6.1树的定义和基本术语,2.形式化表示 对于一个T的形式化表示为:T=(D,R) D为T中结点的集合;R为T中结点之间关系的集合。 仍以图1为例。 D=A,B,C,D,E,F,G,H,I,J,K,L,M R=,二、树的表示方法,6.1树的定义和基本术语,1结点:包含一个数据元素及若干指向其子树的分支。 图1所示的树有13个结点。 2结点的度(degree):结点拥有的子树数。A结点的度为3。 3叶子或终端结点(leaf):度为0的结点。K,L,F
5、,G,M,I,J皆为叶子。 4分支结点或非终端结点:度不为0的结点。 5树的度:树内各结点的度的最大值。图1所示的树的度为3。 6双亲结点(parent):结点的前驱结点。A是B,C,D的双亲。,三、基本术语,见图1,6.1树的定义和基本术语,三、基本术语,7. 孩子结点(child):结点的后继结点。B,C,D是A的孩子。 8. 兄弟结点(sibling):同一双亲的孩子。B,C,D是兄弟。 9. 祖先:从根到某结点所经分支上的所有结点,皆为该结 点的祖先。G的祖先是A,C;K的祖先是A,B,E。 10. 子孙:以某结点为根的子树中的任一结点都为该结点的子孙。E,F,K,L皆为B的子孙。 1
6、1结点的层次(level):从根开始定义起,根为第1层,根的孩子为第2层。若某结点在第L层,则其子树的根在L+1层。 12堂兄弟:其双亲在同一层的结点互为堂兄弟。G,与E,F,H,I,J互为堂兄弟。,见图1,6.1树的定义和基本术语,13树的深度(depth)或高度:树中结点的最大层次。图1所示树的深度为4。 14有序树和无序树:树中结点的各子树从左至右排列,不可对换,称这种树为有序树,且把各子树分别称为第一子树,第二子树,最左边的子树为第一孩子,最右边子树为最后一个孩子。否则称为无序树。 15森林(forest):是m(m0)棵互不相交树的集合。对树中每个结点而言,其子树的集合即为森林。如图
7、1,若删除A,就得到三棵子树构成的森林。可以用森林和树相互递归的定义来描述树。树的逻辑结构采用二元组形式:T=(root,F) root:根结点,数据元素 F:m棵数的森林,F=(T1,T2,Tm)Ti=(ri,Fi)是第i棵子树树根和子树之间的关系:RF= |i=1,2,m,m0 ,三、基本术语,见图,6.1树的定义和基本术语,第1层,第3层,第2层,第4层,树的度为3 树的深度为4,返回,6.2 二叉树,一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构,一、二叉树的定义,6.2二叉树,1定义二叉树(Binary Tree)是n(n0)个结点的集合,这个集合可以是空集,或者是由一个根
8、结点和两棵称为左子树和右子树的互不相交的二叉树组成。(由此看出二叉树定义是递归的) 2特点 (1)每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点); (2)可以是空树,即不含任何结点; (3)二叉树是有序树,子树有左右之分,次序不能任意颠倒;允许某些结点只有右子树,或者只有左子树。,1抽象数据类型二叉树的定义ADT BinaryTree数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D=,则R=,称BinaryTree为空二叉树;若D,则R=H,H是如下二元关系:(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;(2)若D-root,则存在D-root=
9、Dl,Dr,且DlDr=;,一、二叉树的定义,6.2二叉树,(3)若Dl,则Dl中存在唯一的元素xl, H,且存在Dl上的关系H1H;若Dr,则Dr中存在唯一的元素xr,H,且存在Dr 上的关系HrH;H=,,Hl,Hr; (4)(Dl,Hl)是一棵符合本定义的二叉树,称为根的左子树,(Dr,Hr)是一棵符合本定义的二叉树,称为根的右子树。 基本操作P:略。 ADT BinaryTree,一、二叉树的定义,6.2二叉树,4.二叉树的五种基本形态,一、二叉树的定义,6.2二叉树,5. 特殊的二叉树 (1)满二叉树如果二叉树的最后一层都是叶子结点,且它各层的结点都包含左、右子树,则称该二叉树为满二
10、叉树。,对二叉树从第1层的根结点开始连续编号,编号顺序是自上而下、自左而右,则该编号方法给出了满二叉树的顺序表示法。,一、二叉树的定义,6.2二叉树,(2)完全二叉树如果一棵深度为k的有i(1in)个结点的二叉树,对树中的结点自上而下、自左而右连续编号,若编号为i的结点与满二叉树中编号为i的结点的位置相同,则称此二叉树为完全二叉树。,特点: a.叶子结点只可能在层数最大的两层上出现; b.对任一结点,若其右分支下的子孙的最大层次为L,则其左分支下的子孙的最大层次为L或L+1。,完全二叉树,非完全二叉树,一、二叉树的定义,6.2二叉树,性质1 在二叉树的第i(i1)层上至多有2i-1个结点。用数
11、学归纳法就可以证明。满二叉树的第i层上共有2i-1个结点。深度为k的完全二叉树,除了第k层外,其余各层也均 有2i-1个结点(1I1,则其双亲结点parent(i)是结点i/2。 (2)若2in,则结点i无左子树;若2in,则其左子树lchild(i)是结点2i。 (3)若2i+1n,则结点i无右子树;若2i+1n,则其右子树rchild(i)是结点2i+1。,6.2二叉树,二、二叉树的性质,i=1 只有根结点,i1,i=23-1=4 双亲为i/2 =2 左子树为2i=2*23-1=8 右子树为2i+1=9,i1,i+1=23-1+1=4+1 双亲为i/2 =2 左子树为2i+2=2*4+2
12、=8+2=10 右子树为2i+3=11,i=8,2in无左子树,6.2二叉树,二、二叉树的性质,1顺序存储结构略。 2.链式存储结构所谓二叉树的链接存储,是指二叉树诸结点被随机存放在内存空间中,结点之间的关系用指针说明。设计不同的结点结构可构成不同形式的链式存储结构。,三、二叉树的存储结构,6.2二叉树,(1) 二叉链表一个结点包含三个域:数据域、左、右指针域分别指向左子树和右子树。(2) 三叉链表为了便于找到双亲结点,在二叉链表的基础上,增加一个指向双亲结点的指针域,构成三叉链表。,三、二叉树的存储结构,6.2二叉树,(3) 线索链表在含有n个结点的二叉链表中有n+1个空链域。如图所示。利用
13、这些空链域存储其他有用信息,即可得到另一种链式存储结构线索链表。,三、二叉树的存储结构,6.2二叉树,3.二叉树的二叉链表存储表示: typedef struct BiTNode TelemType data;Struct BiTNode *lchild ,*rchild;BiTNode,*BiTree;,三、二叉树的存储结构,6.2二叉树,6.3 遍历二叉树和线索二叉树,一、遍历二叉树 二、线索二叉树(穿线树),所谓遍历就是按某指定规则访问数据结构中的所有结点,且每个结点只访问一次。各种数据结构包括线性表也有遍历运算。这里“访问”的含义很广,可以对结点作各种处理,如输出结点信息、求结点个数等
14、。对于线性结构,遍历的运算比较简单。而对二叉树这种非线性结构,每个结点都可能有两棵子树,需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,从而便于遍历。,一、遍历二叉树,6.3 遍历二叉树和线索二叉树,1遍历规则二叉树是由三个基本单元组成:根结点、左子树和右子树。所谓遍历规则是指在遍历时是先访问根结点还是先访问子树,是先访问左子树还是先访问右子树。不同的遍历规则会产生不同的遍历结果。 以D、L、R表示访问根结点、左子树、右子树,有6种遍历方式:DLR、LDR、LRD、DRL、RDL、RLD 一般规定,在二叉树遍历中,按先访问左子树,后访问右子树的顺序进行遍历。,一、遍历二叉树,6.3 遍历二叉树和线索二叉树,有四种遍历:先(根)序遍历(DLR) 1 2 4 8 9 5 10 11 3 6 12 7中(根)序遍历(LDR) 8 4 9 2 10 5 11 1 12 6 3 7后(根)序遍历(LRD) 8 9 4 10 11 5 2 12 6 7 3 1层次遍历:先从上到下,再从左到右的顺序遍历 1 2 3 4 5 6 7 8 9 10 11 12,