数据结构（34）二叉排序树_二叉排序树的构造过程

目录

1、二叉排序树（BST,Binary Sort Tree）定义

2、二叉排序树的查找

3、二叉排序树的插入

4、二叉排序树的构造

5、二叉排序树的删除

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

7、二叉排序树与二分排序对比

---

1、二叉排序树（BST,Binary Sort Tree）定义

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

1）若左子树非空，则左子树上所有结点的值均小于根节点的值。

2）若右子树非空，则右子树上所有结点的值均大于根节点的值。

3）左、右子树也分别是一棵二叉排序树。

根据二叉排序树的定义，左子树结点值<根节点值<右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。例如，图34-1所示的二叉排序树的中序遍历序列为123468。

          图34-1  二叉排序树

2、二叉排序树的查找

二叉排序树的查找是从根节点开始，沿某个分支逐层向下比较的过程（有没有感觉一股浓浓的二分法的气息迎面而来）。若二叉排序树非空，先将给定值与根节点的关键字比较，若相等，则查找成功；若不相等，如果小于根节点的关键字，则在根节点的左子树上查找。

二叉排序树的非递归查找算法：

BSTNode *BST_Search(BiTree T,ElemType key)
{
    while(T != NULL && key != T->data)
    {
        if(key < T->data)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

3、二叉排序树的插入

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

插入结点的过程如下：若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根节点值，则插入左子树，若关键字k大于根节点值，则插入右子树。插入的结点一定是一个新添加的叶节点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或者右孩子。如图34-1所示在一个二叉排序树中一次插入结点28和结点58，虚线表示的边是其查找路径。

                                   图34-1  向二叉排序树中插入结点

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

int BTSInsert(BiTree &T,DataType k)
{
    if(!T)
    {
        T = (BiTree)malloc(sizeof(BSTNode));
        T->data= k;
        T->lchild = NULL;
        T->rchild = NULL;
        return 1;
    } 
    Bitree p = T;   
    else if(k == T->data)
        return 0;
    else if(k < T->data)
        return BTSInsert(T->lchild,k);
    else if(k > T->data)
        return BTSInsert(T->rchild,k);
}

4、二叉排序树的构造

从一颗空树出发，一次输入元素，将他们插入到二叉排序树中合适的位置。设查找的关键字序列为{45,24,53,45,12,24}，则生成的二叉排序树如图34-2所示。

                                                             图34-2  二叉排序树的构造过程

算法实现我就不用写了吧，就是遍历关键字序列，每个关键字序列调用二叉排序树中插入操作算法。

5、二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上

摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会改变。

删除操作按3种情况来处理：

①若被删除结点z是叶节点，则直接删除，不会破坏二叉排序树的性质。

②若结点z只有一棵左子树或右子树，则让z的子树直接成为z父结点的子树，代替z的位置。

③若结点z有左右两棵子树：

1. 可以用右子树的最小元素
2. 或者左子树的最大元素来替代被删除的节点

                            

思考一个问题，就是删除这个78的时候，不止81可以符合占据原位置，65也可以，所以二叉排序树插入的位置变动是唯一的，删除就不一定了。所以同一个元素的一插一删会有可能改变原排序二叉树的形状，但是性质不会变。

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

二叉排序树的查找效率，主要取决于树的高度。若二叉排序树的左右子树高度之差不超过1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为O(log2(n))。若而二叉排序树是一个只有左（右）孩子的单支树（类似于有序的单链表），则其平均查找长度为O(n)。

在最坏的情况下，即构造二叉树的输入序列是有序的，则会形成一个倾斜的单枝树，此时二叉排序树的性能显著变坏，树的高度也等于元素个数n，如图34-3所示。

                                 图34-3 相同关键字组成的不同排序二叉树

7、二叉排序树与二分排序对比

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

就平均时间性能而言，二叉排序树上的查找和二分查找差不多。

就表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(lgn)，因此更有效。

二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。

当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，则应选择二叉排序树作为其存储结构。