Java数据结构-树及树的存储结构

淡淡的烟草味﹌ 2022-08-02 13:55 291阅读 0赞

树的定义：n（n>=0）个节点的有限集。

1.  n=0时称为空树。
2.  n!=0时为非空树，有且仅有一个特定的节点——根；n>1时，其它节点可以分为m（m>0）个互不相交的有限集T1~Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

**树的一些基本术语：**

1.  树的结点：由一个数据元素和若干个指向其子树的分支组成。
2.  结点的度：结点所拥有的子树的个数（即分支数）称为该结点的度。
3.  叶子结点：度为0的结点称为叶子结点，或者称为终端结点。
4.  分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点由叶子结点和分支结点组成。
5.  孩子、双亲、兄弟：树中一个结点的子树的根结点称为这个结点的孩子；这个结点称为它孩子结点的双亲；具有同一个双亲的孩子结点互称为兄弟。
6.  路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（i为1~k，不等于k的值），就把n1,n2,…,nk称为一条由n1至nk的路径。路径长度是指路径上经过的边的数量，所以这条路径的长度是k-1。
7.  祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
8.  结点的层数：规定树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。
9.  树的深度（高度）：树中所有结点中的最大层数称为树的深度。
10. 树的度：树中各结点中度的最大值称为该树的度。
11. 有序树、无序树：如果一棵树中结点的各子树从左到右都是有次序的，不能交换的，称这棵树为有序树；反之为无序树。
12. 森林：ｍ（ｍ＞＝０）棵互不相交的树的集合。
13. 同构：对于两棵树，若通过对各结点适当重命名，就可以使这两棵树完全相等（结点对应相等，结点关系也相等），称这两棵树同构。
14. 层序编号：将书中结点按照从上层到下层、同层从左到右的次序依次给它们编号１开始的自然数。

**线性结构和树结构的比较：**  
![1.jpg][]

**树的存储结构：**  
**双亲表示法：**  
（用一组连续空间来存储树的结点）  
在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。  
结点的结构如下：  
![2.png][]

下面演示一下双亲表示法：约定根结点的指针域设为-1；  
![3.jpg][]

这个方法通过结点只要花O(1)的时间就可以访问到此结点双亲结点，但是要找到其孩子结点却需要遍历整棵树。需要改进；  
改进版一：增加最左孩子（长子）结点指针域；如下：  
![4.jpg][]

改进版二：增加右兄弟结点指针域；如下：  
![5.jpg][]  
可以根据需求来进行改进，灵活的设计存储结构。

多重链表表示法：  
（用多重链表来实现）  
每个结点有多个指针，其中每个指针指向一棵子树的根结点，这种方法叫多重链表表示法。  
方案一：  
指针域的个数等于树的度；结构如下：  
![6.png][]  
举例上图的树的度为3，所以指针域的个数为3，方法的实现如下：  
![7.jpg][]  
解释：对于树中各结点的度相差很大时，是很浪费空间的；如果各结点的度相差很小时，空间是被充分利用的。  
根据按需分配空间的想法，于是我们有了第二组方案。  
方案二：  
每个结点指针域的个数等于该结点的度，通过设置一个位置来存储结点指针域的个数；结构如下：  
![8.png][]  
于是乎上述图可以画出该方案的实现：  
![9.jpg][]  
解释：该方法客服了空间上的浪费，但是由于链表的结构不同以及需要维护结点的度的数值，因此在运算上就是在时间上有所消耗。

**孩子表示法：**  
利用数组来存放数组的结点，利用单链表来存放结点的孩子结点。  
演示上述图例结构如下：  
![10.jpg][]

解释：  
表头数组的的结构；data是数据域，存储结点的数据信息；firstchild是头指针，存储该结点的孩子链表的头指针。  
孩子链表的结构：child是数据域，存储某个结点在表头数组中的下标；next是指针域，用来存储指向某结点的下一个孩子结点的指针。

改进版：孩子双亲表示法：  
在表头数组中增加一个parent域，用来保存指向双亲结点的指针。

**孩子兄弟表示法：**  
结构如下：  
![11.jpg][]  
解释：data是数据域；firstchild为指针域，存储该结点的长子的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储地址。  
这样上述图中所述树的实现如下：  
![12.jpg][]  
如果想找到双亲，可以增加一个双亲指针。

后续继续讲解二叉树。

[1.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树1.jpg
[2.png]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树2.png
[3.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树3.jpg
[4.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树4.jpg
[5.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树5.jpg
[6.png]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树6.png
[7.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树7.jpg
[8.png]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树8.png
[9.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树9.jpg
[10.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树10.jpg
[11.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树11.jpg
[12.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/树12.jpg