#include<iostream>
#include<cstdlib>
using namespace std;
/*查找二叉树，这里用的都是无敌的递归方法，因为它极容易理解，
也很容易编程，但值得注意的是返回值很重要*/ 
typedef struct TreeNode
{
int Element;
TreeNode *Left;
TreeNode *Right; 
}TreeNode,*MyTree;

MyTree MakeEmpty(MyTree &T);  //二叉树置空 
void InorderTraverse(const MyTree &T); //中序遍历 
MyTree Find(const MyTree &T,int X); //查找一个元素的位置 
MyTree FindMin(const MyTree &T);  //查找最小值 
MyTree FindMax(const MyTree &T);  //查找最大值 
MyTree Insert(MyTree &T,int X);   //插入 
MyTree Delete(MyTree &T,int X);   //删除 

int main()  //用于测试 
{
MyTree T=NULL,Temp=NULL;
MakeEmpty(T);

int i,a[10]={5,14,7,8,11,22,16,9,10,12};
for(i=0;i<10;i++)
Insert(T,a[i]);
cout <<"建立好了一个二叉树" <<endl ;
InorderTraverse(T); 
cout <<endl ; 

Delete(T,11);
cout <<"删除一次后" <<endl ;
InorderTraverse(T);
cout <<endl ; 

Temp=FindMin(T);
cout <<"最小的元素为" <<Temp->Element <<endl ;

Temp=FindMax(T);
cout <<"最大的元素为" <<Temp->Element <<endl ;

Temp=Find(T,12);
cout <<"查找12的位置,再根据这个位置输出它的值" <<Temp->Element <<endl ;

MakeEmpty(T);

return 0;
}

MyTree MakeEmpty(MyTree &T)  
{
if(T)
{
MakeEmpty(T->Left);  //置空左树 
MakeEmpty(T->Right); //置空右树 
delete T;            //释放根节点 
}
return NULL;
}

void InorderTraverse(const MyTree &T)
{
if(T)
{
InorderTraverse(T->Left);
cout <<T->Element <<' ' ;
InorderTraverse(T->Right);
}
}

MyTree Find(const MyTree &T,int X) 
{
if(T==NULL) return NULL ; 
if(T->Element>X) return Find(T->Left,X);  //X小，进入小于X的范围 
else if(T->Element<X) return Find(T->Right,X); //X大,进入大于X的范围 
else return T;   
}

MyTree FindMin(const MyTree &T)
{
if(T->Left) return FindMin(T->Left);
    else return T;
}

MyTree FindMax(const MyTree &T)
{
if(T->Right) return FindMax(T->Right);
else return T;
}

MyTree Insert(MyTree &T,int X) //插入 
{
if(T==NULL)     //如果根不存在 
{
T=new TreeNode;
if(T==NULL)
cout <<"空间不足插入失败! " <<endl ;
else
{
T->Element=X;
T->Left=T->Right=NULL;
} 
}
else if(X<T->Element) T->Left=Insert(T->Left,X); //如果X>根数值，那么插入右边 
else if(X>T->Element) T->Right=Insert(T->Right,X); //如果X<根数值，那么插入左边 
return T;  //don't forget
}

MyTree Delete(MyTree &T,int X)    //比较复杂的是删除操作，要分为两种情况考虑它 
{
MyTree Temp;
if(T==NULL) 
   cout<<"没有找到这个元素" <<endl ; 
else if(X<T->Element)  
    T->Left=Delete(T->Left,X);  
else if(X>T->Element) 
    T->Right=Delete(T->Right,X); 
else if(T->Left&&T->Right)       //情况一：被删除节点有两个子节点,找到右树最小值代替它，再删除右树最小值元素 
{
Temp=FindMin(T->Right);   
T->Element=Temp->Element; 
T->Right=Delete(T->Right,T->Element); 
}
else     //情况二：被删除的节点只有一个子或者没有节点,直接删除 
{
Temp=T;
if(T->Left==NULL) T=T->Right; 
else if(T->Right==NULL) T=T->Left;
delete Temp; 
}
return T; //it is important 
}