基本概念和实现

概念和基本术语

关于二叉树有一些基本概念需要介绍一下，以下概念都针对节点N。

1. 父节点parent，节点的唯一前驱。
2. 子节点children，节点向下的后继，二叉树可以分为左子树lchild和右子树rchild。
3. 兄弟节点sibling，与节点拥有同一个父节点的其他节点。
4. 子树subtree，以某个子节点为根节点的树，当然二叉树也有左子树和右子树。
5. 叶子节点leaf，没有子节点的节点。
6. 根节点root，唯一一个没有前驱的节点，从根节点开始可以到达所有节点。
7. 深度depth，从某个节点到最远的叶子节点的距离（层数），在本课程里约定根节点的深度为1。
8. 树的深度，规定树的深度是所有节点深度的最大值。即离根节点最远的节点的层数。

二叉树的性质

对于二叉树，每个节点最多有两个子节点。我们可以很容易推断出高度和节点数目之间的关系。

对于深度是$n$的树，节点最少的情况是每个节点都只有一个子节点，此时树相当于退化到链表。因此节点数目也是$n$。

而节点最多的情况当然是除叶子节点之外，每一个节点都有两个子节点，我们很容易可以算出这种情况下节点数目是$n^2-1$：

对于右侧这种最多节点的情况，我们把这种树称为满二叉树。

满二叉树的条件是比较苛刻的，只有在二叉树有$1,3,7,15,31...2^n-1$个节点的条件下才可能构成满二叉树。

如果我们把条件放宽一些，允许节点以从上到下，从左到右的方式依次排列。这样第$n-1$层上构成满二叉树，而第$n$层的节点从左向右填充，中间不留空位，我们把这样的二叉树称为完全二叉树。

左边的两棵树都是完全二叉树，遵循从上到下从左到右的排列方式，中间不留空位。右侧的两个树则都不是，他们在红色框的部分留了空位。

显然满二叉树是完全二叉树的一种特例。

根据完全二叉树的这个性质，我们可以很容判断出某个节点数目下的完全二叉树有多少层。

所以如何换算？

一棵高度为$n$的完全二叉树，最多有多少个节点，最少有多少个节点？

给定节点数目$n$的完全二叉树，能知道他的层数吗？

二叉树的顺序表示

对于二叉树这种非线性的结构，好像很难用顺序结构来表示，但其实是可以的。

完全二叉树的线性表示

我们先考虑完全二叉树的情况，由于完全二叉树实际上是按从上到下，从左到右依次排列的。因此我们可以构成如下的线性映射关系：

为了符合完全二叉树的定义要求，显然增加和删除节点，只能在数组的尾部进行。

除了将节点放到对应的位置，更重要的是节点关系如何确定，他们的关系已经隐含在下标里了：

1. 下标$n$的节点，其父节点的下标为$(n-1)/2$
2. 下标为$n$的节点，其左孩子下标为$2\times n+1$，右孩子的下标为$2\times (n+1)$

普通二叉树的线性表示

对于普通二叉树，可以视为完全二叉树去掉某些节点后的产物，我们只需要针对性地将对应的下标置为0，表示该位空缺，即可用顺序表来表示普通二叉树：

同样的，节点之间的关系也可以通过下标计算来简单推导。

这种方式在表示完全二叉树时非常有效，因为数据中间不可能存在空位，是完全紧凑的。同时添加元素总发生在顺序表的最后，开销很小。

但对于普通二叉树，这种表示方式的缺点也很明显，需要大量的空位来维持节点之间的关系。如果树是稀疏的，那么他就会变得非常不经济。最极端的情况是所有节点都只有左或者右节点，大家可以算算这种情况下空间利用率是多少。

因此顺序表示法我们一般只用在表示完全二叉树上，普通的二叉树我们一般用链式表示法。

二叉树的链式表示

链式表示法也非常简单，用左右两个指针分别指向孩子节点即可：

struct BTreeNode {
    int value;
    BTreeNode* left_child;
    BTreeNode* right_child;
    BTreeNode* parent; // 可选
};

在有些情况下，我们可能会希望由子树进行上溯，对于这种情况，可以增加一个parent指针来指向其父节点。注意这种情况下，在节点发生变化时，要注意也必须更新parent指针。

和链表一样，如果节点没有左或者右子树，那么我们就令其等于空。