首页 > 代码库 > 《大话数据结构》笔记（6-1）--树：树
《大话数据结构》笔记（6-1）--树：树
代码实现：
https://github.com/Lyu0709/data-structure/blob/master/src/com/coding/basic/tree/Tree.java
第六章 树
树的定义
树的结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树数称为结点的度（degree）。
度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。
除根结点之外，分支结点也称为内部结点。
树的度是树内各结点的度的最大值。
结点的子树的根称为该节点的孩子（Child），相应的，该结点称为孩子的Parent
同一个Parent的孩子之间互称兄弟（Sibling）。
结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
结点的层次（Level）从根开始定义起。其Parent在同一层的结点互为堂兄弟。
树中结点的最大层数称为树的深度（Depth）或高度。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称改树为有序树，否则称为无序树。
森林（Forest）是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
树的抽象数据类型
树的存储结构
双亲表示法
假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。
结点结构定义代码：
约定根结点的位置域设置为-1
根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为O(1)；如果想要知道结点的孩子是什么，则需要遍历整个结构才行。
改进：
可以把此结构扩展为双亲域、长子域、右兄弟域等。
存储结构的设计是一个非常灵活的过程，一个存储结构设计的是否合理，取决于基于该存储结构的运算是否适合、是否方便、时间复杂度好不好等。
孩子表示法
每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这个方法叫做多重链表表示法。
由于树的每个结点的度不相同，所以有两种方案来解决。
方案一
指针域的个数等于树的度。
这种方法对于树中各节点的度相差很大时，显然是浪费空间的。不过如果树的各结点度相差很小时，就意味着开辟的空间被充分利用了，这时存储结构的缺点反而变成了优点。
方案二
每个结点指针域的个数等于该结点的度。
这种方法克服了浪费空间的缺点，对空间利用率是提高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。
有没有什么方法，既可以减少空指针的浪费又能使结点各结构相同？
孩子表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
为此，需要设计两种结点结构，一个是孩子链表的孩子结点
另一个是表头数组的表头结点
另一个是表头数组的表头结点孩子表示法的结构定义代码：
这里存在的问题是需要遍历整棵树才知道某个结点的双亲。
改进
双亲孩子表示法
孩子兄弟表示法
任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的有兄弟。
所有有必要知道父结点，完全可以再增加一个parent指针域来解决快速查找双亲的问题。
其实这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。
《大话数据结构》笔记（6-1）--树：树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。