引入
前面,我们介绍了双亲表示法
,每个结点中出了节点的值,还保存了parent
的信息。今天我们换个角度,用孩子表示法
来看看如何构建树的存储结构。
想一想
现在双亲表示发的问题在哪?
- 只能体现双亲信息和该结点信息
- 没有孩子的信息
- 增加节点内的结构只能增加部分孩子信息,如3个、5个
- 如果某个子节点大量孩子加入,会造成内存空间浪费
想达到什么效果?
- 能体现孩子的信息
- 孩子无论增加多少,都可以只浪费一定的内存空间
- 如果能再包含双亲的信息就更好了!
数组下标 | Data | Pointer | P1 | P1-Node | P2 | P2-Node | P3 | P3-Node |
---|---|---|---|---|---|---|---|---|
0 | A | -> | 1 | -> | 2 | -> | 3 | NULL |
1 | B | -> | 4 | NULL | ||||
2 | C | NULL | ||||||
3 | D | -> | 5 | -> | 6 | NULL | ||
4 | E | -> | 7 | -> | 8 | -> | 9 | NULL |
5 | F | NULL | ||||||
6 | G | -> | 10 | NULL | ||||
7 | H | NULL | ||||||
8 | I | NULL | ||||||
9 | J | NULL | ||||||
10 | K | NULL |
经过修改,我们看这个架构,由数组和链表组合而成
- 数组存储结点信息和链表的头部地址
- 链表则存储者孩子的信息
- 例如:A 是根,下标是0,A 有三个孩子,三个孩子分别在下标1、2、3,A 的指针域是链表的头部,指向了三个孩子所在的下标。
- 这种通过链表的方式扩展孩子,每个结点只要留出一个用于存储地址的指针域空间,就可以通过链表的方式不断的增加孩子的数量了。
等等…我们不是说最好再有双亲信息
就更完美了吗?
没关系,我们把上一节的双亲表示法和孩子表示法结合组成双亲孩子表示法
数组下标 | Data | Parent | Pointer | P1 | P1-Node | P2 | P2-Node | P3 | P3-Node |
---|---|---|---|---|---|---|---|---|---|
0 | A | -1 | -> | 1 | -> | 2 | -> | 3 | NULL |
1 | B | 0 | -> | 4 | NULL | ||||
2 | C | 0 | NULL | ||||||
3 | D | 0 | -> | 5 | -> | 6 | NULL | ||
4 | E | 1 | -> | 7 | -> | 8 | -> | 9 | NULL |
5 | F | 3 | NULL | ||||||
6 | G | 3 | -> | 10 | NULL | ||||
7 | H | 4 | NULL | ||||||
8 | I | 4 | NULL | ||||||
9 | J | 4 | NULL | ||||||
10 | K | 6 | NULL |
我们将结点的信息再次增加一个 Parent 信息,这样我们既可以直到孩子的信息,又可以直到双亲的信息,并且孩子的后期扩展也不会大量的浪费内存空间。
代码
我们来看看如何构建这个双亲孩子表示法
1 |
|
之后还有孩子兄弟表示法,我们先学习完二叉树的概念,然后再看看孩子兄弟表示法。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。