二叉查找树 - ONESRC

二叉树查找二叉排序树

二叉查找树（英语：Binary Search Tree），也称为有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若根节点左子树非空，则左子树上所有节点关键字均小于根节点关键字
若根节点右子树非空，则右子树上所有节点关键字均大于根节点关键字
根节点的左右子树本身又各是一棵二叉排序树

注：在某些非严格定义下，以上情况均可以取等号

树的建立：

二叉查找树的建立过程本质上可以看作向一棵空树里插入确定数量个节点。

插入节点：

考虑到二叉查找树的性质，可以采用递归实现。如果节点为空，则新建节点存入要插入的数据，并用该节点取代原有空位置。如果要插入的数据小于该节点数据，则递归左子树，否则递归右子树。

查找节点：

这里依旧采用递归实现，递归过程同上。

删除节点：

节点的删除，仍需要保证删去节点后，剩余节点构成的二叉树仍然是一棵二叉排序树。

删除节点前，仍需要上述思路找到节点。找到要删除的节点（假设为bt）后分为以下五种情况：

左右子树均为空

bt为叶子节点。最简单的情况，直接删去该节点即可。

左子树为空

bt只有右子树。直接将右子树替代bt，其余部分不变。

右子树为空

bt只有左子树。直接将左子树替代bt，其余部分不变。

左右子树均不为空，且bt的左子树的右子树为空

取左子树tmp，以其取代bt。再将tmp的左子树添加到bt的左子树上。

               7
       5               #
   2       6       #       #
 1
//删除节点5
-----------------------------------
       7
   2       #
 1   6

-----------------------------------

左右子树均不为空，且bt的左子树的的右子树不为空

取左子树最大节点tmp（该节点右子树一定为空），以其取代bt。再将tmp的左子树添加到tmp的原有位置上。

               7
       5               #
   2       6       #       #
 1   4   #   #   #   #   #   #
# # 3//删除节点5
-----------------------------------
               7
       4               #
   2       6       #       #
 1   3

-----------------------------------

性能分析

最坏情况下，当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树(链表），树的深度为n，其平均查找长度为 (n+1)/2

最好的情况是二叉查找树的形态和折半查找的判定树相同，其平均查找长度为O(log_2(N))

代码示例：

cpp中引用传递使用起来比较方便,故采用cpp实现。另外，printT中的相关变量及函数来自 : 如何优雅地打印二叉树，下列代码不再给出打印函数的具体实现。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int data;
    struct Node *l, *r;
}Node;

void printT(Node* root){
    for (int i = 0; i < MAXCOUNT;i++){
        nodeList[i] = NULL;
    }
    nodeNum = 0;
    toList(root, 1);
    printBinTree(nodeList, 1, nodeNum);
}

void insertBST(Node *&bt,int k){
    if(bt==NULL){
        bt = (Node *)malloc(sizeof(Node));
        bt->data = k;
        bt->l = bt->r = NULL;
    }else if(k<bt->data){
        insertBST(bt->l, k);
    }else{
       insertBST(bt->r, k);
    }
}

Node * createBST(int R[],int n){
    Node * bt = NULL;
    int i;
    for (i = 0; i < n;i++){
        insertBST(bt, R[i]);
    }
    return bt;
}

Node * searchBST(Node * bt,int k){
    if(bt==NULL||bt->data==k){
        return bt;
    }else if(k<bt->data){
        return searchBST(bt->l, k);
    }else{
        return searchBST(bt->r, k);
    }
}

void deleteBST(Node * &bt ,int k){
    if(bt==NULL)
        return;
    if(k==bt->data){
        Node *pre,*tmp;
        if(bt->r==NULL){
            pre = bt;
            bt = bt->l;
            free(pre);
        }else if(bt->l==NULL){
            pre = bt;
            bt = bt->r;
            free(pre);
        }else{
            pre = bt;
            tmp = bt->l;
            while (tmp->r!=NULL) {
                pre = tmp;
                tmp = tmp->r;
            } // 找到左子树中最大的元素s
            bt->data = tmp->data;  //替代被删节点
            if (pre != bt)
                pre->r = tmp->l; 
            else//pre==bt
                pre->l = tmp->l;
            free(tmp);
        }
    }else if(k<bt->data){
        deleteBST(bt->l, k);
    }else{
        deleteBST(bt->r, k);
    }
}

int main(void){
    int a[] = {3, 2, 8, 1, 5, 9, 4};
    Node *root = createBST(a, 7);
    printT(root);
    deleteBST(root, 5);
    printT(root);
}

实例输出:

               3
       2               8
   1       #       5       9
 #   #   #   #   4

-----------------------------------
       3
   2       8
 1   #   4   9

-----------------------------------

本文由 ukuq 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 19, 2019 at 05:20 pm