数据结构第07次课-树A.ppt

《数据结构第07次课-树A.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、每课一贴：一个人去买鹦鹉，看到一只鹦鹉前标：此鹦鹉会两门语言，售价二百元。另一只鹦鹉前则标有：此鹦鹉会四门语言，售价四百元。该买哪只呢？两只都毛色光鲜，非常灵活可爱。这人转啊转，拿不定主意。结果突然发现一只老掉了牙的鹦鹉，毛色暗淡散乱，标价八百元。这人赶紧将老板叫来：这只鹦鹉是不是会说八门语言？店主说：不。这人奇怪了：那为什么又老又丑，又没有能力，会值这个数呢？店主回答：因为另外两只鹦鹉叫这只鹦鹉老板。这故事告诉我们，真正的领导人，不一定自己能力有多强，只要懂信任，懂放权，懂珍惜，就能团结比自己更强的力量，从而提升自己的身价

2、。相反许多能力非常强的人却因为过于完美主义，事必躬亲，什么人都不如自己，最后只能做最好的攻关人员，销售代表，成不了优秀的领导人。1数据结构课程的内容2第6章树和二叉树（Tree&BinaryTree）6.1树的基本知识6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1:n）36.1树的基本知识1.树的定义2.若干术语3.逻辑结构4.存储结构5.树的运算41.树的定义注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义

3、已修改。注2：树的定义具有递归性，即树中还有树。由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。52.若干术语——即上层的那个结点(直接前驱)parent——即下层结点的子树(直接后继)child——同一双亲下的同层结点（孩子之间互称兄弟）sibling——即双亲位于同一层的结点（但并非同一双亲）cousin——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结

4、点ABCGEIDHFJMLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。62.若干术语（续）——即树的数据元素——结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJMLK——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——除树根以外的结点（也称

5、为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝13347树的表示法有几种：图形表示法嵌套集合表示法广义表表示法目录表示法左孩子－右兄弟表示法树的抽象数据类型定义参见教材P118-1198图形表示法：教师学生其他人员99级2000级2001级2002级……三峡大学电气学院计算机系电子系自控系……叶子根子树9广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))根作为由子树森林组成的表的名字写在表

6、的左边ABCGEIDHFJMLK10左孩子－右兄弟表示法ABCDEFGHIJKLM数据左孩子右兄弟ABCGEIDHFJMLK11树的抽象数据类型定义ADTTree{数据对象D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明D是具有相同特性的数据元素的集合。//至少有15个123.树的逻辑结构(特点)：一对多（1:n），有多个直接后继（

7、如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。4.树的存储结构讨论1：树是非线性结构，该怎样存储？————仍然有顺序存储、链式存储等方式。13讨论3：树的链式存储方案应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论2：树的顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义

8、好多种结构类型）。14解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树。二叉树讨论4：计算机如何实现各种不同进制的运算？实现思路：先研究最简单、最有规律的二进制运算规律，然后设法把各种不同进制的运算转化二进制运算。讨论5：树的存储可否借鉴这种思路呢？155.树的运