- // 二叉搜索树的实现 //
- // 使用
- node *root = NULL;
- root = insert(root, 1);
- find(root, 1);
- // 实现
- struct node// 表示节点的结构体
- {
- int val;
- node *lch, *rch;
- };
- node *insert(node *p, int x)// 插入数值 x
- {
- if(p==NULL)
- {
- node *q = new node;
- q->val = x;
- q->lch = q->rch = NULL;
- return q;
- }
- else
- {
- if(x <q->val) p->lch = insert(p->lch, x);
- else p->rch = insert(p->rch, x);
- return p;
- }
- }
- bool find(node *p, int x)// 查找数值 x
- {
- if(p==NULL)
- return false;
- else if(x == p->val) return true;
- else if(x <p->val) return find(p->lch, x);
- else return find(p->rch, x);
- }
- node *remove(node *p, int x)// 删除数值 x
- {
- if(p==NULL) return NULL
- else 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)// 删除的节点没有左儿子
- {
- node *q = p->rch;
- delete p;
- return q;
- }
- else if(p->lch->rch == NULL)// 删除的节点的左儿子没有右儿子
- {
- node *q = p->lch;
- q->rch = p->rch;
- delete p;
- return q;
- }
- else// 以上两种情况都不满足的话, 就把左儿子的子孙中最大的节点提到需要删除的节点上
- {
- node *q;
- for(q = p->lch; q->rch->rch != NULL; q = q->rch);
- node *r = q->rch;
- q->rch = r->lch;
- r->lch = p->lch;
- r->rch = p->rch;
- delete p;
- return r;
- }
- return p;
- }
删除的最后一部分的代码相对较难理解, 得反复琢磨.
觉得有帮助的话不妨点个推荐呀!
来源: http://www.bubuko.com/infodetail-3006711.html