一、存储结构

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

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

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

二、双亲表示法

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

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 指针域来解决。参考《大话数据结构》 #以书之名#