《计算思维与算法入门》 —2.7.2 二叉树

2.7.2  二叉树

一般树结构在计算机内存中的存储方式以链表（Linked List）为主。对于n叉树来说，每个节点的度数都不相同，当n=2时，它的链接浪费率最低。为了避免树结构空间浪费的缺点，所以我们最常使用二叉树（Binary Tree）结构来取代其他的树结构。

二叉树（又称为Knuth树）是一个由有限节点所组成的集合，此集合可以为空集合，或由一个树根及其左右两棵子树组成。简单地说，二叉树最多只能有两个子节点，就是度数小于或等于2。二叉树每个节点在计算机中的数据结构如图2-54所示。

图2-54  二叉树节点在计算机中的数据结构示意图

二叉树和一般树的不同之处整理如下：

（1）树不可为空集合，而二叉树可以。

（2）树的度数为d≥0，而二叉树的节点度数为0≤d≤2。

（3）树的子树间没有次序关系，而二叉树有。

下面我们来看一棵实际的二叉树，如图2-55所示。

图2-55  二叉树

图2-55是以A为根节点的二叉树，包含以B、D为根节点的两棵互斥的左子树和右子树，如图2-56所示。

图2-56  两棵互斥的左子树和右子树

以上这两棵左右子树属于同一种树结构，不过却是两棵不同的二叉树，原因是二叉树必须考虑前后次序关系。这点大家要特别注意。

由于二叉树应用得相当广泛，因此衍生了许多特殊的二叉树结构。我们分别介绍如下：

1．满二叉树（Fully Binary Tree）

如果二叉树的高度为h（h≥0），树的节点数为2h1，我们就称此树为“满二叉树”，如图2-57所示：

图2-57  满二叉树

2．完全二叉树（Complete Binary Tree）

完全二叉树的高度为h，所含的节点数小于2h1，但其节点的编号方式如同高度为h的满二叉树一样，从左到右、从上到下的顺序一一对应，如图2-58所示。

图2-58  完全二叉树和非完全二叉树

3．斜二叉树（Skewed Binary Tree）

当一个二叉树完全没有右节点或左节点时，我们就把它称为左斜二叉树或右斜二叉树，如图2-59所示。

图2-59  左斜二叉树和右斜二叉树

4．严格二叉树（Strictly Binary Tree）

二叉树中的每一个非终端节点均有非空的左右子树，如图2-60所示。

图2-60  严格二叉树