数据结构—造树计划—二叉搜索树
定义
struct node{
int val;
node *lch, *rch;
};
功能
插入
-
使命：值val
-
思路：若值小于当前结点的值，则该点移向该节点的左儿子树（
p->lch = insert(p->lch,x） -
情况：
- 到底了（到达目的地），直接创建一个新结点，并把左右子结点赋值为null，采用new的方式来创建。
- 直接一个点都没有（初始情况），按1处理
- 有结点，与该结点的值进行比较，来选择接触左儿子，还是右儿子。
-
疑点：
-
为什么函数需要以结点来作为返回值？为什么函数需要返回值。
-
个人理解：加入一个新的结点，是动了这棵树的整个的生态圈（其实是半个）。即便看似没有关系，但实际上是有关系的。就好像一个大伯突然多了一个重孙一样。
-
node *insert(node *p, int x)
{
if(p == NULL)
{
node *q = new node;
q->lch = NULL; //q本来就是一个指向结构体node的指针 ，再用来指东西不过分吧？
q->rch = NULL;
q->val = 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)
bool find(node* p,int x)
{
//Null是在计算中具有保留的值，用于指示指针不引用有效对象
if(p == NULL) return false;
else if(x == p->val)return true;
else if(x< p -> val) find(p->lch,x);
else find(p->rch,x);
}
删除
-
起初想想好像是挺简单的，但看看代码还是有点复杂的。
-
这个例子有点极端，如果要从这个世界上抹除一个毫无社会关系的人，那么对社会造成的影响是微乎其微的。而实际情况下，如果一个人要从这个社会上消失的话，往往就会涉及到遗产的分配，社会关系财产的转交等等。
-
所以删除一个结点也要考虑该结点与其他结点的社会关系，还要做好社会关系变更的工作（返回结点）。
-
比如要删去的结点的左儿子没有右儿子，可以让左儿子来继承要删去的结点的右儿子部分
-
情况：
-
删数的路上：
- 类似搜数
-
删数：
-
无左儿子
解决方案：右儿子上移，无家产继承
-
左儿子无右儿子
解决方案：左儿子上移，并继承家产
-
左儿子有右儿子
解决方案：找到该结点左子树部分的最大值（即先找做儿子，然后从这个左儿子一直往右下方找）
有点认子作父的感觉
-
查无此户。。
-
-
node * remove(node *p, int 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->rch=NULL)
{
node *new_p=p->rch;
delete p;
return new_p;
}
else if(p->lch->rch==NULL)
{
node *new_p=p->lch;
new_p->rch=p->rch;//继承家产
delete p;
return new_p;
}
else
{
node *new_p=p->lch;
while(new_p->rch->rch!=NULL)new_p=new_p->rch;//到最后一个点会保留一个右儿子，而这个右儿子是p结点左子树中最大的
node *answer_p=new_p->rch;
new_p->rch=answer_p->lch;//删除answer_p曾屈居点下的记录（左子结点上移）
answer_p->rch=p->rch;
answer_p->rch=p->lch;
delete p;
return answer_p;
}
//注意，搜寻的过程也要记得返回更新的结点
return p;
}
完整代码
#include<iostream>
using namespace std;
struct node{
int val;
node *lch, *rch;
};
node *insert(node *p, int x)
{
if(p == NULL)
{
node *q = new node;
q->lch = NULL; //q本来就是一个指向结构体node的指针 ，再用来指东西不过分吧？
q->rch = NULL;
q->val = 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)
{
//Null是在计算中具有保留的值，用于指示指针不引用有效对象
if(p == NULL) return false;
else if(x == p->val)return true;
else if(x< p -> val) find(p->lch,x);
else find(p->rch,x);
}
node * remove(node *p, int 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->rch=NULL)
{
node *new_p=p->rch;
delete p;
return new_p;
}
else if(p->lch->rch==NULL)
{
node *new_p=p->lch;
new_p->rch=p->rch;//继承家产
delete p;
return new_p;
}
else
{
node *new_p=p->lch;
while(new_p->rch->rch!=NULL)new_p=new_p->rch;//到最后一个点会保留一个右儿子，而这个右儿子是p结点左子树中最大的
node *answer_p=new_p->rch;
new_p->rch=answer_p->lch;//删除answer_p曾屈居点下的记录（左子结点上移）
answer_p->rch=p->rch;
answer_p->rch=p->lch;
delete p;
return answer_p;
}
//注意，搜寻的过程也要记得返回更新的结点
return p;
}
int main()
{
node *root = NULL;
root = insert(root,1);
find(root,1);
return 0;
}
其他
参考资料
- 挑战程序设计竞赛