数据结构的四种基本存储方式（数据结构树的存储结构）

顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。存储的元素之间是一对一的关系，但是在树形结构中元素之间是一对多的关系。

树中某个结点的孩子可以有多个，则无论按何种顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。简单说就是我们单纯地按照数组存储，我们将无法知道每个元素的双亲、孩子节点是谁。所以单纯的顺序存储结构是不能满足树的实现要求的。

不过我们可以利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构的表示。我们这里要介绍三种不同的表示法：双亲表示法 、孩子表示法、孩子兄弟表示法。

树的存储结构

树形结构，除了根结点外，其余每个结点，它不一定有孩子，但是一定有且仅有一个双亲亲。我们假设以一组连续空间存储树的结点，同时在每个结点中设置一个指示器，指示其双亲结点到链表中的位置。也就是说每个节点除了知道自己是谁以外，还必须知道它的双亲是谁。

双亲表示法

Data是该节点的数据域；parent 是该节点指向双亲节点的指针域；

class Node<T>{ //数据 T data; //双亲节点的下标 int parent; } class Tree{ //数组的大小 int max_size=10; //数组容器 Node [] nodes=new Node[max_size]; //根节点的下标 int root; }

有了结构的定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有双亲的位置。

双亲表示法

这样的存储结构，我们可以根据结点的 parent 指针很容易找到他的双亲结点，所用的时间复杂度为 0(1)，直到 parent等于-1时，表示找到了树结点的根。但是我们要知道结点的孩子是谁，我们只能遍历整个数组才行。我们可以增加指向左孩子的指针域，或者增加指向右孩子的指针域。如下图双亲表示法增加左孩子节点的指针

双亲表示法增加左孩子节点

孩子表示法就是先用数组存储每个节点，然后用单链表把每个节点的子节点串联起来。会编程的小伙伴都知道 Map 的数据结构。树的孩子表示法非常类似于 Map 的数据结构。

节点的存储结果

其中Data是数据域，存储某节点的数据信息。 FirstChild是头指针域，存储该结点的孩子链表的头指针。

孩子节点的结构

child是数据域，存储某个结点在表头数组中的下标。next是指针域，用来存储某结点的下一个孩子结点的指针。

孩子表示法

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

孩子兄弟表示法

data是数据域，firstchild为指针域，存储第一个孩子结点的地址，rightsib是指针域，存储该结点的右兄弟的地址。

孩子兄弟表示法

这种方法给查找某结点的某个孩子带来了方便，只需要通过firstchild 找到此结点的左儿子，然后再通过左儿子找到二弟，一直下去，直到找到具体的孩子。当然，如果想要找到双亲，完全可以增加一个parent 指针域来解决。参考《大话数据结构》 #以书之名#