基本数据结构 —— 二叉搜索树(C++实现)

c/c++

浏览数:51

2019-8-9


什么是二叉搜索树

二叉搜索树(英语:Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉搜索树。

二叉搜索树如何储存数值

如图所示:

所有的节点,都满足左子树上的所有节点都比自己的小,而右子树上的所有节点都比自己大这个条件。

二叉搜索树的操作

因为二叉搜索树的性质,二叉搜索树能够高效地进行如下操作:

  • 插入一个数值;
  • 查询是否包含某个数值;
  • 删除某个数值

如果共有n个元素,那么平均每次操作需要O(logn)的时间。
接下来用C++来实现以上操作。首先定义节点结构体如下:

node* insert(node* p,int x)
{
    if(!p)
    {
        auto q = new node(x);
        return q;
    }
    else
    {
        if(x < p->val) p->lch = insert(p->lch,x);
        else p->rch = insert(p->rch,x);
        return p;
    }
}

插入一个数值

如图所示:

node* insert(node* p,int x)
{
    if(!p) //空树
    {
        auto q = new node(x);
        return q;
    }
    else
    {
        if(x < p->val) p->lch = insert(p->lch,x);
        else p->rch = insert(p->rch,x);
        return p;
    }
}

查询是否包含某个数值

如图所示:

bool find(node* p,int x)
{
    if(!p) return false;
    if(x == p->val) return true;
    if(x < p->val) return find(p->lch,x);
    else return find(p->rch,x);
} 

删除某个数值

数值的删除比起之前提到的操作要稍微麻烦一些。例如,我们要删除数值15。如果删除了15所在的节点,那么它的两个儿子10和17就悬空了。于是,把11提到15所在的位置就可以解决问题。如图所示:

一般来说,需要根据下面几种情况分别进行处理:

  • 需要删除的节点没有左儿子,那么就把右儿子提上去。
  • 需要删除的节点的左儿子没有右儿子,那么就把左儿子提上去。
  • 以上两种情况都不满足的话,就把左儿子的子孙中最大的节点提到需要删除的节点上。
node* remove(node* p,int x)
{
    if(!p) return NULL;
    if(x < p->val) p->lch = remove(p->lch,x);
    else if(x > p->val) p->rch = remove(p->rch,x);
    else
    {
        if(p->lch == NULL) //需要删除的节点没有左儿子 
        {
            auto q = p->rch;
            delete p;
            return q;
        }
        else if(p->lch->rch == NULL) //需要删除的节点的左儿子没有右儿子 
        {
            auto q = p->lch;
            q->rch = p->rch;
            delete p;
            return q; 
        }
        else
        {
            auto q = p->lch;
            while(q->rch->rch != NULL) q = q->rch;
            auto r = q->rch;
            q->rch = r->lch;
            r->lch = p->lch;
            r->rch = p->rch;
            delete p;
            return r;
        }
        return p;
    }
}

测试代码

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

struct node{
    int val;
    node *lch,*rch;
    node(int value): val(value),lch(NULL),rch(NULL){ }
}; 
node* insert(node* p,int x)
{
    if(!p)
    {
        auto q = new node(x);
        return q;
    }
    else
    {
        if(x < p->val) p->lch = insert(p->lch,x);
        else p->rch = insert(p->rch,x);
        return p;
    }
}
bool find(node* p,int x)
{
    if(!p) return false;
    if(x == p->val) return true;
    if(x < p->val) return find(p->lch,x);
    else return find(p->rch,x);
} 
node* remove(node* p,int x)
{
    if(!p) return NULL;
    if(x < p->val) p->lch = remove(p->lch,x);
    else if(x > p->val) p->rch = remove(p->rch,x);
    else
    {
        if(p->lch == NULL) //需要删除的节点没有左儿子 
        {
            auto q = p->rch;
            delete p;
            return q;
        }
        else if(p->lch->rch == NULL) //需要删除的节点的左儿子没有右儿子 
        {
            auto q = p->lch;
            q->rch = p->rch;
            delete p;
            return q; 
        }
        else
        {
            auto q = p->lch;
            while(q->rch->rch != NULL) q = q->rch;
            auto r = q->rch;
            q->rch = r->lch;
            r->lch = p->lch;
            r->rch = p->rch;
            delete p;
            return r;
        }
        return p;
    }
}
void printTree(node* root)
{
    queue<node*> q;
    q.push(root);
    while(!q.empty())
    {
        auto p = q.front();q.pop();
        if(p)
        {
            cout << p->val << " ";
            q.push(p->lch);
            q.push(p->rch);
        } 
    }
    cout << endl;
}
int main() {
    node* root = insert(NULL,7);
    insert(root,2);
    insert(root,15);
    insert(root,1);
    insert(root,5);
    insert(root,10);
    insert(root,17);
    insert(root,4);
    insert(root,6);
    insert(root,8);
    insert(root,11);
    insert(root,16);
    insert(root,19);
    if(find(root,15)) cout << "find 15" << endl;
    else cout << "can not find 15" << endl;
    if(find(root,3)) cout << "find 3" << endl;
    else cout << "can not find 3" << endl;
    printTree(root);
    remove(root,15);
    printTree(root);
    return 0;
};

结果:

参考资料

作者:闽A2436