侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

二叉树的存储

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 56 阅读 / 1,513 字

因为二叉树的定义和特性,树这种结构不能简单通过线性表的前后关系来存储,在线性表中,一个节点只有至多一个前驱节点和至多一个后驱节点,树则不然,一个节点可能有多个后驱节点,这个时候,我们需要通过更加复杂的结构才能存储树。二叉树是一种特殊的树,比多叉树要简单,因为特定节点至多只有两个节点,这就极大简化了相应的数据结构,使得通过线性表就可以实现二叉树的存储。

通过数组存储二叉树

对于特定的二叉树而言,比如满二叉树、完全二叉树,它们的节点之间是有一定关联关系的,以下面这棵完全二叉树为例:

1.png

我们按照从上到下,从左到右对所有节点编号,可以看到,下一层的左右子节点和对应父节点序号存在某种数学关系,如果父节点的序号是 i,其对应左子节点位于 2i 的位置上,对应右子节点位于 2i + 1 的位置上,我们可以参照这个规则将上述完全二叉树存储到数组中:

1.png

注意我们的下标从 1 开始(根节点),索引为 0 的下标舍弃,浪费这个空间,以方便计算。这样,我们就可以从根节点开始,依次将所有节点元素存放到数组中,并且可以根据节点间的数学关系很方便地遍历整棵树。此外,由于完全二叉树的特殊性,除了第一个元素之外,该数组不存在任何空间的浪费。由于满二叉树是完全二叉树的子集,所以也可以通过这种方式来存储。

那么其它二叉树呢?当然也可以按照这种思路来做,我们把不存在的节点补全,比如假设上述序号为 4、6、8、9 的元素不存在:

1.png

可以看到,我们将不存在的元素补上,只是对应位置值为 null,缺失的节点越多,数组的「空洞」也就越多,如果是极端情况,比如二叉树只包含 1、3、7 三个元素,那么数组中将会存在大量的「空洞」,浪费大量的空间,而且也会影响性能。

综上,数组适合满二叉树、完全二叉树这些特殊二叉树的存储,一些比较稠密的二叉树也可以用数组,如果二叉树比较稀疏就不适合用数组了,我们可以通过链表来存储它们。

通过链表存储二叉树

理论上来说,链表适用于所有的二叉树存储,只不过这里我们需要对线性表中的链表进行扩展,因为二叉树特定节点最多有两个子节点,所有我们在链表结点上设置两个指针域,分别指向左右子节点,所以这种链表结构又被称作二叉链表。我们可以通过一个类表示二叉链表的结点:

class Node {
public:
    int data;
    int left;
    int right;

    Node(int data){
        this->data = data;
    }
};

如果要用二叉链表表示上面的完全二叉树,对应的图示如下:

1.png

不管是什么样结构的二叉树,用链表来存储都不会存在空间的浪费。

0

评论区