二叉树存储可以用顺序存储（转化为完全二叉树用数组存，结点孩子和双亲下标能互相快速定位），也可以用链表来存（主要为二叉链表，结点存有左右孩子指针）。

那么树能怎么存储呢？

双亲表示法

借鉴二叉树的顺序存储思路，用数组存储每个结点，不过此处双亲和孩子下标不再有相互关系，因此需要给结点增加数据成员 parent，记录双亲结点在数组的下标（根结点的parent = -1），如图：

此时 结点数据成员有 data + parent

// 结点成员有 data, parent
typedef struct
{
    /* data */
    ElemType data;  // 结点内容
    int parent;     // 双亲在数组的下标
}PTNode;

静态存储

#define MaxTreeNodes 100
typedef struct
{
    /* data */
    PTNode nodes[MaxTreeNodes];
    int n;     // 记录结点数
    int r;     // 记录根结点下标 (可有可无)
}PTree;

动态存储

// 动态存储
typedef struct
{
    /* data */
    PTNode *nodes;  // 初始化时动态分配空间
    int n;
    int r;
}PTree;

阿Q：该方法适用于频繁找双亲的场景（结点p找孩子 需要遍历数组，若当前结点的parent为p下标，则当前结点为p的孩子，找孩子比较麻烦）。

---

孩子表示法

怎样能将结点p的孩子串起来呢？ p -> child1 -> child2 -> … ，用单链表即可。

然后再用数组将全部结点存储进去（数组存结点，结点链孩子），如图：

孩子数据成员有：index（该结点在数组的位置）+ next

结点数据成员有：data + next

// 孩子结点
typedef struct CNode
{
    /* data */
    int index;  // 结点在数组的位置
    struct CNode *next;
}CNode;

// 结点
typedef struct
{
    /* data */
    ElemType data;
    CNode *next;
}CTNode;

静态存储

// 整棵树
typedef struct
{
    /* data */
    CTNode nodes[MaxTreeNodes];
    int n;      // 记录结点数
    int r;      // 记录根结点的下标
}CTree;

动态存储

//动态存储
typedef struct
{
    /* data */
    CTNode *nodes;  // 初始化时动态分配空间
    int n;
    int r;
}CTree;

阿Q：该方法适用于频繁找孩子的场景（结点p找双亲，需要遍历数组，若当前结点的next，next->next一直到null中都没找到结点p，那么次结点不为p的双亲，否则该结点即为p的双亲，找双亲麻烦）。

---

双亲 + 孩子 表示法

双亲和孩子表示法各有缺点，将两者融合起来就互补短处了，如图：

那么只需要修改孩子表示法中 结点 结构，数组只需修改结构名即可

此时结点数据成员有 parent + data + next

// 孩子结点
typedef struct CNode
{
    /* data */
    int index;  // 结点在数组的位置
    struct CNode *next;
}CNode;

// 结点 （增加parent数据成员）
typedef struct
{
    /* data */
    int parent;  // 增加部分
    ElemType data;
    CNode *next;
}CPTNode;

// 整棵树（以静态存储为例）
typedef struct
{
    /* data */
    CPTNode nodes[MaxTreeNodes];
    int n;
    int r;
}CPTree;

阿Q：找孩子和找双亲都很方便（用空间换时间，阿Q比较推荐）

---

孩子兄弟表示法

在二叉树中，二叉链表的指针分别指向左右孩子。

但是在树结构中，如果链表全指向孩子，二叉链表肯定是不行的了。

但换个思路，如果将二叉链表的左指针指向第一个孩子，右指针指向兄弟，那就可行了啊（因此孩子兄弟表示法又称为二叉树表示法），如图：

阿Q：指针指向能改变整个结构（思维不能僵化）。

结点数据成员： firstchild + data + nextsibling

// 二叉树表示法
// 结点
typedef struct CSNode
{
    /* data */
    ElemType data;
    
    // 指向第一个孩子 
    struct CSNode *firstchild;

    // 指向兄弟
    struct CSNode *nextsibling;

}CSNode, *CSTree;

阿Q：方便实现转化为二叉树的操作，容易找结点的孩子（结点p的孩子，结点p的左指针指向第一个孩子，沿着右支走到 null，期间的所有结点均为p的孩子）。

二叉树和树的转换 即 通过此方式进行的，详情看树、森林、二叉树的转换

---

双亲 + 孩子兄弟表示法

和二叉树的二叉链表存储一样，用三叉链表实现，结点增加数据成员 指针parent 即可。

// 三叉链表示法
// 结点
typedef struct CSPNode
{
    /*data*/
    ElemType data;

    struct CSPNode *firstchild, *nextsibling;

    // 增加parent指针
    struct CSPNode *parent;

}CSPNode, *CSPTree;