我認為要看懂下面的代碼，對於遞歸的運行，要很了解才是！
[html]
#include <stdio.h>
#include <stdlib.h>
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 = Insert(5, tree);
tree = Insert(4, tree);
tree = Insert(3, tree);
DeleteTree(3, tree);
//DeleteTree(3, tree);
//DeleteTree(6, tree);
ShowTree(tree);
printf("\n");
FindMax(tree);
FindMin(tree);
return 0;
}
