二叉搜索树实现

举报
兔老大 发表于 2021/04/20 01:12:07 2021/04/20
【摘要】 本文给出二叉搜索树介绍和实现   首先说它的性质:所有的节点都满足,左子树上所有的节点都比自己小,右边的都比自己大。   那这个结构有什么有用呢? 首先可以快速二分查找。还可以中序遍历得到升序序列,等等。。。 基本操作: 1、插入某个数值 2、查询是否包含某个数值 3、删除某个数值   根据实现不同,还可以实现其他很多种操作...

本文给出二叉搜索树介绍和实现

 

首先说它的性质:所有的节点都满足,左子树上所有的节点都比自己小,右边的都比自己大。

 

那这个结构有什么有用呢?

首先可以快速二分查找。还可以中序遍历得到升序序列,等等。。。

基本操作:

1、插入某个数值

2、查询是否包含某个数值

3、删除某个数值

 

根据实现不同,还可以实现其他很多种操作。

 

实现思路思路:

前两个操作很好想,就是不断比较,大了往左走,小了往右走。到空了插入,或者到空都没找到。

而删除稍微复杂一些,有下面这几种情况:

1、需要删除的节点没有左儿子,那就把右儿子提上去就好了。

2、需要删除的节点有左儿子,这个左儿子没有右儿子,那么就把左儿子提上去

3、以上都不满足,就把左儿子子孙中最大节点提上来。

 

当然,反过来也是成立的,比如右儿子子孙中最小的节点。

 

下面来叙述为什么可以这么做。

下图中A为待删除节点。

第一种情况:

 

1、去掉A,把c提上来,c也是小于x的没问题。

2、根据定义可知,x左边的所有点都小于它,把c提上来不影响规则。

 

第二种情况

 

3、B<A<C,所以B<C,根据刚才的叙述,B可以提上去,c可以放在b右边,不影响规则

4、同理

 

第三种情况

 

5、注意:是把黑色的提升上来,不是所谓的最右边的那个,因为当初向左拐了,他一定小。

因为黑色是最大,比B以及B所有的孩子都大,所以让B当左孩子没问题

而黑点小于A,也就小于c,所以可以让c当右孩子

大概证明就这样。。

下面我们用代码实现并通过注释理解

上次链表之类的用的c,循环来写的。这次就c++函数递归吧,不同方式练习。

定义


  
  1. struct node
  2. {
  3. int val;//数据
  4. node *lch,*rch;//左右孩子
  5. };

插入


  
  1. node *insert(node *p,int x)
  2. {
  3. if(p==NULL)//直到空就创建节点
  4. {
  5. node *q=new node;
  6. q->val=x;
  7. q->lch=q->rch=NULL;
  8. return p;
  9. }
  10. if(x<p->val)p->lch=insert(p->lch,x);
  11. else p->lch=insert(p->rch,x);
  12. return p;//依次返回自己,让上一个函数执行。
  13. }

查找


  
  1. bool find(node *p,int x)
  2. {
  3. if(p==NULL)return false;
  4. else if(x==p->val)return true;
  5. else if(x<p->val)return find(p->lch,x);
  6. else return find(p->rch,x);
  7. }

删除


  
  1. node *remove(node *p,int x)
  2. {
  3. if(p==NULL)return NULL;
  4. else if(x<p->val)p->lch=remove(p->lch,x);
  5. else if(x>p->val)p->lch=remove(p->rch,x);
  6. //以下为找到了之后
  7. else if(p->lch==NULL)//情况1
  8. {
  9. node *q=p->rch;
  10. delete p;
  11. return q;
  12. }
  13. else if(p->lch->rch)//情况2
  14. {
  15. node *q=p->lch;
  16. q->rch=p->rch;
  17. delete p;
  18. return q;
  19. }
  20. else
  21. {
  22. node *q;
  23. for(q=p->lch;q->rch->rch!=NULL;q=q->rch);//找到最大节点的前一个
  24. node *r=q->rch;//最大节点
  25. q->rch=r->lch;//最大节点左孩子提到最大节点位置
  26. r->lch=p->lch;//调整黑点左孩子为B
  27. r->rch=p->rch;//调整黑点右孩子为c
  28. delete p;//删除
  29. return r;//返回给父
  30. }
  31. return p;
  32. }

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/81741034

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。