树与二叉树的存储结构

树的存储结构

双亲表示法：

除了树的根节点之外，其余每个结点不一定有孩子，但是一定有且仅有一个双亲。
假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示双亲结点在数组中的位置
结点结构如下:其中data是数据域，存储结点的数据信息。而parent是指针域，存储该节点的双亲在数组中的下标。
这样可以根据结点的parent指针很容易找到它的双亲结点，可如果需要知道孩子结点，则需要遍历整个树结构。故可以增加一个指针域指向最左边孩子。同样的，也可以增加指向右兄弟的指针域来体现兄弟关系。

双亲表示法
双亲表示法示例如下： 双亲表示法

孩子表示法：

由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。不过，树中的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案解决：
1、指针域的个数就等于树的度（树的度等于树中各个结点的度的最大值d）,其中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点（对于树中各个结点的度相差很大时，浪费空间）

第一种
2.每个结点指针域的个数等于该结点的度，专门取一个位置存储结点指针域的个数（虽然克服了浪费空间的缺点，但是时间上的消耗增大，需要维护度的数值）
第二种
综上，有了孩子表示法，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放金一个一维数组中。
为此，设计两种结点结构，一个是孩子链表的孩子结点，如图所示,其中child为数据域，用于存储某个结点在表头数组中的下标。next为指针域，用于存储指向某结点的下一个孩子结点的指针。
孩子结点
另一个是表头数组的表头结点，其中data为数据域，存储某个结点的数据信息，firstchild是头指针域，存储该结点的孩子链表的头指针。
表头结点
但是这也存在着问题，需要通过遍历查找某个结点的双亲，故改进上述表头数组的表头结点，再附加一个指向双亲结点的指针域,把这种方法称为双亲孩子表示法。
双亲孩子表示法

孩子兄弟表示法：

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。其中data是数据域，firstchild为指针域，存储该结点的第一个孩子结点的地址，rightsib是指针域，存储该结点的右兄弟结点的地址。

孩子兄弟表示法
这个方法的最大好处是可将一棵复杂的树变成一棵二叉树，可以充分利用二叉树的特性和算法处理这棵树。

二叉树的存储结构

二叉树的顺序存储结构：

用一维数组存储二叉树的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子之间的关系

二叉树的顺序存储结构
可以看出，完全二叉树可以用顺序结构表现出来，当然对于一般的二叉树，尽管层序编号不能反应逻辑关系，但是可以将其按完全二叉树编号，只不过，将不存在的结点设置为空而已。
但是，下面这种极端情况下，一棵深度为k的斜树，只有k的结点，却需要分配2k-1个存储单元空间，非常浪费空间
斜树的顺序存储

二叉树的链式存储结构

二叉树每个结点最多有两个孩子，所有为它设计一个数据域和两个指针域的结点，称这样的链表为二叉链表。其中data为数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。（如果需要，还可以增加一个指向其双亲的指针域，那样就称之为三叉链表）

二叉树链式存储结构