Tim的资源站

二叉树通常采用两种存储方式：顺序存储结构和链式存储结构。

一、顺序存储结构

二叉树是非线性结构，一般情况下用顺序存储难以表达出数据之间的逻辑关系。然而，当二叉树是完全二叉树时，可用顺序存储结构。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下是一棵完全二叉树及其相应的存储结构。

完全二叉树的顺序

完全二叉树的存放

在 C++ 语言中，这种存储形式的类型定义如下：

#define maxsize 100

class QbTree {
  public:
    DataType elem[maxsize]; //根存储在下标为1的数组单元中

    int n;  //当前完全二叉树的结点个数

    void CreateBTree(int m);   //构造一棵完全二叉树

    int LeftCHild(int i);   //获取给定结点的左孩子

    int RightChild(int i);   //获取给定结点的右孩子

    int Parent(int i);    //获取给定结点的双亲
}

这种顺序存储结构不仅能将结点的值存储起来，同时还能体现出结点间的关系（父子关系及兄弟关系）。例如，编号为 i 的结点存储在数组中下标为 i 的元素中，由性质5可知，其左孩子结点在数组中的元素的下标为2i（若存在的话），右孩子下标为2i+1（若存在的话），其父结点的下标为(i/2)（若存在的话）。这种存储结构的特点是空间利用率高、寻找孩子和双亲比较容易。

二、链式存储结构

顺序存储虽然方便，但也存在问题。若二叉树不是完全二叉树，则为了体现出这种关系，就不得不空出许多元素，这就造成了空间的浪费。极端情况下，仅有 n 个结点的二叉树，却需要2n-1个元素空间，这显然是不能接受的。对二叉树而言，最常用的存储结构是链式存储结构。

二叉链表结点结构：

其中，Leftchild 和 Rightchild 是分别指向该结点左孩子和右孩子的指针，data 是数据元素的内容。

显然，一个二叉链表由头指针唯一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。在一个具有 N 个结点的二叉树中，共有 2N 个指针域，其中只有 N-1 个用来指示结点的左孩子和右孩子，其他的 N+1 个指针域为空。

一棵二叉树及相应的二叉链式存储结构:

这种存储结构的特点是寻找孩子结点容易，寻找双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下图所示。

三叉链表结点结构：

下一篇文章将介绍二叉树链式存储结构下的C++定义及算法实现。