树和二叉树的应用

本文主要介绍树和二叉树的应用，主要包含3个部分：二叉排序树、平衡二叉树和哈夫曼树和哈夫曼编码。

二叉排序树（BST）

定义

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

若左子树非空，则左子树上所有结点关键字的值均小于根结点的关键字值
若右子树非空，则右子树上所有结点关键字的值均大于根结点的关键字值
左、右子树本身也分别是一棵二叉排序树

查找

关于二叉排序的查找，在C语言实现七大查找算法（三）我的这篇博文中，已经详细介绍了，此处不再赘述。

查找效率：平均查找长度主要取决于树的高度。

二叉排序树和二分查找的对比

二叉排序树	二分查找（有序顺序表）
判定树	不唯一	唯一
有序性	无需移动结点，修改指针
插入、删除	$O (l o g_{2}^{n})$	$O (n)$
有序表静态		√
有序表动态	√

插入

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

由于二叉排序树是递归定义的，插入结点的过程如下：

若原二叉排序树为空，直接插入结点
若关键字 $k$ 小于根结点的关键字，插入到左子树中
若关键字 $k$ 大于根结点的关键字，插入到右子树中

一个插入示例如下（插入28，58），发现插入的新结点一定是某个叶子结点。

实现代码如下

int BST_InSert(BiTree &T,KeyType k){
    if(T==NULL){                                 //原树为空，新插入的记录为根结点
        T=(BiTree) malloc (sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else if(k==T->key)                          //树中存在相同关键字的结点
        return 0;
    else if(k<T->key)
        return BST_InSert(T->lchild,k);        //递归插入T的左子树中
    else
        return BST_InSert(T->rchild,k);       //递归插入T的右子树中
}

构造

void Creat_BST(BiTree &T,KeyType str[],int n){
    //用关键字数组str[]建立一个二叉排序树
    T=NULL;
    int i=0;
    while(i<n){
        BST_InSert(T,str[i]);
        i++;
    }
}

删除

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

删除操作实现过程按以下3种情况来处理：

若删除的结点z为叶子结点，直接删除
若结点 $z$ 只有一颗左子树或右子树，则让 $z$ 的子树成为 $z$ 父节点的子树，替代 $z$ 的位置
若 $z$ 有左右2棵子树，则令 $z$ 的直接后继（或直接前驱）替代 $z$ ，然后从 $B S T$ 中删去这个直接后继（或直接前驱），这样就转化为了第一种或第二种情况