树与二叉树的应用

二叉排序树（BST）

二叉排序树的定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左、右子树也分别是一棵二叉排序树。

根据二叉排序树的定义，左子树结点值 < 根结点值 < 右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树的查找

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。这显然是一个递归的过程。

二叉排序树的非递归查找算法，最坏空间复杂度 #card=math&code=O%281%29&id=jSeOz) ：

// 二叉排序树的结点
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;
// 在二叉排序树中查找值为 key 的结点
BSTNode *BST_Search(BSTree T, int key) {
    while (T != nullptr && key != T->key) {
        if (key < T->key) {
            T = T->lchild;  // 小于 在左子树上查找
        } else {
            T = T->rchild;  // 大于 在右子树上查找
        }
    }
    return T;
}

二叉排序树的递归查找算法实现，最坏空间复杂度 #card=math&code=O%28h%29&id=C3X9U) ：

BSTNode *BST_Search(BSTree T, int key) {
    if (T == nullptr) {
        return nullptr;  // 查找失败
    }
    if (key == T->key) {
        return T;  // 查找成功
    } else if (key < T->key) {
        return BST_Search(T->lchild, key);  // 在左子树中查找
    } else {
        return BST_Search(T->rchild, key);  // 在右子树中找
    }
}

二叉排序树的插入

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。

插入结点的过程如下：若原二叉排序树为空，则直接插入结点；否则，若关键字 key 小于根结点值，则插入到左子树，若关键字 key 大于根结点值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。

二叉排序树插入操作的算法描述如下：

// 在二叉排序树插入关键字为 k 的新结点（递归实现）
int BST_Insert(BSTree &T, int k) {
    if (T == nullptr) {  // 树为空，新插入的结点为根结点
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = nullptr;
        return 1;
    } else if (k == T->key) {  // 树中存在相同关键字结点。插入失败
        return 0;
    } else if (k < T->key) {  // 插入到T的左子树
        return BST_Insert(T->lchild, k);
    } else {  // 插入到T的右子树
        return BST_Insert(T->rchild, k);
    }
}

TODO 实现二叉排序树插入操作的非递归实现

二叉排序树的构造

构造二叉排序树的算法描述如下：

void Creat_BST(BSTree &T, int str[], int n) {
    T = nullptr;  // 初始时T为空树
    int i = 0;
    while (i < n) { // 依次将每个关键字插入到二叉排序树中
        BST_Insert(T, str[i]);
    }
}

二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按 3 种情况来处理：

1. 若被删除结点是叶结点，则直接删除，不会破坏二叉排序树的性质。
2. 若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
3. 若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

   二叉排序树的查找效率分析

   二叉排序树的查找效率，主要取决于树的高度。

若二叉排序树的左、右子树的高度之差的绝对值不超过 1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为 #card=math&code=O%28%5Clog_%7B2%7D%7Bn%7D%29&id=K9VBq) 。

若二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表），则其平均查找长度为 #card=math&code=O%28n%29&id=w7Tfw)。在最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数 。

从查找过程看，二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树上的查找和二分查找差不多。但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树，

平衡二叉树⭐

平衡二叉树的定义

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1， 将这样的二叉树称为平衡二叉树（Balanced Binary Tree），简称平衡树（ AVL 树）。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 -1、0 或 1。

因此，平衡二叉树可定义为或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。

// 平衡二叉树结点
typedef struct AVLNode {
    int key;
    int balance;
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

平衡二叉树的插入

二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

注意：每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列 4 种情况：

1. LL 平衡旋转（右单旋转）。由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。 将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。如下图所示，其中结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

1. RR 平衡旋转（左单旋转）。由于在结点 A 的右孩子（ R ）的右子树（ R ）。上插入了新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。将 A 的右孩子 B 向左，上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树。

1. LR 平衡旋转（先左后右双旋转）。由于在 A 的左孩子（L）的右子树（R）。上插入新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置。

1. RL 平衡旋转（先右后左双旋转）。由于在 A 的右孩子（R）的左子树（L）。上插入新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置。

假设关键字序列为 {15, 3, 7, 10, 9, 8}，通过该序列生成平衡二叉树的过程如下图所示。(d) 插入 7 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的右子树，故执行 LR 旋转，先左后右双旋转，调整后的结果如图 (e) 所示。图 (g) 插入 9 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的左子树，故执行 LL 旋转，右单旋转，调整后的结果如图 (h) 所示。图 (i) 插入 8 后导致不平衡，最小不平衡子树的根为 7，插入位置为其右孩子的左子树，故执行 RL 旋转，先右后左双旋转，调整后的结果如图 (j) 所示。

平衡二叉树的查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，与给定值进行比较的关键字个数不超过树的深度。假设以 表示深度为 的平衡树中含有的最少结点数。显然，有 ，并且有 。 可以证明，含有 个结点的平衡二叉树的最大深度为 #card=math&code=O%28%5Clog%7B2%7D%7Bn%7D%29&id=Oictb)，因此平衡二叉树的平均查找长度为 #card=math&code=O%28%5Clog_%7B2%7D%7Bn%7D%29&id=YV4Kv) 。

哈夫曼树和哈夫曼编码

哈夫曼树的定义

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权（如：表示结点的重要性）。

从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。

树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为 式中， 是第 个叶结点所带的权值， 是该叶结点到根结点的路径长度。

在含有 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

哈夫曼树的构造

给定 个权值分别为 的结点，构造哈夫曼树的算法描述如下：

1. 将这 个结点分别作为 棵仅含一个结点的二叉树，构成森林 。
2. 构造一个新结点，从 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从 中删除刚才选出的两棵树，同时将新得到的树加入 中。
4. 重复步骤 2 和 3，直至 中只剩下一棵树为止。

从上述构造过程中可以看出哈夫曼树具有如下特点：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了个结点（双分支结点），因此哈夫曼树的结点总数为 。
3. 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

   哈夫曼编码

   在数据通信中：

• 若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。
• 若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。

可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。举例:设计字符 A，B 和 C 对应的编码 0，101 和 100 是前缀编码。对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译为原码，再对余下的编码文件重复同样的解码操作。例如，码串 00101100 可被唯一地翻译为0，0，101 和 100。另举反例：如果再将字符 D 的编码设计为 00，此时 0 是 00 的前缀，那么这样的码串的前两位就无法唯一翻译。

由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。显然，所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为 0 表示“转向左孩子”，标记为 1 表示“转向右孩子”。

注意：0 和 1 究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且是最优的。