数据结构—造树计划—二叉搜索树

定义

struct node{
	int val;
	node *lch, *rch;
};

功能

插入

使命：值val
思路：若值小于当前结点的值，则该点移向该节点的左儿子树（p->lch = insert(p->lch,x）
情况：
1. 到底了（到达目的地），直接创建一个新结点，并把左右子结点赋值为null，采用new的方式来创建。
2. 直接一个点都没有（初始情况），按1处理
3. 有结点，与该结点的值进行比较，来选择接触左儿子，还是右儿子。
疑点：
- 为什么函数需要以结点来作为返回值？为什么函数需要返回值。
- 个人理解：加入一个新的结点，是动了这棵树的整个的生态圈（其实是半个）。即便看似没有关系，但实际上是有关系的。就好像一个大伯突然多了一个重孙一样。

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;//返回上一层函数，回去作报告 
	}
}

寻找

寻找本身有点类似插入的操作。
与操作不同的是寻找只需找下去，向上层打报告的内容只需回答找得到还是找不到，因此函数返回的类型是布尔类型
情况：
1. 找到了
2. 找不到
3. 在找中
  1. 向左找
  2. 向右找

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);
}

删除

起初想想好像是挺简单的，但看看代码还是有点复杂的。
这个例子有点极端，如果要从这个世界上抹除一个毫无社会关系的人，那么对社会造成的影响是微乎其微的。而实际情况下，如果一个人要从这个社会上消失的话，往往就会涉及到遗产的分配，社会关系财产的转交等等。
所以删除一个结点也要考虑该结点与其他结点的社会关系，还要做好社会关系变更的工作（返回结点）。
比如要删去的结点的左儿子没有右儿子，可以让左儿子来继承要删去的结点的右儿子部分
情况：
1. 删数的路上：
  - 类似搜数
2. 删数：
  1. 无左儿子
    
    解决方案：右儿子上移，无家产继承
  2. 左儿子无右儿子
    
    解决方案：左儿子上移，并继承家产
  3. 左儿子有右儿子
    
    解决方案：找到该结点左子树部分的最大值（即先找做儿子，然后从这个左儿子一直往右下方找）
    
    有点认子作父的感觉
  4. 查无此户。。

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;
}

其他

参考资料

挑战程序设计竞赛