数据结构第七讲：二叉树基本概念

§6.2 二叉树

二叉树 或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别称做根节点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。 提醒：度为 2 的树不可能是空树，因此二叉树与度为 2 的树不同。

满二叉树 每一层都满（第 $i$ 层恰好有 $2^{i-1}$ 个节点）时、，且叶子节点在同一层上。

完全二叉树 除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个节点。

完全二叉树至多只有最下边两层节点的度数小于 2。
按层序编号后对编号为 $k$ 的节点，若 $2k \leqslant n$，则是分支节点，否则是叶子节点。其父节点编号为 $\lfloor \cfrac{n}{2} \rfloor$，左右子节点编号分别为 $2k,2k+1$。
若 $n$ 为奇数，则每个分支节点都既有左子节点，也有右子节点，也就是没有度为 1 的节点，即 $n_{1}=0$；若 $n$ 为偶数，则编号最大的分支节点只有左子节点，没有右子节点，其余分支节点都有左右子节点，也就是恰好有一个度为 1 的节点，即 $n_{1}=1$。
完全二叉树的叶子节点数是 $\lceil \cfrac{n}{2} \rceil$。

完全二叉树或满二叉树采用 顺序存储结构 比较合适，既能够最大可能地节省存储空间，又可以利用数组元素的下标确定节点在二叉树中的位置以及节点之间的关系。典型的例子是普通线段树。

如果需要增加很多空节点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构，而是用 二叉链存储结构。典型的例子是动态开点线段树。

这节主要是理解。

创建二叉树：这是由逻辑结构即括号表示法表示的二叉树字符串转为存储结构，具体实现是用栈维护的，不需要递归，置临时变量表示当前处理的是左孩子还是右孩子。

其它常见操作都是基于递归的。