2. 二叉树¶
2.1. 定义与性质¶
二叉树 由一个有限的元素集合构成， 这些元素称为 结点 。 这个集合要么为空，要么由一个称为 根结点 的结点， 加上分别称为左 子树 和右子树的两棵二叉树组成； 这两棵子树互不相交，并且都与根结点不相交。 （"不相交"是指它们没有共同的结点。） 这些子树的根是根结点的 子结点 。 从结点到它的每个子结点都有一条 边 ， 而一个结点被称为其子结点的 父结点 。
如果 \(n_1, n_2, ..., n_k\) 是树中结点构成的一个序列， 其中对 \(1 \leq i < k\) ， \(n_i\) 都是 \(n_i+1\) 的父结点， 那么这个序列就称为从 \(n_1\) 到 \(n_k\) 的一条 路径 。 该路径的 长度 为 \(k-1\) 。 如果存在一条从结点 \(R\) 到结点 \(M\) 的路径， 那么 \(R\) 就是 \(M\) 的 祖先 ， 而 \(M\) 是 \(R\) 的 后代 。 因此，树中的所有结点都是树根的后代， 而根结点是所有结点的祖先。 树中结点 \(M\) 的 深度 是指从树根到 \(M\) 的路径长度。 树的 高度 是树中最深结点的深度。 深度为 \(d\) 的所有结点都位于树的第 \(d\) 层 上。 根结点是第 0 层上唯一的结点，它的深度为 0。 叶结点 是指两个子结点均为空的结点。 内部结点 是指至少有一个非空子结点的结点。
图 7.2.1 展示了用于标识二叉树各个部分的 若干术语。 图 7.2.2 展示了关于二叉树结构的一个重要事实。 由于 所有 二叉树结点都有两个子结点（其中一个或两个可能为空）， 图 7.2.2 中的两棵二叉树 并非 相同。
有两种受限形式的二叉树非常重要，值得专门命名。 满二叉树 中的每个结点，要么是恰好有两个 非空子结点的内部结点，要么是叶结点。 完全二叉树 则具有一种受限的形状： 从根结点开始，逐层自左向右地填充结点。 在高度为 \(d\) 的完全二叉树中，除第 \(d\) 层可能不满外， 其余各层都是全满的。 最底层的结点从左侧开始依次填充。
图 7.2.3 展示了满二叉树与完全二叉树的 差别。 [1] 这两种树形之间并没有特定的联系； 也就是说，图 7.2.3 (a) 中的树是满的 但不完全，而图 7.2.3 (b) 中的树是完全 但不满的。 堆 数据结构就是完全二叉树的一个例子。 Huffman 编码树 则是满二叉树的一个例子。
