#include<stdio.h>
#include<stdlib.h>


typedef int ElementType;
struct TreeNode
{
ElementType Element;
struct TreeNode *Left;
struct TreeNode *Right;
};
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;


SearchTree MakeEmpty(SearchTree T); //創(chuàng)建空樹?
Position Find (ElementType X,SearchTree T); //查找X?
Position FindMin(SearchTree T); //查找樹的的最小值?
Position FindMax(SearchTree T); //查找樹的最大值?
SearchTree Insert(ElementType X,SearchTree T); //插入X?
SearchTree Delete(ElementType X,SearchTree T); //刪除X?
ElementType Retrieve(Position P);
void Traveral_Q (SearchTree T); //前序遍歷?
void Traveral_Z (SearchTree T); //中序遍歷?
void Traveral_H (SearchTree T); // 后序遍歷?
void Print(Position P); //打印P結(jié)點(diǎn)的值?


int main(void)
{
SearchTree T = NULL;
int M;?
int a[5] = {2,8,6,5,3};
int i;
Position P;
ElementType ele;

MakeEmpty(T);
T = Insert(6,T); //注意前面一定要加T = ，不然會(huì)崩潰, 因?yàn)閭魅氲氖荰的復(fù)制品?

for( i =0; i < 5; i++)
Insert(a[i],T); //后面可以不加，因?yàn)榧恿说扔?，T = T，和不加一樣




//但是第一次要加，因?yàn)椴患拥脑?，T 一直為NULL。?
Traveral_Z(T);
// Delete(99,T);

// Print(FindMax(T));

return 0;
}




SearchTree MakeEmpty(SearchTree T)
{
if(NULL != T)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}

return NULL;
}
Position Find (ElementType X,SearchTree T)
{
if(NULL == T)
return NULL;

if(X < T->Element)
return Find(X,T->Left);
else?
if( X > T->Element)
return Find(X,T->Right);
else?
return T;
}






Position FindMin(SearchTree T) //使用尾遞歸也可以下面的方式?
{
if(NULL == T)
return NULL;
else?
if(NULL == T->Left)
return T;
else?
return FindMin(T->Left);

}
Position FindMax(SearchTree T) //使用循環(huán)，因?yàn)閭魅氲氖?T的復(fù)制，所以不會(huì)改變T?
{
if( NULL != T)
{
while(NULL != T->Right)
T = T->Right;
}
return T;
}


SearchTree Insert(ElementType X,SearchTree T) //插入X?
{

if(NULL == T)
{
T = (SearchTree)malloc(sizeof(struct TreeNode));
if( NULL == T)
printf("Out of Space\n");
else?
{
T->Element = X;
T->Left = T->Right = NULL;
}
}
else?
if( X < T->Element) //沒(méi)有考慮存在X的情況?
T->Left = Insert(X,T->Left);
else?
if(X > T->Element)
T->Right = Insert(X,T->Right);

return T;
}?


void Print(Position P)
{
printf("%d",P->Element);
}


SearchTree Delete(ElementType X,SearchTree T)
{
Position TmpCell;
if(NULL == T)
{
printf("No Found\n");
}
else?
if(X < T->Element)
T->Left = Delete(X,T->Left);
else?
if(X > T->Element)
T->Right = Delete(X,T->Right);
else?
if(T->Left && T->Right) // 存在兩個(gè)兒子節(jié)點(diǎn)?
{
TmpCell = FindMin(T->Right); //從右子樹中找到最小值覆蓋該值，等于刪除該數(shù)?
T->Element = TmpCell->Element;
T->Right = Delete(T->Element,T->Right); //遞歸在右子樹中刪除這個(gè)最小值?
}
else //存在一個(gè)或者0個(gè)兒子節(jié)點(diǎn)?
{
TmpCell = T;
if(NULL == T->Left) //如果右邊為空，用左邊兒子代替該節(jié)點(diǎn)?
T = T->Right;
else if(NULL == T->Right ) //如果左邊為空，用右邊兒子代替該節(jié)點(diǎn)?
T = ?T->Left;

free(TmpCell); //刪除該節(jié)點(diǎn)?
}

return T;
}?






void Traveral_H (SearchTree T)
{
if(NULL != T->Left)
{
Traveral_H(T->Left);
}
if(NULL != T->Right)
{
Traveral_H(T->Right);
}
printf("%d ",T->Element);
}


void Traveral_Z (SearchTree T)
{
if(NULL != T->Left)
{
Traveral_Z(T->Left);
}

printf("%d ",T->Element);

if(NULL != T->Right)
{
Traveral_Z(T->Right);
}
}


void Traveral_Q (SearchTree T)
{
printf("%d ",T->Element);
if(NULL != T->Left)
{
Traveral_Q(T->Left);
}
if(NULL != T->Right)
{
Traveral_Q(T->Right);
}
}?
?