二叉树的顺序存储

结构体定义

1
2
3
4
typedef struct {
    ElemType value;
    int isEmpty;
} Node;

静态声明

1
Node[] tree;

不忽略结点顺序的顺序二叉树的结点关系

为了保持数组索引和结点编号的一致性

在声明完成数组后一般第一个元素不会被使用即tree[0]被放弃使用，树的第一个结点会从tree[1]开始存储

这样如果需要访问树的第$i$个结点只需要访问tree[i]即可，不需要写成$i-1$，增加代码的可读性

对于一个存储在数组tree[MAXSIZE]的完全二叉树

当有一编号为$i$的结点，可以得出结点关系为

  • $2i$ 为其左结点的编号
  • $2i+1$ 为其右结点的编号
  • $\lfloor \frac{i}{2} \rfloor$ 为其父节点的编号 $\lfloor \rfloor$ 为向下取整符号 （假设现在考虑编号为3的结点 那么$\frac{3}{2}=1.5$ 此时如果向上取整得到2 显然2是其兄弟结点而不是父节点 因此应该向下取整）

使用顺序二叉树的使用场景

在使用顺序表进行存储时，如果碰到了非完全二叉树并且二叉树的高度比较高、结点数量比较少时时会有两种解决方案

  1. 将结点按照顺序继续存储进入顺序表
  2. 对于空白结点继续存储顺序表而不是忽略

显然使用第一种方案后我们就不能按照$2i,2i+1,\lfloor\frac{i}{2}\rfloor$去访问左结点、右结点、父节点

为了能够继续使用$2i,2i+1,\lfloor\frac{i}{2}\rfloor$去访问左结点、右结点、父节点我们使用第二种方案，但我们会发现有较多的空白结点被浪费

因此对于顺序二叉树我们一般仅在存储完全二叉树时使用

二叉树的链式存储

结构体定义

1
2
3
4
typedef struct {
    ElemType value;
    Node *lchild,*rchild;
}BinaryTree,*Node;

链式存储时的结点关系

对于某个结点i

想要找到其左/右节点可以通过

1
2
i -> lchild;
i -> rchild;

进行访问

但如果想要访问其父亲结点

就需要从父亲结点开始往下依次遍历结点