/*
WRITE BY 1XIU
20111103
*/
typedef int ElementType;
#ifndef _TREE_H
#define _TREE_H
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
SearchTree MakeEmpty(SeatchTree T);
Poisition Find(ElementType X,SearchTree T);
Poisition FindMin(SearchTree T);
Poisition FindMax(SearchTree T);
SearchTree Insert(ElementType X,SearchTree T);
SeatchTree Delete(ElementType X,SearchTree T);
ElementType Retrieve(PoisiTION p);
#endif
:
#include "TreeHead.h"
#include<stdlib.h>
struct TreeNode
{
ElementType Element;
SearchTree Left;
SeatchTree Right;
};
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;
}
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(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(strutc TreeNode));
if(T == NULL)
FatalError("out of space!");
else
{
T->Element = X;
T->Left = 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);
//if X is in the tree ,do nothing
return T;
}
SearchTree Delete(ElementType X ,SearchTree T)
{
Position tmpCell;
if(T == NULL)
Error("Element not found!");
else if( X<T->Eelement)
T-Left = Delete(X,T-Left);
else if(X>T->Right)
T->Right = Delete(X,T->Right);
else if(T->Left && T->Right)
{
//find the smallest if right subtree
tmpCell = FindMin(T->Right);
T->Element = tmpCell->Element;
T->Right = Delete(T->Element,T->Rigjt);
}else
{
tmpCell = T;
if(T->Left == NULL)
T = T->Right;
else if(T->Right = NULL)
T = T->Left;
free(tmpCell);
}
return T;
}