如下图所示，这是一棵普通的树，该如何存储呢？通常，存储具有普通树结构数据的方法有 3 种：
双亲表示法；
孩子表示法；
孩子兄弟表示法；
图1
树的双亲表示法
双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。
注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。
图2
双亲表示法存储普通树代码
/*
* @Description: 树的双亲表示法
* @Version: V1.0
* @Autor: Carlos
* @Date: 2020-05-21 14:41:32
* @LastEditors: Carlos
* @LastEditTime: 2020-06-01 22:12:34
*/
#include<stdio.h>
#include<stdlib.h>
//宏定义树中结点的最大数量
#define MAX_SIZE 20
//宏定义树结构中数据类型
typedef char ElemType;
//结点结构
typedef struct Snode
{
//树中结点的数据类型
ElemType data;
//结点的父结点在数组中的位置下标
int parent;
}PNode;
//树结构
typedef struct
{
//存放树中所有结点
PNode tnode[MAX_SIZE];
//结点个数
int n;
}PTree;
/**
* @Description: 节点初始化
* @Param: PTree tree 结构体变量
* @Return: PTree 结构体地址
* @Author: Carlos
*/
PTree InitPNode(PTree tree)
{
int i,j;
char ch;
printf("请输入节点个数:\n");
scanf("%d",&(tree.n));
printf("请输入结点的值其双亲位于数组中的位置下标:\n");
for(i=0; i<tree.n; i++)
{
fflush(stdin);
scanf("%c %d",&ch,&j);
tree.tnode[i].data = ch;
tree.tnode[i].parent = j;
}
return tree;
}
/**
* @Description: 查找树中指定节点
* @Param: PTree tree 结构体变量
* @Return: 无
* @Author: Carlos
*/
void FindParent(PTree tree)
{
char a;
int isfind = 0;
printf("请输入要查询的结点值:\n");
fflush(stdin);
scanf("%c",&a);
for(int i =0;i<tree.n;i++){
if(tree.tnode[i].data == a){
isfind=1;
//找到父节点的下标数值
int ad=tree.tnode[i].parent;
printf("%c的父节点为 %c,存储位置下标为 %d",a,tree.tnode[ad].data,ad);
break;
}
}
if(isfind == 0){
printf("树中无此节点");
}
}
int main()
{
PTree tree;
tree = InitPNode(tree);
FindParent(tree);
return 0;
}
树的孩子表示法
孩子表示法存储普通树采用的是 "顺序表+链表" 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。
如果节点没有孩子节点（叶子节点），则该节点的链表为空链表。
例如，使用孩子表示法存储左图中的普通树，则最终存储状态如右图所示：
图3
/*
* @Description: 树的孩子表示法。三部分构成，链表，节点，树
* @Version:
* @Autor: Carlos
* @Date: 2020-05-21 14:59:47
* @LastEditors: Carlos
* @LastEditTime: 2020-06-01 22:47:38
*/
#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;
/**
* @Description: 孩子表示法存储普通树
* @Param: CTree tree 树的结构体变量
* @Return: CTree tree 结构体变量
* @Author: Carlos
*/
CTree InitTree(CTree tree){
printf("输入节点数量：\n");
scanf("%d",&(tree.n));
for(int i=0;i<tree.n;i++){
printf("输入第 %d 个节点的值：\n",i+1);
fflush(stdin);
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;
}
/**
* @Description:查找节点
* @Param: CTree tree 树的结构体，char a 要查找的节点
* @Return: 无
* @Author: Carlos
*/
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;
//打印所有孩子节点 p->child 孩子节点在数组中的位置
printf("%c ",tree.nodes[p->child].data);
p=p->next;
}
break;
}
}
if(hasKids==0){
printf("此节点为叶子节点");
}
}
int main()
{
CTree tree;
tree = InitTree(tree);
//默认数根节点位于数组notes[0]处
tree.r=0;
printf("找出节点 F 的所有孩子节点：");
FindKids(tree,'F');
return 0;
}
树的孩子兄弟表示法
树结构中，位于同一层的节点之间互为兄弟节点。例如，图1中的普通树中，节点 A、B 和 C 互为兄弟节点，而节点 D、E 和 F 也互为兄弟节点。
孩子兄弟表示法，采用的是链式存储结构，其存储树的实现思想是：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。
因此，该链表中的节点应包含以下 3 部分内容：
节点的值；
指向孩子节点的指针；
指向兄弟节点的指针；
图4
用 C 语言代码表示节点结构为：
#define ElemType char
typedef struct CSNode{
ElemType data;
struct CSNode * firstchild,*nextsibling;
}CSNode,*CSTree;
以图1为例，使用孩子兄弟表示法进行存储的结果如下图所示:
图5
由图5可以看到，节点 R 无兄弟节点，其孩子节点是 A；节点 A 的兄弟节点分别是 B 和 C，其孩子节点为 D，依次类推。
实现上图中的 C 语言实现代码也很简单，根据图中链表的结构即可轻松完成链表的创建和使用，因此不再给出具体代码。
接下来观察图 1 和图 5。图 1 为原普通树，图5 是由图 1 经过孩子兄弟表示法转化而来的一棵树，确切地说，图5是一棵二叉树。因此可以得出这样一个结论，即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，换句话说，任意一棵普通树都有唯一的一棵二叉树于其对应。
因此，孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为"二叉树表示法"或"二叉链表表示法"。
原文链接：https://www.f2er.com/datastructure/995702.html有任何问题，均可通过公告中的二维码联系我
