本文共 3069 字，大约阅读时间需要 10 分钟。
树的定义（数据结构）
前言
这次我们学习树和二叉树，树是一种一对多的非线性结构
一.树导学
1.知识点线索
（概述）
第1章 数据结构、ADT、算法（基础）
（线性结构） 第2章 线性表 第3章 栈和队列 第4章 字符串 第5章 数组与广义表 （非线性结构） 第6章 树和二叉树 第7章 图（应用）
第9章 查找 第10章 内部排序 第11章 外部排序2.知识点搜素
树这一章依然是看他的两种存储结构，以及在这两种结构上所进行的操作，从而再讨论算法，但是我们要重点掌握对树来说十分重要操作——遍历.
3.主要内容
树这里需要掌握的内容有很多
4.树的应用
树的应用是普遍存在的，比如图谱树状图分支图，还有比较常见的在计算机中的文件管理器，像是一颗倒着的树。树的特点很明显是一对多：一个点对应着多个分支。
二.树的定义
（在这里我们讨论的树是一颗倒着的树）
1.树的定义
树：T={D,R}
（1）树的形式化定义用T来定义，主要包括D和R两部分，D是数据，R是关系。D中的数据我们把它叫做结点，（树中的结点就是他的数据）R是指结点和结点之间一对多的关系。通过这些结点和他们之间的关系来描绘出一颗树。
D={A,B,C,D,E,F,G,H,I,J,K,L,M}
R={r} ① r={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<G,J>,<I,K>,<I,L>,<I,M>}
（2）D是包含n个节点的有穷集合（n≥0）
当n=0时为空树 当n>0时，关系R满足以下一对多条件：① 有且仅有一个节点d0∈D没有前驱节点，节点d0称作树的根节点
② 除节点d0外，D中的每个节点有且仅有一个前驱节点 ③ D中每个节点可以有零个或多个后继节点 （有0个节点我们把它叫做叶子，除了叶子以外其他节点都有多个后继）（3）总结：
树（Tree）是n（n≥0）个结点的有限集，或为空树（n = 0），或为非空树（n>0）。对于非空树T：
① 有且仅有一个称之为根的结点； ②除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm, 称为根的子树（SubTree）。
在上棵树建立的过程我们可以看出来，A结点为根节点，他还包括T1，T2，T3这三棵子树，这实际上体现了递归的思想，一棵树的建立是由结点构成的多个子树构成的。
2.树的表示法
（1）树形表示法：又叫做直观表示法。
树的表示法有多种，最常用的最普通的就是这种直观表示法，也就是用圆圈代表着每个结点，结点和结点之间用线相连表示结点之间的关系。
（3）凹入表示法：又叫目录表示法。
把一棵树看成了一篇文章一本书，这本书又分成了不同的章，每章又分为不同的节，然后依次凹入进去
（4）括号表示法：又叫做广义表表示法。
括号外A是根，括号括起来的是用逗号来隔开的三棵子树，而每棵子树又有他的根，然后括号括起来了。
3.树的基本术语
➢ 根：根结点(没有前驱) ： （A）
➢ 叶子：即终端结点(没有后继) ： （ KLFGHIJ） ➢ 森林：指m棵不相交的树的集合(例如删除A后的子树个数 BCD三棵子树) ➢ 有序树：结点各子树从左至右有序，不能互换（左为第一棵子树） ➢ 无序树：结点各子树可互换位置。➢ 结点：即树的数据元素（一般用圆圈表示，元素一般写到圆圈里面）
➢ 结点的度：结点挂接的子树数（比如A的度为3，C的度为1） ➢ 结点的层次：从根到该结点的层数（根结点算第一层） ➢ 终端结点：即度为0的结点，即叶子 ➢ 分支结点：即度不为0的结点（也称为内部结点，非叶子） ➢ 树的度：所有结点度中的最大值（这棵树中A和D的度最大，均为3，所以这棵树的度为3） ➢ 树的深度(或高度)：指所有结点中最大的层数（也就是从根节点开始数几层，你会发现树状结构实际上是一种层次结构）（有趣的术语，很像生活中我们的称呼）
➢ 双亲：即上层的那个结点(直接前驱) （比如B结点的双亲就是A） ➢ 孩子：即下层结点的子树的根(直接后继) （孩子就是双亲反过来，比如A的孩子是BCD） ➢ 兄弟：同一双亲下的同层结点（孩子之间互称兄弟）（比如BCD互为兄弟） ➢ 堂兄弟：即双亲位于同一层的结点（但并非同一双亲）（比如FG互为堂兄弟） ➢ 祖先：即从根到该结点所经分支的所有结点 ➢ 子孙：即该结点下层子树中的任一结点4.树的ADT（抽象数据类型）
ADT Tree
{ 数据对象： D = {ai | ai∈ElemType, i=1,2,…,n, n≧0 } //ElemType为类型标识符数据关系：
R = {<ai,aj> | ai, aj∈D, i=1,2,…,n, j=1,2,…,n，其中每个元素只有一个前驱节点，可以有零个或多个后继节点，有且仅有一个元素（根节点）没有前驱节点 }数据操作：
（1）初始化树InitTree(&t)：构造一个空的树t （2）销毁树DestroyTree(&t)：释放树t占用的内存空间 （3）求双亲节点Parent(t)：求t所指节点的双亲结点 （4）求子孙节点Sons(t)：求t所指节点的子孙节点 … … }树的运算主要分为三大类：
第一类，寻找满足某种特定关系的节点，如寻找双亲节点。 第二类，插入或删除某个节点，如在树的当前节点上插入一个新节点或删除当前节点的第i个孩子节点等。 第三类，遍历树中每个节点。5.树的遍历
（2） 树有三种遍历方式
① 先根遍历：若树不空，则先访问根节点，然后依次 先根遍历（都是先从左开始）各棵子树。 ABEFCGJDHIKLM②后根遍历：若树不空，则先依次后根遍历各棵子树，
然后访问根节点。 EFBJGCHKLMIDA③ 层次遍历：若树不空，则自上而下自左至右访问树
中每个节点。 ABCDEFGHIJKLM（我们通常把先根遍历和后根遍历称为树的深度优先遍历，而层次遍历称为广度优先遍历）
6.讨论——树的结构
树的逻辑结构：
（1）讨论1：树的逻辑结构（特点） ①一对多（1:n）； ②有多个直接后继，但只有一个根结点; ③子树之间互不相交。树的存储结构：
（1）讨论1：树是非线性结构，该怎样存储？ 仍然有顺序存储、链式存储方式。（2）讨论2：树的顺序存储方案应该怎样制定？
①可规定为：从上至下、从左至右将树的结点依次存入内存； ②重大缺陷：复原困难（不能唯一复原的话就没有实用价值）。（3）讨论3：树的链式存储方案应该怎样制定？
①可用多重链表：一个前趋指针，n个后继指针。 ②细节问题：树中结点的样式该如何设计？ “等长”？“不等长”？ ③缺点： 等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。后续
从树的存储结构我们可以看出，无论是顺序存储还是链式存储，树的存储都很复杂，所以我们想到一种解决方法: 解决思路：先研究最简单、最有规律的树——二叉树，然后把一般的树转化为简单树。
发表评论
最新留言
关于作者
