C语言数据结构树的双亲表示法实例详解

什么是双亲表示法

在树上，每个节点都有且仅有一个父节点（根节点除外）。对于一个树结构，我们可以使用许多方法来表示这个树，其中最常见的一种方法是双亲表示法。该表示法使用一个一维数组来存储树的节点，数组的下标即为该节点的编号，数组的值则表示该节点的父节点编号。 当一个节点没有父节点时，该节点即为根节点。

双亲表示法的优缺点

双亲表示法的优点是在查找根节点、父节点、子节点等基本操作时非常高效。但是，在查找其他不在其子树内的节点时，效率会降低。 此外，如果树的深度很大，数组中可能会出现许多空白的节点。 这时，考虑到空间效率，我们可以考虑其他表示法。

双亲表示法的代码实现

在双亲表示法中，我们可以使用一个结构体来表示节点。

typedef struct node{
    int val;//节点的权值
    int parent;//节点的父节点编号
}Node;

然后，我们可以使用一个一维数组来表示整颗树：

#define maxn 1000 //最大节点数
Node nodes[maxn];//节点数组
int root;//根节点编号
int n;//树的节点数

在节点数组中，第i个节点的父节点编号存储在nodes[i].parent中。当节点i为根节点时，它的父节点编号就被设置为-1或0等特殊值。

示例说明一

我们来看一个简单的例子，假设有如下一棵树：

      0
    / | \
   1  2  3
 /   |   |  \
4    5   6   7

对于这颗树，我们可以使用如下代码来存储：

Node nodes[] = {
    {0, -1},
    {1, 0},
    {2, 0},
    {3, 0},
    {4, 1},
    {5, 2},
    {6, 3},
    {7, 3},
};
root = 0;
n = 8;

示例说明二

现在，我们来看一个稍微复杂一些的例子，假设有如下一棵树：

          0
       /   |   \
      1    2    3
     /     |     \
    4      5      6
         / | \   /  \
        7  8  9  10 11

对于这颗树，我们可以使用如下代码来存储：

Node nodes[] = {
    {0, -1},
    {1, 0},
    {2, 0},
    {3, 0},
    {4, 1},
    {5, 2},
    {6, 3},
    {7, 5},
    {8, 5},
    {9, 5},
    {10, 6},
    {11, 6},
};
root = 0;
n = 12;

总结

双亲表示法是一种简单又高效的树结构表示法，在实际应用中也有着广泛的应用。我们需要根据实际情况选择符合场景的树表示方法，以达到高效使用的目的。