C语言-二叉查找树(BST)

发布于 / 数据结构与算法 / Comments Off on C语言-二叉查找树(BST)

0x00、二叉查找树的递归定义

    二叉查找树(二叉搜索树、二叉排序树、排序二叉树、Binary Search Tree,BST)是一种特殊的二叉树。递归定义如下:

●若二叉查找树没有任何节点,则二叉查找树为空树

●若二叉查找树不是空树,则二叉查找树的左子树和右子树均为二叉树,而且左节点的数据域小于等于根节点右节点的数据域大于根节点。如下图

0x01、二叉查找树的查找操作(C语言实现)

    因为二叉查找树的左右节点与根节点的大小关系是固定的,所以查找起来不像普通二叉树一样,"盲目"的查找。

我们可以确定这样的一个思路。比如要寻找数字:n,根节点为root。

●如果root == NULL则查找失败,返回

●如果root->data == n则查找成功,输出

●如果root->data < n,说明要查找的数据比当前节点大,应该往右找

●如果root->data > n,说明要查找的数据比当前节点小,应该往左找

下面我们尝试使用C语言递归代码实现查找函数:

/**
  * 二叉查找树的递归查找方法
  * 传入根节点root和要查找的数据data
  */
void search(node* root, int data){
    if(root == NULL)return;    //查找失败
    if(root -> data == data)   //查找成功
        printf("%d", root -> data);
    if(root -> data > data)    //当前节点大,往左找
        search(node -> lchild, data);
    if(root -> data < data)    //当前节点小,往右找
        search(node -> rchild, data);
}

0x02、插入操作

二叉查找树是有顺序的,所以插入操作不可以像普通二叉树一样,"盲目"的插入,要根据顺序插入到正确的位置,我们按照下面的思路插入节点。比如根节点为root,要插入的数据为data

●如果root == null,这里就是应该插入的位置,让root=new node,并写入数据data

●如果root->data == data,那么说明数据已经存在了,返回

●如果root->data < data,说明数据比根节点大,往右搜索合适位置并插入

●如果root->data > data,说明数据比根节点小,往左搜索合适位置并插入

下面我们尝试使用C语言实现二叉查找树的插入过程:

void insert(node* &root, int data){
    if(root == NULL){    //节点为空,插入到当前节点
        root = new node;
        root->lchild = NULL, root->rchild = NULL;
        root->data = data;
        return;
    }
    if(root -> data == data) //数据已存在,无需插入
        return;
    else if(root -> data < data)//比节点数据大,往右插
        insert(root->rchild, data);
    else if(root -> data > data)//比节点数据小,往左插
        insert(root->lchild, data);
}

上面代码中,参数部分node* &root,这里加&是因为函数里面可能修改了root,如果不加&就不会真正修改。

0x03、二叉搜索树的中序遍历

二叉搜索树有个很实用的性质,由于二叉搜索树的特性:左子树<根节点<右子树,这和中序遍历的顺序是一样的,所以二叉搜索树的中序遍历序列就是一个有顺序的序列。

0x04、删除操作

我们依然拿这个二叉搜索树举例:

假如我现在想要删掉节点30,如果直接删除,把节点30给free掉,后果是二叉树被分成两部分,不再是一棵完整的二叉树,所以我们不可以直接删除节点。

这里定义两个定义:

在一个集合中,存在n属于这个集合。比n小的最大的数叫做n的前驱;比n大的最小的数叫做n的后继

例如上面的二叉搜索树,30的前驱是20;30的后继是40。


接着我们继续回归到我们之前的问题上,删除节点30。

由于二叉树中序遍历是有顺序的,所以我们有两种删除30的方法:

1,我们可以使用30的前驱:20,替换掉30,接着问题转化为删除子树20。删除20的时候我们用20的前驱:15,替换掉20的位置,这样就成功删除了30.

2,我们可以使用30的后继:40,替换掉30,接着问题转化为删除子树40。删除40的时候我们使用40的后继:50,替换掉40,这样就删除了40.

所以这仍然是一个递归问题!删除某个节点的时候使用后继或前驱替换掉节点,然后再以前驱或后继作为根节点删除下一级的前驱或后继,从而完成二叉搜索树删除节点。

下面我们先来实现查找根节点的前驱和后继。

查找前驱的时候也就是查找根节点左节点的最大值,我们只需要以左节点做为根节点,沿着右边遍历一遍即可。问题转化为找最大值,代码如下:

node* findMax(node* root){
    while(root->rchild != NULL)
        root = root->rchild;    //不断往右(大)
    return root;
}

同理,找最小值:

node* findMin(node* root){
    while(root->lchild != NULL)
        root = root->lchild;    //不断往右(大)
    return root;
}

下面来完成删除节点的完整的函数:

void deleteNode(node* &root, int data){
    if(root == NULL) return;    //不存在这个点
    if(root->data == data){    //找到了
        if(root->lchild == NULL && root->rchild == NULL)    //叶子节点直接删除
            root = NULL;    //删除
        else if(root->lchild != NULL){
            node* pre = findMax(root->lchild);    //在左子树中找到最大值,也就是root的前驱
            root->data = pre->data;    //使用前驱的数据覆盖掉根节点的数据
            deleteNode(root->lchild, pre->data);    //删掉前驱
                            //(因为前驱数据已经给了根节点。再保留前驱就重复了)
        }else if(root->rchild != NULL){
            node* next = findMin(root->rchild);    //右子树找最小值,也就是root的后继
            root->data = next->data;
            deleteNode(root->rchild, next->data);
        }
    }else if(root->data != data){    //这个点不是要删除点
        if(root->data > data)    //当前点大了。往左边瞅瞅
            deleteNode(root->lchild, data);
        if(root->data < data)    //当前点笑了,往右边瞅瞅
            deleteNode(root->rchild, data);
    }
}

转载原创文章请注明,转载自: 斐斐のBlog » C语言-二叉查找树(BST)
评论已关闭