前言

二叉树也有顺序存储结构和链式存储结构。由于二叉树是一种特殊的树，所以也可以通过顺序存储结构来实现。因为是顺序存储结构，所以要用数组来实现。

顺序存储结构

  • 存放数据的区域（数组），而且数组的下标也要体现节点间的逻辑关系。

  • 数组的大小要定义为完全二叉树的大小。当中某些节点有可能是为空的，所以顺序存储结构一般只用于完全二叉树，否则会造成空间的浪费。

链式存储结构

既然顺序存储结构的适用性不强，所以将引入二叉链表。它一般被分为两个区域——数据区和指向左右孩子的指针区。然而它还可以在指针区增加一个指针来指向父母。

1
2
3
4
5
6
7
8
9
typedef struct Node *PtrToNode;
typedef PtrToNode Tree;
typedef int ElementType;

typedef struct Node
{
    ElementType e;
    PtrToNode lchild, rchild;
}Node