引入
前面，我们学习了树的一些基础内容，今天我们就来看看，树有哪些存储结构。说到存储结构我们会想到线性表中的顺序存储结构和链式存储结构，那么树会怎么设计自己的存储结构呢？我们一起来看一看~
树的存储结构
要存储树，用简单的顺序存储结构和链式存储结构都不行。因为树中有双亲、孩子、兄弟这些概念，我们不能用简单的顺序、链式存储结构表达树中各个结点的情况。所以，根据不同的角度，我们有三种存储结构表示一棵树
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
双亲表示法
双亲表示法，顾名思义，就是以双亲作为索引的关键词的一种存储方式。
- 我们先划出一段连续存储空间，类似数组，存储每一个结点
- 在每个结点中，附设一个指示其双亲结点在数组中位置的元素
- 也就是说，每个结点直到自己和自己的双亲
1 |
|
| 数组下标 | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | E | 1 |
| 3 | H | 2 |
| 4 | I | 2 |
| 5 | J | 2 |
| 6 | C | 0 |
| 7 | D | 0 |
| 8 | F | 7 |
| 9 | G | 7 |
| 10 | K | 9 |
上面这就是根为 A 的树在连续内存中存储的情况
- r 根的位置为 0
- n 结点的个数为 11，因为有11个圈
- 下标为0的结构体中，data 为结点的值 A，父母情况为-1，因为根没父母
- 下标为1的结构体中，data 为结点的值 B，父母的下标是0
- 下标为2的结构体中，data 为结点的值 E，父母的下标是1
- 依次类推
结构体 tree 描述了树的情况
- 结点是用的哪个结构体，连续存储的 MAXSIZE 是多少
- 根节点在哪
- 现在树上有多少个节点了
结构体 pt 描述了结点的情况
- 结点的值是多少
- 该结点的爹妈，也就是双亲的下标在哪里
所以，我们在使用双亲表示法的时候，这种存储结构，我们找父母
- 结点包含父母信息
- 直到找到父母信息是 - 1 的时候
- 证明找到了树的根。
- 时间复杂度是 O( 1 )
但是我们在找某个结点的孩子是什么的时候，就不行了，就需要遍历整个树去寻找…
看着这张图，我们改一下结构，让结点中多包含一些信息
| 数组下标 | data | parent | child-1 | child-2 |
|---|---|---|---|---|
| 0 | A | -1 | 1 | 6 |
| 1 | B | 0 | 2 | -1 |
| 2 | E | 1 | 3 | 4 |
| 3 | H | 2 | -1 | -1 |
| 4 | I | 2 | -1 | -1 |
| 5 | J | 2 | -1 | -1 |
| 6 | C | 0 | -1 | -1 |
| 7 | D | 0 | 8 | 9 |
| 8 | F | 7 | -1 | -1 |
| 9 | G | 7 | 10 | -1 |
| 10 | K | 9 | -1 | -1 |
我们在原有结点的结构体中，增加了两个孩子结点的信息，这样我们的每个结点就都包括
- 一个父母信息，有且只能有一个双亲
- 两个孩子信息，当然这个并不全，但比刚才没有强
相应的，我们也可以在结点的结构体信息中包含其他信息
- rightsib 保存右兄弟的信息
- midsib 保存中间兄弟的信息
- 等等
存储结构
我们看到，对存储结构进行不同的修改，就可以保存不同的信息，相应的，我们可以根据需要定义不同的存储结构，然后保存每个结点你需要的信息。
一个存储结构设计的是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等等。
尾巴
这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。
