#ifndef _Tree_H
#define _Tree_H
typedef int ElementType;
typedef struct TreeNode
{
ElementType Element;
struct TreeNode *Left;
struct TreeNode *Right;
}*Position, *SearchTree;
SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
#endif
#include <stdio.h>
#include <stdlib.h>
#include "binarySearchTree.h"
SearchTree MakeEmpty(SearchTree T)
{
if (T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
Position Find(ElementType X, SearchTree T)
{
if (T == NULL)
return NULL;
else if (X < T->Element)
return Find(X, T->Left);
else if (X > T->Element)
return Find(X, T->Right); //都需要return
else
return T;
}
Position FindMin(SearchTree T)
{
if (T == NULL)
{
return NULL;
}
else if (T->Left == NULL)
{
return T;
}
else
{
return FindMin(T->Left);
}
}
Position FindMax(SearchTree T)
{
if (T == NULL)
{
while (T->Right != NULL)
{
T = T->Right;
}
}
return T;
}
SearchTree Insert(ElementType X, SearchTree T)
{
if (T == NULL)
{
T = malloc(sizeof(struct TreeNode));
if (T == NULL)
perror("malloc error\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;
}
SearchTree Delete(ElementType X, SearchTree T)
{
Position TmpCell = NULL;
if (T == NULL)
{
printf("Element not found");
}
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) //找到值
{
TmpCell = FindMin(T->Right); //找出右子树中的最小值，这样它没有左子树
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
}
else //只有左子树或只有右子树
{
TmpCell = T;
if (T->Left == NULL)
{
T = T->Right;
}
else if (T->Right == NULL)
{
T = T->Left;
}
free(TmpCell);
}
return T;
}
void printMember(Position T)
{
if (T == NULL)
printf("this Position is not exit\n");
else
printf("Element = %d\n", T->Element);
}
void printTree(SearchTree T, int deep, char *s)
{
int i = deep;
if (T == NULL)
return;
i++;
while (deep)
{
printf("\t");
deep--;
}
printf("%s -> %d\n",s, T->Element);
printTree(T->Left, i, "left");
printTree(T->Right, i, "right");
return;
}
int main()
{
SearchTree T = NULL;
MakeEmpty(T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
printTree(T, ,"start");
printMember(Find(, T));
printMember(FindMax(T));
printMember(FindMin(T));
T = Delete(, T);
printTree(T, , "delete");
}