5.6.1 树的存储结构（不是二叉树）

双亲表示法

以一组连续的存储单元存储树的结点，每个结点除了数据域 data 之外，还附加一个 parent 域用来指向其双亲结点的位置。
找双亲容易，找孩子难。

实现

定义结构数组存放树的结点，每个结点包含两个域：

数据域：存放结点本身的信息。
双亲域：指示本结点的双亲结点在数组中的位置。

例如

根节点 R 没有双亲，所以双亲域存放-1。
ABC 的双亲域里存着的都是0，表示他们共同的双亲都是在数组下标0出的数据 R，以此类推。

类型定义

typedef struct PTNode
{TElemType data;//存放的结点当中的数据，元素类型取决于要存储的结点的元素类型。int parent;//存放结点双亲的所在位置的下标}PTNode;

定义树结构数组

#define MAX_TREE_SIZE 100
typedef struct
{PTNode nodes[MAX_TREE_SIZE];//有100个PTNode类型的数组int r;//表示根结点的下标的位置int n;//记录总共存储了多少结点}PTree;

孩子表示法

由于树中每个结点都可能有多棵子树，则可以使用多重链表，即每个结点由多个指针域，其中每个指针域指向一棵子树的根节点。
把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则 n 个结点有 n 个孩子链表（叶子的孩子链表为空表）。而 n 个头指针又组成一个线性表，用顺序表（含 n 个元素的结构数组）存储。
找孩子容易，找双亲难

举个栗子

如上图所示：

根节点 R 的孩子是 ABC，那么就把它的孩子看成是一个线性表。
将 ABC 用一个单链表穿起来。数据域用来存放数据元素，指针域则存放后继结点的地址。

在这里插入图片描述

其他结点的孩子则以此类推依次用单链表串起来。
用数组来存储每个单链表的头指针。

根节点 R 在下标为 r = 4 的位置，总共有 n = 10 个结点

结构定义

孩子结点结构

在这里插入图片描述

typedef struct CTNode
{int child;struct CTNode *next;}*ChildPtr;

双亲结点结构

在这里插入图片描述

typedef struct
{TElemType data;ChildPtr firstchild;//孩子链表的头指针，这个指针指向的类型是有两个成员所构成的孩子结点结构。}CTBox;

树结构

typedef struct
{CTBox nodes[MAX_TREE_SIZE];//用来存放所有指向孩子链表的头指针int r;//表示根节点所在数组位置的下标int n;//表示该树有多少个结点}CTree;

双亲孩子法

由前面两种表示法知道，要么不好找孩子，要么不好找双亲，这个时候就需要一种既能找爸爸又能找孩子的表示法。
可以将双亲法与孩子表结合起来，变成孩子双亲法，在结构数组中再增加一个成员用来存储每个结点的双亲结点的下标。
这种结构就称为带双亲的孩子链表。

孩子兄弟法

又称为二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。
链表中结点的两个链域分别指向该结点的第一个孩子以及下一个兄弟结点（左孩右兄）。
找孩子兄弟容易，找双亲困难

结构定义

//树的二叉链表（孩子-兄弟）存储表示
typedef struct CSNode
{ElemType data;//data存储的元素是什么类型它就是什么类型struct CSNode* firstchild ;//指向结点的第一个孩子struct CSNode* nextsibling;//指向节点的下一个兄弟}CSNode,*CSTree;

举个栗子