二叉搜索树（BinarySearchTree）相关操作（C++）

#include
#include
#include
#include
using namespace std;
typedef struct node
{
	int val;
	node* left;
	node* right;
}node;

node* Create(int val)
{
	node* temp=NULL;
	temp=(node*)malloc(sizeof(node));
	temp->val=val;
	temp->left=NULL;
	temp->right=NULL;
	return temp;
}

void Insert(int val,node** proot)
{
	if(*proot==NULL)
	{
		*proot=Create(val);
	}
	else if((*proot)->val>=val)
	{
		Insert(val,&((*proot)->left));
	}
	else
	{
		Insert(val,&((*proot)->right));
	}
	return;
}

node* Search(int val,node* root)
{
	if(root==NULL)return NULL;
	if(root->val==val)return root;
	if(root->valright);
	if(root->val>val)return Search(val,root->left);
}

int FindminIteration(node* root)//迭代法寻找最小值 ，返回整型 
{
	if(root==NULL)
	{
		printf("Error:Empty Treen");
		return -1;
	}
	while(root->left)
	{
		root=root->left;
	}
	return root->val;
}

int FindminRecursion(node* root)//递归法寻找最小值 ，返回整型 
{
	if(root==NULL)
	{
		printf("Error:Empty Treen");
		return -1;		
	}
	if(root->left==NULL)
	{
		return root->val;
	}
	return FindminRecursion(root->left);
}

node* Findmin(node* root)//递归法寻找最小值 ，返回地址 
{
	if(root==NULL)
	{
		//printf("Error:Empty Treen");
		return NULL;		
	}
	if(root->left==NULL)
	{
		return root;
	}
	return Findmin(root->left);
}

int FindHeight(node* root)
{
	int lefth,righth;
	if(root==NULL)return -1;
	lefth=FindHeight(root->left);
	righth=FindHeight(root->right);
	return (lefth>righth?lefth:righth)+1;
}

void LevelOrder(node *root)//层次序遍历二叉树（广度优先） 
{
	if(root==NULL)return;
	queue Q;
	Q.push(root);
	while(!Q.empty())
	{
		node* current=Q.front();
		printf("%d ",current->val);
		if(current->left!=NULL)Q.push(current->left);
		if(current->right!=NULL)Q.push(current->right);
		Q.pop();
	}
}

void Preorder(node* root)//前序遍历 
{
	if(root==NULL)return;
	printf("%d ",root->val);
	Preorder(root->left);
	Preorder(root->right);
} 

void Inorder(node* root)
{
	if(root==NULL)return;
	Inorder(root->left);	
	printf("%d ",root->val);
	Inorder(root->right);	
}

void Postorder(node* root)
{
	if(root==NULL)return;
	Postorder(root->left);
	Postorder(root->right);
	printf("%d ",root->val); 
}

bool IsBstUtil(node* root,int min,int max)
{
	if(root==NULL)return true;
	if(root->valval>max
	&&IsBstUtil(root->left,min,root->val)
	&&IsBstUtil(root->right,root->val,max))
	return true;
	else return false;
}

bool IsBinarySearchTree(node* root)
{
	return IsBstUtil(root,INT_MIN,INT_MAX);
}

node* Delete(node* root,int val)
{
	if(root==NULL)return root;
	else if(valval)root->left=Delete(root->left,val);
	else if(val>root->val)root->right=Delete(root->right,val);
	else
	{
		if(root->left==NULL&&root->right==NULL)//No child 
		{
			delete root;
			root=NULL;
		}
		//One child
		else if(root->left==NULL)
		{
			node* temp=root;
			root=root->right;
			delete temp;
		}
		else if(root->right==NULL)
		{
			node* temp=root;
			root=root->left;
			delete temp;
		}
		else//Two children
		{
			node* temp=Findmin(root->right);
			root->val=temp->val;
			root->right=Delete(root->right,temp->val);
		}
	}
	return root;
}

node* Getsuccessor(node* root,int data)
{
	node* current=Search(val,root);
	if(current==NULL)return NULL;
	
	//Case 1:Node has right subtree
	if(current->right!=NULL)
	{
		return Findmin(current->right);
	}
	//Case 2:No right subtree
	else
	{
		node* successor=NULL;
		node* ancestor=root;
		while(ancestor!=current)
		{
			if(current->datadata)
			{
				successor=ancestor;
				ancestor=ancestor->left;
			}
			else ancestor=ancestor->right;
		}
		return succestor;
	} 
}

int main()
{
	node* root=NULL;
	node** proot=&root;
	Insert(10,proot);
	Insert(20,proot);
	Insert(50,proot);
	Insert(5,proot);
	Insert(40,proot);	
//	if(Search(50,*proot))printf("YESn");
//	if(Search(55,*proot))printf("YESn");
	printf("MinValue1 is %dn",FindminIteration(root));
	printf("MinValue1 is %dn",FindminRecursion(root));
	printf("Height of tree is %dn",FindHeight(root));
	LevelOrder(root); 
	return 0;
}