数据结构的树存储结构(上)：https://developer.aliyun.com/article/1471366
二叉树的链式存储结构（C语言详解）
本节我们学习二叉树的链式存储结构。
图 1 普通二叉树示意图
如图 1 所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，图 1 对应的链式存储结构如图 2 所示：
图 2 二叉树链式存储结构示意图
由图 2 可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：
- 指向左孩子节点的指针（Lchild）；
- 节点存储的数据（data）；
- 指向右孩子节点的指针（Rchild）；
图 3 二叉树节点结构
表示该节点结构的 C 语言代码为：
图 2 中的链式存储结构对应的 C 语言代码为：
#include <stdio.h> #include <stdlib.h> #define TElemType int typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->data=3; (*T)->rchild->lchild=NULL; (*T)->rchild->rchild=NULL; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->lchild->data=4; (*T)->lchild->rchild=NULL; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL; } int main() { BiTree Tree; CreateBiTree(&Tree); printf("%d",Tree->lchild->lchild->data); return 0; }
程序输出结果：
4
其实，二叉树的链式存储结构远不止图 2 所示的这一种。例如，在某些实际场景中，可能会做 "查找某节点的父节点" 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如图 4 所示：
图 4 自定义二叉树的链式存储结构
这样的链表结构，通常称为三叉链表。
利用图 4 所示的三叉链表，我们可以很轻松地找到各节点的父节点。因此，在解决实际问题时，用合适的链表结构存储二叉树，可以起到事半功倍的效果。
树的双亲表示法
普通树结构的数据。
图 1 普通树存储结构
如图 1 所示，这是一棵普通的树，该如何存储呢？通常，存储具有普通树结构数据的方法有 3 种：
- 双亲表示法；
- 孩子表示法；
- 孩子兄弟表示法；
本节先来学习双亲表示法。
双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。
注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。
例如，采用双亲表示法存储图 1 中普通树，其存储状态如图 2 所示：
图 2 双亲表示法存储普通树示意图
树的孩子表示法
孩子表示法存储普通树采用的是 "顺序表+链表" 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。
如果节点没有孩子节点（叶子节点），则该节点的链表为空链表。
例如，使用孩子表示法存储图 1a) 中的普通树，则最终存储状态如图 1b) 所示：
图 1 孩子表示法存储普通树示意图
图 1 所示转化为 C 语言代码为：
#include<stdio.h> #include<stdlib.h> #define MAX_SIZE 20 #define TElemType char //孩子表示法 typedef struct CTNode { int child;//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标 struct CTNode * next; }ChildPtr; typedef struct { TElemType data;//结点的数据类型 ChildPtr* firstchild;//孩子链表的头指针 }CTBox; typedef struct { CTBox nodes[MAX_SIZE];//存储结点的数组 int n, r;//结点数量和树根的位置 }CTree; //孩子表示法存储普通树 CTree initTree(CTree tree) { printf("输入节点数量：\n"); scanf("%d", &(tree.n)); for (int i = 0; i < tree.n; i++) { printf("输入第 %d 个节点的值：\n", i + 1); getchar(); scanf("%c", &(tree.nodes[i].data)); tree.nodes[i].firstchild = (ChildPtr*)malloc(sizeof(ChildPtr)); tree.nodes[i].firstchild->next = NULL; printf("输入节点 %c 的孩子节点数量：\n", tree.nodes[i].data); int Num; scanf("%d", &Num); if (Num != 0) { ChildPtr * p = tree.nodes[i].firstchild; for (int j = 0; j < Num; j++) { ChildPtr * newEle = (ChildPtr*)malloc(sizeof(ChildPtr)); newEle->next = NULL; printf("输入第 %d 个孩子节点在顺序表中的位置", j + 1); scanf("%d", &(newEle->child)); p->next = newEle; p = p->next; } } } return tree; } void findKids(CTree tree, char a) { int hasKids = 0; for (int i = 0; i < tree.n; i++) { if (tree.nodes[i].data == a) { ChildPtr * p = tree.nodes[i].firstchild->next; while (p) { hasKids = 1; printf("%c ", tree.nodes[p->child].data); p = p->next; } break; } } if (hasKids == 0) { printf("此节点为叶子节点"); } } int main() { CTree tree; for (int i = 0; i < MAX_SIZE; i++) { tree.nodes[i].firstchild = NULL; } tree = initTree(tree); //默认数根节点位于数组notes[0]处 tree.r = 0; printf("找出节点 F 的所有孩子节点："); findKids(tree, 'F'); return 0; }
程序运行结果为：
输入节点数量： 10 输入第 1 个节点的值： R 输入节点 R 的孩子节点数量： 3 输入第 1 个孩子节点在顺序表中的位置1 输入第 2 个孩子节点在顺序表中的位置2 输入第 3 个孩子节点在顺序表中的位置3 输入第 2 个节点的值： A 输入节点 A 的孩子节点数量： 2 输入第 1 个孩子节点在顺序表中的位置4 输入第 2 个孩子节点在顺序表中的位置5 输入第 3 个节点的值： B 输入节点 B 的孩子节点数量： 0 输入第 4 个节点的值： C 输入节点 C 的孩子节点数量： 1 输入第 1 个孩子节点在顺序表中的位置6 输入第 5 个节点的值： D 输入节点 D 的孩子节点数量： 0 输入第 6 个节点的值： E 输入节点 E 的孩子节点数量： 0 输入第 7 个节点的值： F 输入节点 F 的孩子节点数量： 3 输入第 1 个孩子节点在顺序表中的位置7 输入第 2 个孩子节点在顺序表中的位置8 输入第 3 个孩子节点在顺序表中的位置9 输入第 8 个节点的值： G 输入节点 G 的孩子节点数量： 0 输入第 9 个节点的值： H 输入节点 H 的孩子节点数量： 0 输入第 10 个节点的值： K 输入节点 K 的孩子节点数量： 0 找出节点 F 的所有孩子节点：G H K
使用孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点。
其实，我们还可以将双亲表示法和孩子表示法合二为一，那么图 1a) 中普通树的存储效果如图 2所示：
图 2 双亲孩子表示法
使用图 2 结构存储普通树，既能快速找到指定节点的父节点，又能快速找到指定节点的孩子节点。该结构的实现方法很简单，只需整合这两节的代码即可，因此不再赘述。
树的孩子兄弟表示法
一种常用方法——孩子兄弟表示法。
图 1 普通树示意图
树结构中，位于同一层的节点之间互为兄弟节点。例如，图 1 的普通树中，节点 A、B 和 C 互为兄弟节点，而节点 D、E 和 F 也互为兄弟节点。
孩子兄弟表示法，采用的是链式存储结构，其存储树的实现思想是：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。
因此，该链表中的节点应包含以下 3 部分内容（如图 2 所示）：
- 节点的值；
- 指向孩子节点的指针；
- 指向兄弟节点的指针；
图 2 节点结构示意图
用 C 语言代码表示节点结构为：
#define ElemType char typedef struct CSNode{ ElemType data; struct CSNode * firstchild,*nextsibling; }CSNode,*CSTree;
以图 1 为例，使用孩子兄弟表示法进行存储的结果如图 3 所示:
图 3 孩子兄弟表示法示意图
由图 3 可以看到，节点 R 无兄弟节点，其孩子节点是 A；节点 A 的兄弟节点分别是 B 和 C，其孩子节点为 D，依次类推。
实现图 3 中的 C 语言实现代码也很简单，根据图中链表的结构即可轻松完成链表的创建和使用，因此不再给出具体代码。
接下来观察图 1 和图 3。图 1 为原普通树，图 3 是由图 1 经过孩子兄弟表示法转化而来的一棵树，确切地说，图 3 是一棵二叉树。因此可以得出这样一个结论，即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，换句话说，任意一棵普通树都有唯一的一棵二叉树于其对应。
因此，孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为"二叉树表示法"或"二叉链表表示法"。
