数据结构之浅谈树

树的相关概念定义

树的定义

它是由n（n>=1）个有限节点组成一个具有层次关系的集合。每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；

树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；
叶节点或终端节点：度为0的节点称为叶节点；
非终端节点或分支节点：度不为0的节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
树的度：一棵树中，最大的节点的度称为树的度；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：双亲在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；
有序树：数中个结点的子树从左至右是有序不能互换的，则称为有序数
无序数: 反之就是无序树

树的存储结构

顺序存储结构是用一段地址连续的存储单元依次将线性表中的数据元素存入。对于一对一的当然可以，但对于树这种一对多的结构就有困难，无论我们采取何种排序方式将树种的节点存入到数组中，结点的存储位置都很难直接反应映射逻辑关系，因为数据元素挨个存储，谁是谁的子节点，谁是谁的双亲？
我们可以充分利用顺序存储与链式存储的特点来实现树的存储结构，有三种表示方法：双亲表示法，孩子表示法，孩子兄弟表示法。
如：该树状结构的存储结构表示法

1.双亲表示法

由于树的定义可知，一个节点可以没有子节点，但有且只有一个双亲。所以我们可以从这一特性考虑，我们可以利用一段连续空间存储树的结点，只要我们知道该节点的双亲就可以找到他。
我们就可以为树的结点添加一个双亲域 来存放双亲结点指针。
树的结点可以设计成：

如将上述树状结构利用双亲表示法来实现，先将树的结点存入数组中，parent记录该结点的双亲在数组中的下标，没有就用-1表示。

下标	data	parent
0	a	-1
1	b	0
2	c	0
3	d	1
4	e	1
5	f	2
6	h	5

此实现让我们可以很快找到结点双亲，但是要找到结点的孩子结点那就要遍历整个结构，比较麻烦。我们又想是否可以再树结点的结构上再添加一个孩子域(长子域，该结点的第一个孩子)呢？

树状结构的实现：

下标	data	parent	firstchild
0	a	-1	1
1	b	0	3
2	c	0	5
3	d	1	-1
4	e	1	-1
5	f	2	6
6	h	5	-1

这样的结构就可以很快的解决 结点有0 1孩子的情况。
这样实现我们就可以很快得到一个查找双亲与孩子结点都很快的存储。但是我们又想很快的查找结点的兄弟结点，这个设计又得修改，所以根据不同的关注点，就要不同结构设计，这过程很灵活。

2.孩子表示法

每个结点可能有多棵子树，我们可以考虑用多重链表，树的每个结点有多个指针域，每个指针域指向一个子树的根结点，我们把这种方法称为多重链表表示法
树结点设计

上述树结构(度为2，没有孩子的 为空)多重链表的实现方式

由图中可推测，开辟了很多没有使用的空间，会造成空间的浪费。
我们想是否可以通过添加一个域来表示该结点的度 degree

上述树状结构的实现

有没有一种既能避免空间浪费又能保证树每个的结点结构是一致的能呢？
这就是孩子表示法(把每个结点的孩子结点排列起来，以单链表来作为存储结构，n个结点就有n个孩子链表，叶子结点的孩子链表为空，然后n 个头指针又组成一个线性表，采用顺序存储结构，存入数组中)
这种表示方式涉及到两种结点：一孩子链表中的孩子结点，头指针中的头结点
孩子结点: data数据域，next指向下一个孩子的指针。

头结点：data数据域，firstchild 指向第一个孩子的指针

上述树状结构的孩子表示

该设计还是有个问题 ，如果要找某个结点的双亲的话还是比较麻烦的，我们可以在头结点添加一个双亲域 parent

上述树状结构的双亲孩子表示(是孩子表示法的一种改进)实现

3.孩子兄弟表示法

任意的一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，我们设置两个指针，分别指向该结点的第一个孩子结点和此结点的右兄弟

上述树状结构的孩子兄弟表示法

这种实现，我们要查找某个结点的某个孩子，我们可以通过先查找该结点firstchild 然后通过firstchild的右兄弟rightsib来查找。
但是要查找某个结点双亲 就比较困难，所以我 们可以按照上述的方式给结点添加一个parent域。
仔细观察该实现方式有点像二叉树。

通过上述树的几种表示方式，我们可以发现，树的存储设计师非常灵活的。我可以通过侧重不同操作的效率如（查找）来设计不同的存储结构。