为每个节点指定一个关键值，每个节点的左子树的关键值都小于节点的关键值，而右子树的关键值都大于节点的关键值。
平均深度为O（logN）。
1.fatal.h
#include <stdio.h>
#include<stdlib.h>
#define Error(str) FatalError(str)
#define FatalError(str) fprintf(stderr,"%s\n",str),system("pause"),exit(1)
2.searchtree.h
#include<stdio.h> typedef int ElementType; #ifndef _Tree_H struct TreeNode; typedef struct TreeNode *Position; typedef struct TreeNode *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); ElementType Retrieve(Position P); void Preorder(SearchTree T); #endif
3.searchtree.c
#include "searchtree.h"
#include "fatal.h"
#include <stdio.h>
#include <stdlib.h>
struct TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree 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)
//{
// return NULL;
//}
//else if (T->Right == NULL)
//{
// return T;
//}
//else
//{
// return FindMax(T->Right);
//}
if (T != NULL)
{
while (T->Right != NULL)
{
T = T->Right;
}
}
return T;
}
ElementType Retrieve(Position P)
{
return P->Element;
}
SearchTree Insert(ElementType X, SearchTree T)
{
if (T == NULL)
{
T = malloc(sizeof(struct 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);
return T;
}
SearchTree Delete(ElementType X, SearchTree T)
{
Position TmpCell;
if (T == NULL)
{
Error("Element not found");
}
else if (X < T->Element)
T->Left = Delete(X, T->Left);
else if (X>T->Right)
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->Right;
}
free(TmpCell);
}
}
return T;
}
void Preorder(SearchTree T)
{
if (T == NULL)
{
Error("Tree not found");
}
if (T->Left != NULL)
{
Preorder(T->Left);
}
if (T->Right != NULL)
{
Preorder(T->Right);
}
printf("%d\t", Retrieve(T));
}
4.testsearchtree.c
#include "fatal.h"
#include "searchtree.h"
#include <stdio.h>
#include <stdlib.h>
void main1()
{
SearchTree T = NULL;
T = MakeEmpty(T);
int i = 0;
for (i = 0; i < 10;i++)
{
T= Insert(i, T);
}
Preorder(T);
for (i = 0; i < 10; i++)
{
T = Delete(i, T);
}
system("pause");
}
main()
{
SearchTree T;
Position P;
int i;
int j = 0;
T = MakeEmpty(NULL);
for (i = 0; i < 50; i++)
T = Insert(i, T);
//for (i = 0; i < 50; i++, j = (j + 7) % 50)
// T = Insert(j, T);
Preorder(T);
for (i = 0; i < 50; i++)
if ((P = Find(i, T)) == NULL /*|| Retrieve(P) != i*/)
printf("Error at %d\n", i);
for (i = 0; i < 50; i ++)
T = Delete(i, T);
//for (i = 1; i < 50; i += 2)
// if ((P = Find(i, T)) == NULL || Retrieve(P) != i)
// printf("Error at %d\n", i);
//for (i = 0; i < 50; i += 2)
// if ((P = Find(i, T)) != NULL)
// /*printf("Error at %d\n", i);*/
printf("Min is %d, Max is %d\n", Retrieve(FindMin(T)),
Retrieve(FindMax(T)));
system("pause");
return 0;
}
原文：http://www.cnblogs.com/my-cat/p/5971947.html