5.2 二叉树

  • 「二叉树 binary tree」 是有限多个结点的集合,这个集合或者是空集,或者由一个根结点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。
  • 『二叉树和树的区别』 一棵树至少含有一个结点,而二叉树可以为空。二叉树的子树有顺序,而树的子树没有顺序。如下图为两棵不同的二叉树。

两棵不同的二叉树

  • 「ADT 二叉树」 Binary_Tree 是结点的有限集合,该集合或者为空,或者由根结点、左 Binary_Tree 和右 Binary_Tree 组成。
class Binary_Tree
{
    Binary_Tree Create() {
        // 创建一个空二叉树
    }
    bool IsEmpty(Binary_Tree bt) {
        if (bt == 空二叉树) return true;
        else return false;
    }
    Binary_Tree MakeBT(Binary_Tree bt1, Element item, Binary_Tree bt2) {
        return 二叉树,其左子树为 bt1,右子树为 bt2,根结点的数据为 item
    }
    Binary_Tree Lchild(Binary_Tree bt) {
        if (IsEmpty(bt)) return 错误
        else return bt 的左子树
    }
    Element Data(Binary_Tree bt) {
        if (IsEmpty(bt)) return 错误
        else return bt 的根结点的数据
    }
    Binary_Tree Rchild(Binary_Tree bt) {
        if (IsEmpty(bt)) return 错误
        else return bt 的右子树
    }
}
二叉树的性质
  • 引理 1:『结点数的最大值』

    1. 在二叉树中,第 ii 层的结点数最多为 2i1,i12^{i-1}, i \geq 1
    2. 在深度为 kk 的二叉树中,结点总数最多为 2k1,k12^k - 1, k \geq 1
  • 引理 2:『叶子结点的个数与度为 2 的结点个数之间的关系』 对任何非空的二叉树 TT,如果叶结点的个数为 n0n_0,而度为 2 的结点数为 n2n_2,则 n0=n2+1n_0 = n_2 + 1

    • 证明:设 n1n_1 为二叉树中度为 1 的结点数,nn 是结点总数。由于 TT 中所有结点的度都小于等于 2,故有: n=n0+n1+n2 n = n_0 + n_1 + n_2 如果对二叉树中的分支数进行计数,可以看到,除根结点外,其余结点都有一个进入分支。设 BB 为分支总数,则 n=B+1n = B + 1。又因为所有的分支都从度为 1 和度为 2 的结点发出的,从而,B=n1+2n2B = n_1 + 2n_2,因此,可以得到: n=1+n1+2n2 n = 1 + n_1 + 2n_2 用第二个公式减去第一个公式,整理之后得: n0=n2+1 n_0 = n_2 + 1 即得证。
  • 一个深度为 kk「满二叉树 full binary tree」 是深度为 kk 且具有 2k12^k - 1 个结点的二叉树 (k0)(k \geq 0)

5-7

深度为 4 且结点顺序编号的满二叉树

  • 「完全二叉树 complete binary tree」 若将满二叉树像上图对结点进行顺序编号。一个深度为 kk 且有 nn 个结点的二叉树是 完全的 当且仅当其结点与深度为 kk 的满二叉树结点编号 11nn 相对应。
  • 「倾斜树 skewed tree」 树中的每个结点都是父亲的左儿子,树就是向左倾斜的。或者,每个结点都是父亲的右儿子,树就是向右倾斜的。

5-8

倾斜二叉树(左)和完全二叉树(右)

二叉树的存储表示
  • 『数组存储表示』 由于任意一棵二叉树都可以向上图那样从 11nn 编号,因此可以使用一维数组来存储这些结点(这里不使用数组的第 0 个位置)

5-9

上图倾斜二叉树的数组存储表示(上)和上图完全二叉树的数组存储表示(下)

  • 『链接式存储表示』 虽然顺序存储表示对完全二叉树是可以接受的,但是对于许多其他的二叉树,这种存储表示却浪费存储空间。且在树的中间插入删除结点可能需要移动大量的结点。使用链接式存储表示就可以容易地克服这些问题。在这种存储表示方法中,每个结点都有三个域:左儿子 left_child、数据 data 和右儿子 right_child。如下图。

5-10

二叉树的结点链接式存储表示

虽然这种结点结构难于确定结点的父亲,但它对于绝大多数的应用都是令人满意的。如果需要知道任意一个结点的父亲,只要在结点定义中增加第四个域(父亲 parent 域),就可以了。

results matching ""

    No results matching ""