不做作业
前面讲了二叉树的顺序存储和链式存储，本节来学习如何存储具有普通树结构的数据。
图 1 普通树存储结构
如图 1 所示，这是一棵普通的树，该如何存储呢？通常，存储具有普通树结构数据的方法有 3 种：
双亲表示法；
孩子表示法；
孩子兄弟表示法；
本节先来学习双亲表示法。
双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。
注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。
例如，采用双亲表示法存储图 1 中普通树，其存储状态如图 2 所示：
图 2 双亲表示法存储普通树示意图
图 2 存储普通树的过程转化为 c 语言代码为：
#define max_size 100//宏定义树中结点的最大数量
typedef char elemtype;//宏定义树结构中数据类型
typedef struct snode{
telemtype data;//树中结点的数据类型
int parent;//结点的父结点在数组中的位置下标
}ptnode;
typedef struct {
ptnode tnode[max_size];//存放树中所有结点
int n;//根的位置下标和结点数
}ptree;
因此，存储图 1 中普通树的 c 语言实现代码为：
#include#include #define max_size 20 typedef char elemtype;//宏定义树结构中数据类型 typedef struct snode //结点结构 { elemtype data; int parent; }pnode; typedef struct //树结构 { pnode tnode[max_size]; int n; //结点个数 }ptree; ptree initpnode(ptree tree) { int i, j; char ch; printf("请输出节点个数:\n"); scanf("%d", &(tree.n)); printf("请输入结点的值其双亲位于数组中的位置下标:\n"); for (i = 0; i < tree.n; i ) { getchar(); scanf("%c %d", &ch, &j); tree.tnode[i].data = ch; tree.tnode[i].parent = j; } return tree; } void findparent(ptree tree) { char a; int isfind = 0; printf("请输入要查询的结点值:\n"); getchar(); 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; for (int i = 0; i < max_size; i ) { tree.tnode[i].data = " "; tree.tnode[i].parent = 0; } tree = initpnode(tree); findparent(tree); return 0; }
程序运行示例：
请输出节点个数:
10
请输入结点的值其双亲位于数组中的位置下标:
r -1
a 0
b 0
c 0
d 1
e 1
f 3
g 6
h 6
k 6
请输入要查询的结点值:
c
c的父节点为 r,存储位置下标为 0
