请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

数据结构---二叉搜索树

[复制链接]
查看: 81|回复: 0

2万

主题

3万

帖子

8万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
85202
发表于 2020-2-6 16:18 | 显示全部楼层 |阅读模式
  1.   1 #include   2 #include   3   4 using namespace std;  5   6 struct node  7 {  8     int val;  9     node *lch,*rch; 10 }; 11  12 node *insert(node *p,int x) 13 { 14     if(p==NULL) 15     { 16         // 申请一个新内存空间 17         node *q=new node; 18         q->val=x; 19         q->lch=q->rch=NULL; 20         return q; 21     } 22     else 23     { 24         if(xval) 25         { 26             p->lch=insert(p->lch,x); 27         } 28         else 29         { 30             p->rch=insert(p->rch,x); 31         } 32         return p; 33     } 34 } 35  36 bool find(node *p,int x) 37 { 38     if(p==NULL) 39     { 40         return false; 41     } 42     else if(x==p->val) 43     { 44         return true; 45     } 46     else if(xval) 47     { 48         return find(p->lch,x); 49     } 50     else 51     { 52         return find(p->rch,x); 53     } 54 } 55  56  57 // 删除数值x 58 // 需要删除的节点没有左儿子,右儿子提上去 59 // 需要删除的节点左儿子没有右儿子,左儿子提上去 60 // 以上两种都不满足,把左儿子中最大的节点提上去 61 node *remove(node *p,int x) 62 { 63     if(p==NULL) 64     { 65         return NULL; 66     } 67     else if(xval) 68     { 69         p->lch=remove(p->lch,x); 70     } 71     else if(xval) 72     { 73         p->rch=remove(p->rch,x); 74     } 75     // 假如没有左子节点,右儿子提上去 76     else if(p->lch==NULL) 77     { 78         node *q=p->rch; 79         delete p; 80         return q; 81     } 82     // 有左儿子,可是左儿子没有右儿子 83     else if(p->lch->rch==NULL) 84     { 85         // q为左儿子 86         node *q=p->rch; 87         q->rch=p->rch; 88         delete p; 89         return q; 90     } 91     // 否则,只需把左儿子的最大节点提上去 92     else 93     { 94         // q为p左子树中最大节点的父节点 95         // 记录父节点,方便以后实现 96         node *q; 97         for(q=p->lch;q->rch->rch!=NULL;q=q->rch); 98         // 由于只是将最大节点提到要删除的p节点的位置 99         // 而最大的节点大要右左子树节点,是以考虑q的左子树节点100 101         // r才是要删除节点p左子树的最大节点,要提到p的位置102         node *r=q->rch;103         // r必定没有左子节点,为第一种情况,要将右儿子提上去104         q->rch=r->lch;105 106         // 末端将最大节点提上去,并删除p节点(不能提早删除,需要将关系传毒过去,末端删除)107         r->lch=p->lch;108         r->rch=p->rch;109 110         delete p;111         return r;112     }113     // 假如当前还未找到要删除节点,返回当前节点,保证连续关系114     return p;115 }116 117 int main()118 {119     node *root=NULL;120     root=insert(root,1);121     find(root,1);122     return 0;123 }
复制代码


免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 妈妈网-中国妈妈第一,是怀孕、育儿、健康等知识交流传播首选平台 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表