作者：解学武

前面用大量的篇幅讲解了二叉树，从本节开始带领大家研究普通的树存储结构。


如图 1 所示，这是一棵普通的树，该如何存储呢？通常，存储具有普通树结构数据的方法有 3 种：

1. 双亲表示法；
2. 孩子表示法；
3. 孩子兄弟表示法；

本节先来学习双亲表示法。

双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。

注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。

例如，采用双亲表示法存储图 1 中普通树，其存储状态如图 2 所示：
图 2 存储普通树的过程转化为 C 语言代码为：

#define MAX_SIZE 20 //树中结点的最大数量
typedef char ElemType; //数据的类型
typedef struct Snode   //结点结构
{
    ElemType data;
    int parent;
}PNode;
typedef struct  //树结构
{
    PNode tnode[MAX_SIZE];
    int r, n;   //树根的位置下标和结点数
}PTree;

以图 1 中的树结构为例，采用双亲表示法存储它的 C 语言实现代码为：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 20 //树中结点的最大数量
typedef char ElemType; //数据的类型
typedef struct Snode   //结点结构
{
    ElemType data;
    int parent;
}PNode;

typedef struct  //树结构
{
    PNode tnode[MAX_SIZE];
    int r, n;   //树根的位置下标和结点数
}PTree;

void 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);
        if (j == -1) {
            (*tree).r = i;
        }
        (*tree).tnode[i].data = ch;
        (*tree).tnode[i].parent = j;
    }
}
//找某个结点的父结点
void FindParent(PTree tree)
{
    char a;
    int isfind = 0, i, ad;
    printf("请输入孩子结点的值:\n");
    scanf("%*[^\n]"); scanf("%*c");//清空输入缓冲区
    scanf("%c", &a);
    for (i = 0; i < tree.n; i++) {
        if (tree.tnode[i].data == a) {
            isfind = 1;
            ad = tree.tnode[i].parent;
            printf("%c 的父节点为 %c,存储位置下标为 %d\n", a, tree.tnode[ad].data, ad);
            break;
        }
    }
    if (isfind == 0) {
        printf("树中无此节点\n");
    }
}
//找某个结点的孩子结点
void FindChilds(PTree tree)
{
    char a;
    int i, j;
    int isfind = 0;
    printf("请输入要父亲结点的值:\n");
    scanf("%*[^\n]"); scanf("%*c");//清空输入缓冲区
    scanf("%c", &a);
    for (i = 0; i < tree.n; i++) {
        if (tree.tnode[i].data == a) {
            for (j = 0; j < tree.n; j++) {
                if (tree.tnode[j].parent == i) {
                    isfind = 1;
                    printf("%c 是 %c 的孩子\n", tree.tnode[j].data, a);
                }
            }
            if (isfind == 0) {
                printf("%c没有孩子结点\n", a);
            }
        }
    }
}

int main()
{
    PTree tree;
    memset(&tree, 0, sizeof(PTree));
    InitPNode(&tree);
    FindParent(tree);
    FindChilds(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
请输入要父亲结点的值:
F
G 是 F 的孩子
H 是 F 的孩子
K 是 F 的孩子

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。