记双亲
回到本章开头的第三个问题:怎么把树放进内存?
线性表好办,一个接一个,放在相邻的格子里,关系就有了。树不行:一个结点后面跟着好几个结点,相邻表示不出来。关系只能明着记下来。
从这一节起,我们只关心树的结构,结点不再起名字,用字母代替。下面这棵树有10个结点:
4.1节的结尾说过,程序要记住每个结点的双亲是谁,或者每个结点的孩子是谁。两条路都试一试。每试一种,都在这棵树上数一数,4.2节的操作要走几步。这一节只讲思路,代码放到下一节。
本节问题树的关系,记成什么样,操作才走得少,结点又好设计?
先试记双亲。每个结点只有一个双亲,一个数就记下了。把10个结点放进一张表,parent记着双亲在第几行。根没有双亲,记成−1:
| 下标 | data | parent |
|---|
| 0 | A | −1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 1 |
| 5 | F | 1 |
| 6 | G | 3 |
| 7 | H | 3 |
| 8 | I | 3 |
| 9 | J | 7 |
这种存法叫双亲表示法。
表里每一行放一个结点。程序里,一个结点就用它所在的行号来代表;字母只是我们给它起的名字,记在这一行的data里。树图上每个结点旁边的小字,就是它的行号:
拿"找B的孩子"完整走一次:
- B是第1行。看图上B旁边的小字。
- 找parent等于1的行。从第0行往下看,第4行、第5行是。
- 读这两行的data,是E、F。B的孩子就是E、F。
第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)。
双亲这个关系,每个结点正好一个,好记;可它的方向朝上,往下找就得扫整张表。
记孩子
再试记孩子。方向朝下了,可是每个结点有几个孩子?个数不定。
先用最直接的办法:每个结点都留够格子。这棵树的度是3,那就每个结点留3格,放孩子的位置:
textA:B C D
B:E F 空
C:空 空 空
D:G H I
H:J 空 空
E、F、G、I、J:空 空 空
算一算:10个结点,每个3格,一共30格。树有10个结点,就有9条边,也就是只用了9格,空着21格。
一般地,n个结点、度为d的树,要n × d格,只用n − 1格。孩子最多的那个结点,决定了所有结点的大小。
个数不定的东西,第2章有现成的办法:用链表串起来,有几个就申请几个。表里每个结点带一条孩子链,链上的每一格记一个孩子在第几行:
textA ──► [B] ──► [C] ──► [D]
B ──► [E] ──► [F]
D ──► [G] ──► [H] ──► [I]
H ──► [J]
C、E、F、G、I、J:链是空的
这种存法叫孩子表示法。链上一共9格,一格不多。
结点还是放在表里,用行号代表。程序里,链上的格子记的是孩子的行号,比如[E]那一格记的是4;这里写成字母,是为了好读。
找孩子一步到位。D(第3行)的第一个孩子是谁?看第3行那条链的第一格,是G,是O(1)。
这回轮到找双亲慢了。J(第9行)的双亲是谁?谁的链上有J,谁就是它的双亲。只能从第0行的A开始,一行一行查它们的链:A的链上是B、C、D,不是;B的链上是E、F,不是;一直查到第7行H的链,才看到J。
最坏要把n行、n − 1格都看一遍,是O(n)。
还有一处别扭:这里要两种东西,一种是表里的结点,一种是链上的格子。
下一个兄弟记在哪里
孩子表示法还有一个操作没看:NextSibling。拿E来问:E的下一个兄弟是谁?
答案是F。可是F这条信息,记在哪里?看B的那条孩子链:
上面一行是B,中间是它链上的两格,下面是E、F两个结点,虚线箭头表示这一格记的是哪个孩子。"E的下一个是F",记在E那一格到F那一格的箭头上。E结点自己身上,什么都没有。
所以,要找E的下一个兄弟,得这样找:
- 先找E的双亲。E身上没记,只能把每一行的链都查一遍,查到B的链上才看到E。这一步,就是上一页找双亲的那一大圈,O(n)。
- 在B的链上,找到记着E的那一格。从第一格往后走,走过的格子不会超过B的孩子数。
- 看它的下一格。下一格记的是F,答案就是F。
第一步就要O(n)。问的是E自己的事,答案却记在别人的链上,得先绕一大圈。
那就把它搬过来:E的下一个兄弟是F,就记在E自己身上。
搬得过来吗?4.1节说过,除了根,每个结点恰好有一个双亲,所以每个结点只出现在一条孩子链上,它在链上的"下一格"也只有一个。一个结点,一个"下一个兄弟",一个指针就记得下。
一步一步变过去
把这个办法用到整棵树上,在树的样子上看。下面每一步,左边是原来的树,右边是变到这一步的样子。图里三种颜色的边:
长子边(first)兄弟边(next)要删的边
第0步:原来的树。每个结点连着自己全部的孩子。A和D各连着3个孩子,B连着2个,H连着1个,每个结点连出去的线不一样多。
第1步:只留长子边。每个结点只留下通往第一个孩子的那条边,画成绿色。第一个孩子也叫长子。A留下A到B,B留下B到E,D留下D到G,H留下H到J。其余的孩子边画成橙色虚线,准备删掉。
第2步:连上兄弟边。同一个双亲的孩子,从左到右连起来,画成紫色:B到C到D,E到F,G到H到I。
第3步:删掉橙色的边。删了5条,加了5条,边的总数还是9。现在每个结点最多连出两条:一条往下,连着它的第一个孩子;一条往右,连着它的下一个兄弟。
规则只有一句:双亲只连第一个孩子,其余孩子由兄弟一个接一个连起来。
往下的那条线叫first,往右的那条线叫next。每个结点就记这两个地址,这种存法叫孩子兄弟表示法。画成结点图,向下的箭头是first,向右的箭头是next,没有箭头就是NULL:
记住一句话:first往下走一代,next往右找兄弟。
两个指针就够了
数一数。原来的树有9条边。留下的4条绿色边,就是4个first;新连上的5条紫色边,就是5个next。边的总数没变,只是换了连法。
再数指针。10个结点,每个2个指针,一共20个,用了9个,空着11个。比每个结点留3格时空着21格少,可这不是最要紧的。
最要紧的是:每个结点都只有两个指针,大小统一,再也不用为"有几个孩子"发愁。"一个结点有不定个孩子",换成了"第一个孩子"和"下一个兄弟",每个结点各只有一个,方向又都朝下。
再看操作要走几步。D的第一个孩子?读D的first,是G。E的下一个兄弟?读E的next,是F。都只读一个指针,是O(1)。上上页那一大圈不见了。
只差一个操作:Parent。沿着first和next只能往下、往右,回不到上一级。所以再加一个指针parent,记着双亲,Parent也就是读一个指针,O(1)。图里为了清楚,没有画它。
教材里的孩子兄弟表示法
教材和考研说的孩子兄弟表示法,每个结点只有两个指针:第一个孩子和下一个兄弟。这里多加的parent,是因为4.2节的操作集里有Parent。不需要找双亲的程序,可以不加。
三种存法比一比
三种存法,问的是同一个问题:树的关系,拆成什么来记。
| 存法 | 记什么 | 好在哪 | 难在哪 |
|---|
| 双亲表示法 | 双亲:每个结点一个,方向朝上 | 找双亲O(1),每个结点只多一个数 | 找孩子要扫整张表 |
| 孩子表示法 | 孩子:个数不定,方向朝下 | 找孩子O(1) | 每个结点留够格子就浪费;改用链表,又要两种东西,找双亲、找兄弟都要查所有的链 |
| 孩子兄弟表示法 | 第一个孩子、下一个兄弟:每个结点各一个,方向朝下 | 结点统一成两个指针;找孩子、找兄弟都是O(1) | 找双亲要绕远,可以再加一个parent补上 |
前面几页在例子上数出来的步数,汇总在一起。n个结点,每个操作最多要走几步:
| 操作 | 双亲表示法 | 孩子表示法 | 孩子兄弟表示法(加parent) |
|---|
| Parent | O(1) | O(n) | O(1) |
| FirstChild | O(n) | O(1) | O(1) |
| NextSibling | O(n) | O(n) | O(1) |
双亲表示法的NextSibling,要接着往下扫,找下一个parent相同的行。孩子表示法的NextSibling,就是"下一个兄弟记在哪里"那一页绕的一大圈。
回到本节问题,也回到本章开头的第三个问题:怎么把树放进内存?要看常做的是什么。只需要往上找、很少找孩子的程序,双亲表示法最省。要上下都走,就用孩子兄弟表示法,再加一个parent。
练习1:存一棵小树
一本菜谱的目录:菜谱下面依次是凉菜、热菜、附录;凉菜里有拍黄瓜;热菜里依次是炒菜、炖菜。
填空
先用双亲表示法,按菜谱0、凉菜1、热菜2、附录3、拍黄瓜4、炒菜5、炖菜6编号。再用孩子兄弟表示法,孩子的先后和图上一样。
- 双亲表示法里,炖菜的parent是
- 孩子兄弟表示法里,热菜的first是
- 热菜的next是
- 拍黄瓜的next是
炖菜的双亲是热菜,热菜编号是2。热菜的第一个孩子是炒菜。热菜的下一个兄弟是附录,兄弟是和它并排的,不是它的孩子。拍黄瓜是凉菜唯一的孩子,后面没有兄弟。
练习2:绿色、紫色、橙色各几条?
填空
照上面的四步,把这棵树改成孩子兄弟表示法。
- 留下的长子边(绿色)有 条
- 要删的边(橙色)有 条
- 新连上的兄弟边(紫色)有 条
- R的next是
原来有5条边。留下的是P到Q、S到T。要删的是P到R、P到S、S到U。新连上的是Q到R、R到S、T到U。R的下一个兄弟是S。留下的加新连的,还是5条。
到这里你有了树的三种存法。双亲表示法记双亲,找双亲O(1),找孩子要扫整张表;孩子表示法记孩子,个数不定,要用链表,找双亲、找兄弟都要绕;孩子兄弟表示法把"不定个孩子"换成"第一个孩子"和"下一个兄弟",每个结点统一成两个指针:first往下走一代,next往右找兄弟。从树的样子看,就是双亲只连第一个孩子,兄弟一个接一个连起来。