引入
前面,我们学习了树的一些基础内容,今天我们就来看看,树有哪些存储结构。说到存储结构我们会想到线性表中的顺序存储结构和链式存储结构,那么树会怎么设计自己的存储结构呢?我们一起来看一看~
树的存储结构
要存储树,用简单的顺序存储结构和链式存储结构都不行。因为树中有双亲、孩子、兄弟这些概念,我们不能用简单的顺序、链式存储结构表达树中各个结点的情况。所以,根据不同的角度,我们有三种存储结构表示一棵树
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
双亲表示法
双亲表示法,顾名思义,就是以双亲作为索引的关键词的一种存储方式。
- 我们先划出一段连续存储空间,类似数组,存储每一个结点
- 在每个结点中,附设一个指示其双亲结点在数组中位置的元素
- 也就是说,每个结点直到自己和自己的双亲
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 保存中间兄弟的信息
- 等等
存储结构
我们看到,对存储结构进行不同的修改,就可以保存不同的信息,相应的,我们可以根据需要定义不同的存储结构,然后保存每个结点你需要的信息。
一个存储结构设计的是否合理,取决于基于该存储结构的运算是否适合、是否方便,时间复杂度好不好等等。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。