数据结构7-8-9树

《数据结构7-8-9树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructure彭宏京南京工业大学计算机科学系2007年9月学时数：48(32+16）学分：3教材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月（配题集）参考书：[1]殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月。￥26[2]殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。￥26[3]李春葆，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。￥28[4]丁宝康等，数据结构自学考试指导，清华大学出版社

2、，2001年5月。￥23内容安排章内容学时章内容学时1绪论27图62线性表48动态存储管理略3栈和队列69查找44串（自学）210内部排序45数组和广义表（自学）411外部排序略6树和二叉树612文件略实验：课内上机（16规定内容）+课外上机（24平时作业中编程题验证）数据结构课程的内容各种数据结构的应用1、树的定义和基本术语2、二叉树3、遍历二叉树和线索二叉树4、树和森林5、树和等价问题6、赫夫曼树及其与树的应用7、回溯法与树的遍历8、树的计数目录第六章树和二叉树特点：非线性结构，一个直接

3、前驱，但可能有多个直接后继。（一对多或1:n）1、树的定义和基本术语（1）.树的定义注：树的定义具有递归性，即“树中还有树”。由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。（1）.树的定义（2）.若干术语（3）.逻辑结构（4）.存储结构（5）.树的运算树的表示法主要有5种：图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子－右兄弟表示法1、

4、树的定义和基本术语自学图形表示法：教师学生其他人员2004级2005级2006级2007级……南工大信息学院计算机系电子系通信系……叶子根子树左孩子－右兄弟表示法ABCDEFGHIJKLM数据左孩子右兄弟（2）.若干术语——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即以某结点为根的子树中的任一结点ABCGEIDHFJMLK根叶子森林有序树无序树——

5、即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。（2）.若干术语（续）——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJMLK——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）—

6、—指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝1334（有几个直接后继就是几度，亦称“次数”）ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点M的祖先是A、D、H（3）.树的逻辑结构一对多（1:n），有多个直接后

7、继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。（4）.树的存储结构讨论1：树是非线性结构，该怎样存储？特点：——仍然有顺序存储、链式存储等方式。理论上，你爱怎样存储就怎样存储（比如随手扔进存储器，就像有些不爱收拾的同学对待自己的物品一样）！！但如果这样的话，你要取出来就很要命了（相信大家均有过找东西的烦恼）。学数据结构就是让你/计算机变得更有秩序和高效！原则是：物理存储要反映逻辑结构（逻辑关系必须在存储实现时得到反映）!!注：这两种存储方式对于线性结构来说很直观也很自然。那么

8、，这两种存储方式如何反映1:n的树型关系呢？（想一想？）二叉树讨论3：树的链式存储方案应该怎样制定？复原困难讨论2：树的顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：解决思路：不能唯一复