数据结构之树的存储结构

一、顺序存储结构

顺序存储结构通常用于表示完全二叉树。在这种存储方式中，树中的节点被存储在一个连续的数组中。对于完全二叉树，如果父节点的索引是i（假设从0开始计数），那么它的左子节点的索引是2i+1，右子节点的索引是2i+2。数组的第一个元素存储树的根节点。

优点：
节省空间，特别是对于完全二叉树。
简单，易于实现。

缺点：
不适用于非完全二叉树，会导致空间浪费。
插入和删除操作比较复杂，需要移动大量的节点。

二、链式存储结构

链式存储结构是树最自然的存储方式。在这种存储方式中，每个节点包含一个数据域和一个或多个指针域，指针域指向其子节点。通常使用结构体（在C/C++中）或类（在Java、C#等面向对象的语言中）来实现。

优点：
适用于各种类型的树。
插入和删除操作相对简单，只需修改指针即可。

缺点：
相比顺序存储结构，空间开销更大，因为需要额外的指针域。

三、特殊存储方法

1、双亲表示法

双亲表示法通过采用一维数组来存储树中的节点，其中每个节点被赋予一个结构体类型，包含数据域和父节点位置域（parent域）。这种方法可以方便地找到每个节点的父节点和祖先节点，但查找子节点和兄弟节点较为困难。

2、孩子链表表示法

孩子链表表示法将树中所有节点存储在一个顺序表中，每个数据元素有两个域：数据域和存放该节点第一个孩子地址的指针域。同时，为树中每个节点构建一个单链表，链表中的节点也有两个域：存放该孩子节点在顺序表中的数组下标和指向下一个孩子的指针。这种方法可以方便地找到节点的所有孩子，但查找父节点需要遍历整个数组。

3、孩子兄弟表示法

孩子兄弟表示法采用二叉链表来存储树中的节点，每个节点包含三个域：数据域和两个指针域（child和brother）。child指针指向该节点的第一个孩子节点，brother指针指向该节点的下一个兄弟节点。这种方法将树转化为二叉树的形式，便于利用二叉树的算法进行操作。但需要注意的是，从当前节点查找其父节点较为麻烦，可能需要为每个节点增设一个parent域。