首页 > > 程序设计 > C/C++ >

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

2020-02-06 16:01:28来源：博客园阅读 ()

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

  1 #include <cstdio>
  2 #include <iostream>
  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(x<p->val)
 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(x<p->val)
 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(x<p->val)
 68     {
 69         p->lch=remove(p->lch,x);
 70     }
 71     else if(x<p->val)
 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 }