《数据结构第六章(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,
