数据结构：（代码篇:004）二叉搜索树 BST（二叉查找树）的基本操作

1.基本概念

二叉搜索树：是二叉树是真子集，要求：根节点大于或等于左子树的节点值，小于右子树的节点值。

他的中序遍历是有序的。

基本操作有：查找、插入、删除、建树。

查找和插入以及建树都很简单，和二叉树的差不多。删除略微复杂。

2.存储结构

struct node{
	int data;
	node* lchild;
	node* rchild;
};

3.查找

void search(node* root,int v){
	if(root==NULL){
		cout<<"search failed!"<<endl;
		return ;
	}
	if(root->data==v){
		cout<<"search success!"<<root->data<<endl;
	    return ;
	}
	else
	if(root->data>v){
		search(root->lchild,v);
	}
	else
	if(root->data<v){
		search(root->rchild,v);
	}
}

4.插入

新生成节点：

node* newnode(int v){
	node* t1=new node;
	t1->data=v;
	t1->lchild=t1->rchild=NULL;
	return t1;
}

void insert(node* &root,int v){
	if(root==NULL){
		root=newnode(v);
		return ;
	}
	if(root->data>=v){
		insert(root->lchild,v);
	}
	else
	if(root->data<v){
		insert(root->rchild,v);
	}
}

5.建树

node* create(int data[],int len){
	node* root=NULL;
	int i,j;
	for(i=0;i<len;i++)
	{
		insert(root,data[i]);
	}
	return root;
}

6.删除（重头戏！）

删除二叉搜索树中的某一个节点后，要保持其性质不变：左子树<=root<右子树

还需要了解一个节点的前驱和后继：

前驱：

当前节点左子树中最大的节点（但是小于或等于当前节点），也就是左子树中的最右节点

node* findMax(node* root){      // 找到左子树中最大的节点 
	while(root->rchild!=NULL){
		root=root->rchild;
	}
	return root;
} 

后继：

当前节点右子树中最小的节点（但是大于当前节点），也就是右子树中的最左节点

node* findMin(node* root){     // 找到右子树中最小的节点 
	while(root->lchild!=NULL){
		root=root->lchild;
	}
	return root;
}

分情况讨论：

  （1） 要删除的节点值在树中不存在（为NULL） ，直接返回。

  （2） 要删除的节点值等于当前访问的节点值

             a. 如果当前访问的节点没有任何子树，则直接把当前节点设为NULL

             b. 如果当前访问过的节点有左子树，则需要找到当前节点的前驱（即左子树里最大的节点值），用前驱的值覆盖

            当前节点的值，然后在左子树里删除其前驱。

             c. 如果当前访问过的节点有右子树，则需要找到当前节点的后继（即右子树里最小的节点值），用后继的值覆盖

            当前节点的值，然后在右子树里删除其后继。

   （3）要删除的节点值小于当前访问的节点值 ，则递归删除其左子树

   （4）要删除的节点值大于当前访问的节点值 ，则递归删除其右子树

void Delete(node* &root,int v){
	if(root==NULL){
		return ;
	}
	if(root->data==v){
		if(root->lchild==NULL&&root->rchild==NULL){
			root=NULL;
		}
		else
		if(root->lchild!=NULL){
			node* pre=findMax(root->lchild);
			root->data=pre->data;
			Delete(root->lchild,pre->data);
		}
		else
		if(root->rchild!=NULL){
			node* next=findMin(root->rchild);
			root->data=next->data;
			Delete(root->rchild,next->data);
		}
	}
	else
	if(root->data>v){
		Delete(root->lchild,v);
	}
	else
	if(root->data<v){
		Delete(root->rchild,v);
	}
}

7.完整的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define range 100
#define NULL 0
struct node{
	int data;
	node* lchild;
	node* rchild;
};
node* newnode(int v){
	node* t1=new node;
	t1->data=v;
	t1->lchild=t1->rchild=NULL;
	return t1;
}
void search(node* root,int v){
	if(root==NULL){
		cout<<"search failed!"<<endl;
		return ;
	}
	if(root->data==v){
		cout<<"search success!"<<root->data<<endl;
	    return ;
	}
	else
	if(root->data>v){
		search(root->lchild,v);
	}
	else
	if(root->data<v){
		search(root->rchild,v);
	}
}
void insert(node* &root,int v){
	if(root==NULL){
		root=newnode(v);
		return ;
	}
	if(root->data>=v){
		insert(root->lchild,v);
	}
	else
	if(root->data<v){
		insert(root->rchild,v);
	}
}
node* create(int data[],int len){
	node* root=NULL;
	int i,j;
	for(i=0;i<len;i++)
	{
		insert(root,data[i]);
	}
	return root;
}
node* findMax(node* root){      // 找到左子树中最大的节点 
	while(root->rchild!=NULL){
		root=root->rchild;
	}
	return root;
} 
node* findMin(node* root){     // 找到右子树中最小的节点 
	while(root->lchild!=NULL){
		root=root->lchild;
	}
	return root;
}
void Delete(node* &root,int v){
	if(root==NULL){
		return ;
	}
	if(root->data==v){
		if(root->lchild==NULL&&root->rchild==NULL){
			root=NULL;
		}
		else
		if(root->lchild!=NULL){
			node* pre=findMax(root->lchild);
			root->data=pre->data;
			Delete(root->lchild,pre->data);
		}
		else
		if(root->rchild!=NULL){
			node* next=findMin(root->rchild);
			root->data=next->data;
			Delete(root->rchild,next->data);
		}
	}
	else
	if(root->data>v){
		Delete(root->lchild,v);
	}
	else
	if(root->data<v){
		Delete(root->rchild,v);
	}
}
void preorder(node* root){
	if(root==NULL){
		return ;
	}
	cout<<root->data<<" ";
	preorder(root->lchild);
	preorder(root->rchild);
}
void inorder(node* root){
	if(root==NULL){
		return ;
	}
	inorder(root->lchild);
	cout<<root->data<<" ";
	inorder(root->rchild);
}
void postorder(node* root){
	if(root==NULL){
		return ;
	}
	postorder(root->lchild);
	postorder(root->rchild);
	cout<<root->data<<" ";
}
void layerorder(node* root){
	queue<node*> s;
	s.push(root);
	node* t=NULL; 
	while(!s.empty()){
		t=s.front();
		s.pop();
		cout<<t->data<<" ";
		if(t->lchild!=NULL)
		s.push(t->lchild);
		if(t->rchild!=NULL)
		s.push(t->rchild);
	}
}
int main(){
	int i,j,k,t,n;
	int data[10];
	node* root=NULL;
	cout<<"请输入节点个数:"<<endl;
	cin>>n;
	cout<<"请输入节点值:";
	for(i=0;i<n;i++)
	cin>>data[i];
	cout<<endl;
	root=create(data,n);
	cout<<"中序遍历:";
	inorder(root);
	cout<<"请输入查找的值:";
	cin>>n;
	search(root,n);
	cout<<"请输入删除的值:";
	cin>>n;
	Delete(root,n); 
	cout<<"中序遍历:";
	inorder(root);
	cout<<endl;
	cout<<"先序遍历:";
	preorder(root);
	cout<<endl;
	cout<<"后序遍历:"; 
	postorder(root);
	cout<<endl;
	cout<<"层序遍历:";
	layerorder(root);
	cout<<endl; 
	return 0;
}

代码的力量使我兴奋！

如有错，请指出。新年快乐(*^__^*) 嘻嘻……