Skip to content
第4章

4.3 树的存储结构 ​

记双亲 ​

回到本章开头的第三个问题:怎么把树放进内存?

线性表好办,一个接一个,放在相邻的格子里,关系就有了。树不行:一个结点后面跟着好几个结点,相邻表示不出来。关系只能明着记下来。

从这一节起,我们只关心树的结构,结点不再起名字,用字母代替。下面这棵树有10个结点:

ABEFCDGHJI

4.1节的结尾说过,程序要记住每个结点的双亲是谁,或者每个结点的孩子是谁。两条路都试一试。每试一种,都在这棵树上数一数,4.2节的操作要走几步。这一节只讲思路,代码放到下一节。

本节问题
树的关系,记成什么样,操作才走得少,结点又好设计?

先试记双亲。每个结点只有一个双亲,一个数就记下了。把10个结点放进一张表,parent记着双亲在第几行。根没有双亲,记成−1:

下标dataparent
0A−1
1B0
2C0
3D0
4E1
5F1
6G3
7H3
8I3
9J7

这种存法叫双亲表示法。

表里每一行放一个结点。程序里,一个结点就用它所在的行号来代表;字母只是我们给它起的名字,记在这一行的data里。树图上每个结点旁边的小字,就是它的行号:

A0B1E4F5C2D3G6H7J9I8

拿"找B的孩子"完整走一次:

  1. B是第1行。看图上B旁边的小字。
  2. 找parent等于1的行。从第0行往下看,第4行、第5行是。
  3. 读这两行的data,是E、F。B的孩子就是E、F。
A0B1E4F5C2D3G6H7J9I8

第1步和第3步,只是因为我们用字母出题:先把字母换成行号,最后再把行号换回字母。程序手里拿的本来就是行号,4.2节的FirstChild、NextSibling返回的都是一个结点,在这里就是一个行号;程序从来不按字母去找结点。要显示名字时,读这一行的data就行。真正花工夫的,只有第2步:扫表。

下面就不再换来换去,结点直接写成"字母(第几行)"。

找双亲一步到位。J(第9行)的双亲是谁?读第9行的parent,是7,就是H(第7行)。不管树有多大,都只读一个数,是O(1)。

找孩子就慢了。D(第3行)的第一个孩子是谁?要找parent等于3的行,没有别的办法,只能从第0行往下看:第0行到第5行都不是,看到第6行才找到,是G。一共看了7行。

C(第2行)有没有孩子?要找parent等于2的行。10行全看完,一行都没有,才敢说C没有孩子。

n个结点,找孩子最多要看n行,是O(n)。

双亲这个关系,每个结点正好一个,好记;可它的方向朝上,往下找就得扫整张表。

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