二叉搜索树的增删查

     今天把搜索二叉树的思路又理了一遍，把代码又从头到尾敲了一遍，各位看客就不要在意代码粗糙和内存溢出了，主要把插入和删除的过程理了一遍，其中比较复杂的地方就是搜索二叉树的删除，涉及了很多次的指针重新指向，比较容易晕。另外，对于二叉树，在上溯的时候要特别注意根节点这个特殊的临界状态（大部分情况把根节点的父结点指向空，也可以设一个head结点，使root和head的父结点相互指向）。最后注意null结点不能取左右孩子和父结点，这也是一个容易使程序崩的情况。代码如下：

//二叉搜索树的插入和删除
struct SerachTree
{
	int data;
	SerachTree *left_child;
	SerachTree *right_child;
	SerachTree *parent_node;
};

class Serach_Tree
{
public:
	Serach_Tree()
	{
		root=NULL;
	}
	//插入
	SerachTree* insert(int number)
	{
		if(root==NULL)
		{
			root=new SerachTree;
			root->data=number;
			root->left_child=NULL;
			root->right_child=NULL;
			root->parent_node=NULL;
		}
		else
		{
			SerachTree *tem_root=root;
			SerachTree *tem=NULL;
			while(tem_root!=NULL)
			{
				tem=tem_root;
				if(number<tem_root->data)
					tem_root=tem_root->left_child;
				else
					tem_root=tem_root->right_child;
			}
			SerachTree *child=new SerachTree;
			child->data=number;
			child->left_child=NULL;
			child->right_child=NULL;
			if(number<tem->data)
			{
				tem->left_child=child;
				child->parent_node=tem;
			}
			else
			{
				tem->right_child=child;
				child->parent_node=tem;
			}
		}
		return root;
	}
	//最小值
	int minimum(SerachTree *root)
	{
		if(root==NULL)
			return NULL;
		while(root->left_child!=NULL)
			root=root->left_child;
		return root->data;
	}
	//最大值
	int maximum(SerachTree *root)
	{
		if(root==NULL)
			return NULL;
		while(root->right_child!=NULL)
			root=root->right_child;
		return root->data;
	}
	//查找指定的值，找到返回该值，找不到就返回空
	int search(SerachTree *root,int num)
	{
		if(root==NULL)
			return NULL;
		if(root->data==num)
		{
			return num;
		}
		else
		{
			if(num<root->data)
				search(root->left_child,num);
			else
				search(root->right_child,num);
		}
		return num;
	}
	//找一个结点的前驱结点
	int front_node(int num)
	{
		if(search(root,num)==NULL)
		{
			cout<<"no that node!"<<endl;
			return NULL;
		}
		else
		{
			SerachTree *tem=root;
			//肯定能找到
			while(true)
			{
				if(tem->data>num)
					tem=tem->left_child;
				else if(tem->data<num)
					tem=tem->right_child;
				else
					break;
			}
			//找前驱结点
			if(tem->left_child!=NULL)
				return maximum(tem->left_child);
			SerachTree *tem_parent=tem->parent_node;
			while(tem_parent!=NULL&&tem==tem_parent->left_child)
			{
				tem=tem_parent;
				tem_parent=tem_parent->parent_node;
			}
			if(tem_parent==NULL)
				return NULL;
			else
				return tem_parent->data;
		}
	}
	//找后继结点
	int back_node(int num)
	{
		if(search(root,num)==NULL)
		{
			cout<<"no node"<<endl;
			return NULL;
		}
		else
		{
			SerachTree *tem=root;
			//肯定能找到
			while(true)
			{
				if(tem->data>num)
					tem=tem->left_child;
				else if(tem->data<num)
					tem=tem->right_child;
				else
					break;
			}
			if(tem->right_child!=NULL)
				return minimum(tem->right_child);
			SerachTree *tem_root=tem->parent_node;
			while(tem_root!=NULL&&tem==tem_root->right_child)
			{
				tem=tem_root;
				tem_root=tem_root->parent_node;
			}
			if(tem_root==NULL)
				return NULL;
			else
				return tem_root->data;
		}
	}
	//删除结点
	void delete_node(int num)
	{
		if(search(root,num)==NULL)
		{
			cout<<"delete error!"<<endl;
			return;
		}
		else
		{
			SerachTree *tem_root=root;
			while(true)
			{
				if(tem_root->data<num)
				{
					tem_root=tem_root->right_child;
				}
				else if(tem_root->data>num)
				{
					tem_root=tem_root->left_child;
				}
				else
					break;
			}
			//tem是待删除的结点
			if(tem_root->left_child==NULL) //没有左孩子，直接右孩子顶上
				_delete_node(tem_root,tem_root->right_child);

			else if(tem_root->right_child==NULL) //没有右孩子，直接左孩子顶上
				_delete_node(tem_root,tem_root->left_child);
			else  //左右孩子不为空
			{
				//先找到右子数最小的结点
				SerachTree *tem=tem_root->right_child;
				while(tem->left_child!=NULL)
				{
					tem=tem->left_child;
				}
				if(tem->parent_node!=tem_root)  //找到的点不是与待删除的点直接相连
				{
					_delete_node(tem,tem->right_child);
					tem->right_child=tem_root->right_child;
					tem->right_child->parent_node=tem;
				}
				_delete_node(tem_root,tem);
				tem->left_child=tem_root->left_child;
				tem->left_child->parent_node=tem;
			}
			cout<<"delete success"<<endl;
		}
	}
private:
	void _delete_node(SerachTree *root1,SerachTree *root2)
	{
		if(root1->parent_node==NULL)  //当前结点是根节点
		{
			root=root2;
		}
		else if(root1==root1->parent_node->left_child) //当前结点是父结点的左孩子
		{
			root1->parent_node->left_child=root2;
		}
		else if(root1=root1->parent_node->right_child)
		{
			root1->parent_node->right_child=root2;
		}
		if(root2!=NULL)
			root2->parent_node=root1->parent_node;
	}
public:
	SerachTree *root;
};

int main()
{
	Serach_Tree s;
	int choose;
	while(true)
	{
		cout<<"1：插入  2：max  3:min  4:serach  5:delete  0:exit"<<endl;
		cin>>choose;
		if(choose==1)
		{
			int num;
			cout<<"insert num:";
			cin>>num;
			s.insert(num);
		}
		if(choose==2)
		{
			if(s.maximum(s.root)!=NULL)
				cout<<s.maximum(s.root)<<endl;
			else
				cout<<"no node"<<endl;
		}
		if(choose==3)
		{
			if(s.minimum(s.root)!=NULL)
				cout<<s.minimum(s.root)<<endl;
			else
				cout<<"no node"<<endl;
		}
		if(choose==4)
		{
			int num=0;
			cout<<"search num:";
			cin>>num;
			if(s.search(s.root,num)!=NULL)
				cout<<s.search(s.root,num)<<endl;
			else
				cout<<"no node"<<endl;
		}
		if(choose==5)
		{
			int num=0;
			cout<<"delete num:";
			cin>>num;
			s.delete_node(num);
		}
		if(choose==0)
			break;
	}
	return 0;
}