[html]
#include
#include

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

/* Placein the implement file */
struct TreeNode
{
int Element;
SearchTree Left;
SearchTree Right;
};

/* clean up tree */
SearchTree MakeEmpty(SearchTree T)
{
if (T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
T = NULL;
}

return NULL;
}

/* find x in the tree */
Position Find(int X, SearchTree T)
{
if (T != NULL)
{
if (T->Element == X)
{
return T;
}
else if(T->Element < X)
{
return Find(X, T->Right);
}
else if (T->Element > X)
{
return Find(X, T->Left);
}
}
else
{
return NULL;
}
}

/* find min */
Position FindMin(SearchTree T)
{
if (T == NULL)
{
return NULL;
}
else
{
if (T->Left != NULL)
{
FindMin(T->Left);
}
else
{
printf("MIN = %d\n", T->Element);
return T;
}
}

}
/* find max */
Position FindMax(SearchTree T)
{
if (T == NULL)
{
return NULL;
}
else
{
if (T->Right!= NULL)
{
FindMax(T->Right);
}
else
{
printf("MAX = %d\n", T->Element);
return T;
}
}

}

/* insert x */
SearchTree Insert(int X, SearchTree T)
{
if (T == NULL)
{
T = (SearchTree)malloc(sizeof(struct TreeNode));
if (T == NULL)
{
printf("out of space!!!\n");
}
else
{
T->Element = X;
T->Left = NULL;
T->Right = NULL;
}
}
else if (X < T->Element)
{
T->Left = Insert(X, T->Left); //-----------------
}
else if (X > T->Element)
{
T->Right = Insert(X, T->Right); //----------------
}

return T;
}

/* delete x */
SearchTree DeleteTree(int X, SearchTree T)
{
Position TmpCell;

if (T == NULL)
{
printf("X not found.\n");
}
else
{
if (X < T->Element) /* go to left */
{
T->Left = DeleteTree(X, T->Left);
}
else if (X > T->Element)
{
T->Right = DeleteTree(X, T->Right);
}
else
{
if (T->Left && T->Right) /* Two children */
{
/* replace with smallest in right subtree */
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = DeleteTree(T->Element, T->Right);
}
else
{
TmpCell = T;
if (T->Left == NULL)
T = T->Right;
else if (T->Left == NULL)
T = T->Left;
free(TmpCell);
}
}
}
return T;
}

// 中序遍历。打印。
void ShowTree(SearchTree T)
{
if (T != NULL)
{
ShowTree(T->Left);
printf(" %d ", T->Element);
ShowTree(T->Right);
}

}

int main(void)
{
Position tree = NULL;
tree = Insert(6, tree);
tree = Insert(2, tree);
tree = Insert(8, tree);
tree = Insert(1, tree);
tree =