外观
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。
孩子表示法
孩子表示法要两种东西:表里的结点,和链上的格子:
c
typedef struct CNode { /* 孩子链上的格子 */
int child; /* 这个孩子在第几行 */
struct CNode *next; /* 链上的下一格 */
} CNode;
typedef struct {
char data; /* 结点的值 */
CNode *first; /* 孩子链的第一格 */
} CTBox;
typedef struct {
CTBox nodes[MAXSIZE];
int n; /* 一共几个结点 */
} CTree;找第一个孩子,看链的第一格:
c
int FirstChild(CTree *T, int p) {
return T->nodes[p].first == NULL ? -1 : T->nodes[p].first->child;
}找双亲,一行一行查它们的链,谁的链上有p,谁就是双亲:
c
int Parent(CTree *T, int p) {
int i;
CNode *c;
for (i = 0; i < T->n; i++) /* 每一行 */
for (c = T->nodes[i].first; c != NULL; c = c->next) /* 查它的孩子链 */
if (c->child == p) return i;
return -1; /* 根没有双亲 */
}找下一个兄弟,就是上一节"下一个兄弟记在哪里"的三步,一步一段:
c
int NextSibling(CTree *T, int p) {
int f = Parent(T, p); /* 第一步:先找双亲,要查所有的链 */
CNode *c;
if (f == -1) return -1; /* 根没有兄弟 */
c = T->nodes[f].first;
while (c->child != p) c = c->next; /* 第二步:在双亲的链上找到p那一格 */
return c->next == NULL ? -1 : c->next->child; /* 第三步:下一格才是答案 */
}Parent里套着两层循环,NextSibling一开头就调用Parent,所以都是O(n)。
孩子兄弟表示法
孩子兄弟表示法再加一个parent。每个结点放一个值和三个指针:
c
typedef struct TNode {
char data; /* 结点的值 */
struct TNode *parent; /* 双亲 */
struct TNode *first; /* 第一个孩子 */
struct TNode *next; /* 下一个兄弟 */
} TNode, *Tree;和2.10节的Node、LinkList一样,TNode是结点类型,Tree是指向结点的指针类型。一棵树,只要记住根的地址。
下面六个操作,每个只有一行。InitTree要改根,所以和3.4节一样,参数是Tree *T;其余五个照着写,只读一个指针或一个值。上一节说孩子兄弟表示法的这些操作都是O(1),代码里也看得到,一个循环都没有:
c
void InitTree(Tree *T) { *T = NULL; }
TNode *Root(Tree *T) { return *T; }
char Value(Tree *T, TNode *p) { return p->data; }
TNode *Parent(Tree *T, TNode *p) { return p->parent; }
TNode *FirstChild(Tree *T, TNode *p) { return p->first; }
TNode *NextSibling(Tree *T, TNode *p) { return p->next; }Value、Parent这几个函数其实用不上T。留着它,是因为换成双亲表示法时就要用T去扫表。调用的写法不变,换存法时调用者不用改。
InsertChild:加一个孩子
B已经有一个孩子F。现在InsertChild(T, B, 'E')。
第一步:申请结点q,放E。q的双亲是B;它刚建好,没有孩子,first是NULL:
c
TNode *q = (TNode *)malloc(sizeof(TNode));
q->data = x;
q->first = NULL;
q->parent = p;第二步:q指向原来的第一个孩子:
c
q->next = p->first;第三步:p的第一个孩子改成q:
c
p->first = q;先连上,再改first,顺序不能反。先改first,F的地址就丢了,F再也找不回来。这和2.12节在第0个位置插入,是同一件事。
往空树里放根时,p是NULL,没有孩子链可接,让T指向q就行。写成函数,返回新结点,申请不到时返回NULL:
c
TNode *InsertChild(Tree *T, TNode *p, char x) {
TNode *q = (TNode *)malloc(sizeof(TNode)); /* 第一步:申请结点,放x */
if (q == NULL) return NULL;
q->data = x;
q->first = NULL;
q->parent = p;
if (p == NULL) { /* 空树:q就是根 */
q->next = NULL;
*T = q;
} else {
q->next = p->first; /* 第二步:q指向原来的第一个孩子 */
p->first = q; /* 第三步:p的第一个孩子改成q */
}
return q;
}不用走,是O(1)。
DeleteSubtree:删除子树
删除分两件事:先把p从兄弟链上摘下来,再释放p和它的全部子孙。
第一件事:摘下来。先看删H。H不是D的第一个孩子,要让前一个兄弟G的next跳过它。前一个兄弟没有直接记着,只好从第一个孩子开始,沿着next找:
c
TNode *q = p->parent->first;
while (q->next != p) q = q->next; /* 找到前一个兄弟 */
q->next = p->next;H连同它的孩子J,一起从D的孩子里摘了下来。
如果p是第一个孩子,前面没有兄弟,要改的是双亲的first。删B就是这样,把A的first改成C:
c
p->parent->first = p->next;如果p是根,整棵树都没了,让T变成NULL。一共三种情形。
第二件事:释放。p的孩子可能还有孩子,一层一层有多深,事先不知道。可是每个孩子下面都是一棵子树,释放子树和释放整棵是同一件事。这就是3.8节的递归:
c
void FreeSubtree(TNode *p) {
TNode *c = p->first;
while (c != NULL) {
TNode *after = c->next; /* 先记下下一个兄弟 */
FreeSubtree(c); /* 释放这个孩子的子树 */
c = after;
}
free(p); /* 孩子都释放了,再释放自己 */
}规模变小:每次处理的都是一棵更小的子树。出口:没有孩子时,循环一次都不走,直接释放自己。
先记下next,再释放,顺序不能反。c释放之后,c->next读的是已经不归你的内存。先释放孩子,再释放自己,也不能反:自己先释放了,就读不到first,孩子全找不回来。
删除D时,5个结点释放的先后是这样的:
摘下来时要找前一个兄弟,最多走过双亲的所有孩子;释放要把整棵子树走一遍。合起来:
c
void DeleteSubtree(Tree *T, TNode *p) {
TNode *f = p->parent;
if (f == NULL) { /* p是根 */
*T = NULL;
} else if (f->first == p) { /* p是第一个孩子 */
f->first = p->next;
} else { /* 找到前一个兄弟 */
TNode *q = f->first;
while (q->next != p) q = q->next;
q->next = p->next;
}
FreeSubtree(p);
}把八个操作合起来
再写一个main,把上一节那棵字母树建出来。InsertChild总是放在最前面,所以每个结点的孩子要倒着加,看的时候才是图上的顺序。ShowChildren只用FirstChild和NextSibling,列出一个结点的孩子:
c
void ShowChildren(Tree *T, TNode *p) {
TNode *c;
printf("%c:", Value(T, p));
for (c = FirstChild(T, p); c != NULL; c = NextSibling(T, c))
printf("%c ", Value(T, c));
printf("\n");
}
int main(void) {
Tree T;
TNode *a, *b, *d, *h, *j;
InitTree(&T);
a = InsertChild(&T, NULL, 'A');
d = InsertChild(&T, a, 'D');
InsertChild(&T, a, 'C');
b = InsertChild(&T, a, 'B');
InsertChild(&T, b, 'F');
InsertChild(&T, b, 'E');
InsertChild(&T, d, 'I');
h = InsertChild(&T, d, 'H');
InsertChild(&T, d, 'G');
j = InsertChild(&T, h, 'J');
ShowChildren(&T, a);
ShowChildren(&T, d);
printf("J的双亲:%c\n", Value(&T, Parent(&T, j)));
DeleteSubtree(&T, h);
ShowChildren(&T, d);
DeleteSubtree(&T, d);
ShowChildren(&T, Root(&T));
return 0;
}把这些接在前面的函数后面,在开头加上#include <stdio.h>和#include <stdlib.h>,运行结果:
text
A:B C D
D:G H I
J的双亲:H
D:G I
A:B C这个程序能列出一个结点的孩子,却还列不出整棵树的全部结点。本章开头的第二个问题,还没有回答。
完整的程序放在下面,可以直接复制运行:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct TNode {
char data;
struct TNode *parent;
struct TNode *first;
struct TNode *next;
} TNode, *Tree;
void InitTree(Tree *T) { *T = NULL; }
TNode *Root(Tree *T) { return *T; }
char Value(Tree *T, TNode *p) { return p->data; }
TNode *Parent(Tree *T, TNode *p) { return p->parent; }
TNode *FirstChild(Tree *T, TNode *p) { return p->first; }
TNode *NextSibling(Tree *T, TNode *p) { return p->next; }
TNode *InsertChild(Tree *T, TNode *p, char x) {
TNode *q = (TNode *)malloc(sizeof(TNode)); /* 第一步:申请结点,放x */
if (q == NULL) return NULL;
q->data = x;
q->first = NULL;
q->parent = p;
if (p == NULL) { /* 空树:q就是根 */
q->next = NULL;
*T = q;
} else {
q->next = p->first; /* 第二步:q指向原来的第一个孩子 */
p->first = q; /* 第三步:p的第一个孩子改成q */
}
return q;
}
void FreeSubtree(TNode *p) {
TNode *c = p->first;
while (c != NULL) {
TNode *after = c->next; /* 先记下下一个兄弟 */
FreeSubtree(c); /* 释放这个孩子的子树 */
c = after;
}
free(p); /* 孩子都释放了,再释放自己 */
}
void DeleteSubtree(Tree *T, TNode *p) {
TNode *f = p->parent;
if (f == NULL) { /* p是根 */
*T = NULL;
} else if (f->first == p) { /* p是第一个孩子 */
f->first = p->next;
} else { /* 找到前一个兄弟 */
TNode *q = f->first;
while (q->next != p) q = q->next;
q->next = p->next;
}
FreeSubtree(p);
}
void ShowChildren(Tree *T, TNode *p) {
TNode *c;
printf("%c:", Value(T, p));
for (c = FirstChild(T, p); c != NULL; c = NextSibling(T, c))
printf("%c ", Value(T, c));
printf("\n");
}
int main(void) {
Tree T;
TNode *a, *b, *d, *h, *j;
InitTree(&T);
a = InsertChild(&T, NULL, 'A');
d = InsertChild(&T, a, 'D');
InsertChild(&T, a, 'C');
b = InsertChild(&T, a, 'B');
InsertChild(&T, b, 'F');
InsertChild(&T, b, 'E');
InsertChild(&T, d, 'I');
h = InsertChild(&T, d, 'H');
InsertChild(&T, d, 'G');
j = InsertChild(&T, h, 'J');
ShowChildren(&T, a);
ShowChildren(&T, d);
printf("J的双亲:%c\n", Value(&T, Parent(&T, j)));
DeleteSubtree(&T, h);
ShowChildren(&T, d);
DeleteSubtree(&T, d);
ShowChildren(&T, Root(&T));
return 0;
}练习1:加两个孩子之后
填空
还是上一节那棵字母树,C原来没有孩子。依次调用:
InsertChild(&T, C, 'K'),InsertChild(&T, C, 'L')
- C的first是
- L的next是
- K的next是
- K的parent是
InsertChild总是把新结点放在最前面。先加的K成了C的第一个孩子;再加L,L的next指向原来的第一个孩子K,C的first改成L。K是最后一个,next是NULL。两个都是C的孩子,parent都是C。
练习2:摘下来时少了一步会怎样?
单选
有人写DeleteSubtree时,漏了前一个兄弟那一行:
c
TNode *q = f->first;
while (q->next != p) q = q->next;
/* 漏了 q->next = p->next; */D的孩子依次是G、H、I。调用DeleteSubtree(&T, H)之后,再列出D的孩子,会怎样?
A
正常列出G、I
G的next没改,走到G之后,下一步还是H那个地址。
B
只列出G,到此为止
G的next不是NULL,它还记着H的地址。
C
走到G之后,去读已经释放的H结点,读到什么说不准
H已经还给系统,可G的next还指着它。程序可能打印乱码,也可能崩溃。
摘下来和释放是两件事。先让链上没有人再指着它,才能释放它。
到这里你有了用孩子兄弟表示法加parent写出的树的八个操作。读操作每个一行;InsertChild接在第一个孩子前面;DeleteSubtree先摘下来,分是根、是第一个孩子、在中间三种情形,再用递归释放子孙。下一步每个结点最多两个孩子,而且分左孩子、右孩子的树:二叉树。