Skip to content
第4章

4.4 树的存储结构的实现 ​

双亲表示法 ​

上一节把三种存法的思路、要走几步都讲完了。这一节把它们写成C语言,代码就是把那些步骤一句一句翻译过来。双亲表示法和孩子表示法,只写最能看出好坏的那几个操作;孩子兄弟表示法,把4.2节的八个操作全部写出来。

双亲表示法是一张表。结点在表里第几行,就用这个行号代表它:

c
#define MAXSIZE 100

typedef struct {
    char data;       /* 结点的值 */
    int parent;      /* 双亲在第几行,根是-1 */
} PNode;

typedef struct {
    PNode nodes[MAXSIZE];
    int n;           /* 一共几个结点 */
} PTree;

找双亲,就是读这一行的parent:

c
int Parent(PTree *T, int p) {
    return T->nodes[p].parent;
}

找第一个孩子,就是上一节那样从第0行往下扫,找parent等于p的行:

c
int FirstChild(PTree *T, int p) {
    int i;
    for (i = 0; i < T->n; i++)          /* 把整张表扫一遍 */
        if (T->nodes[i].parent == p) return i;
    return -1;                          /* 没有孩子 */
}

上一节数出来的O(n),在代码里就是这个for循环。Parent没有循环,是O(1)。

两个函数收的、返回的都是行号。上一节说的"换回字母",在代码里就是读data:行号是i的结点,名字是T->nodes[i].data。

选中正文里的任意文字,就可以针对它发表评论