说到存储结构,就会想到我们前面章节讲过的顺序存储和链式存储两种结构。
先来看看顺序存储结构,用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的,(一对一,前驱和后继的结构)
对于树这样一多对的结构呢?
树中某个结点的孩子可以有多个,这就意味着,无论按何种顺序将树中所有结点存储到数组中,结点的存储位置都无法直接反映逻辑关系,你想想看,数据元素挨个的存储,谁是谁的双亲,谁是谁的孩子呢?
简单的顺序存储结构是不能满足树的实现要求的。
不过充分利用顺序存储和链式存储结构的特点,完全可以实现对树的存储结构的表示。
我们这里要介绍三种不同的表示法:
- 双亲表示法、
- 孩子表示法、
- 孩子兄弟表示法。