查找树ADT-二叉查找树

/////////////////////////////// tree.h  /////////////////////////////////
#ifndef _TREE_H_
#define _TREE_H_
#define ElementType int

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);
Position	Insert(ElementType x,SearchTree t);
Position	Delete(ElementType x,SearchTree t);
ElementType Retrieve(Position p);

#endif

struct TreeNode {
	ElementType Element;
	SearchTree Left;
	SearchTree Right;
};
//////////////////////////////////////////////////////////////////////////
#include "tree.h"
#include <stdio.h>
#include <stdlib.h>

//建立一棵空树的例程
SearchTree MakeEmpty(SearchTree t)
{
	if (t != NULL) 
	{
		MakeEmpty(t->Left);
		MakeEmpty(t->Right);
		free(t);
	}
	return NULL;
}
//先序遍历
void Preorder_TreePrint(SearchTree t)
{
	if(t!=NULL)
	{
		printf("%d ",t->Element);
		Preorder_TreePrint(t->Left);
		Preorder_TreePrint(t->Right);
	}
}
//中序遍历
void Inorder_TreePrint(SearchTree t)
{
	if(t!=NULL)
	{
		Inorder_TreePrint(t->Left);
		printf("%d ",t->Element);
		Inorder_TreePrint(t->Right);
	}
}
//后续遍历
void Postorder_TreePrint(SearchTree t)
{
	if(t!=NULL)
	{
		Postorder_TreePrint(t->Left);
		Postorder_TreePrint(t->Right);
		printf("%d ",t->Element);
	}
} 
//查找元素
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 = (SearchTree)malloc(sizeof(struct TreeNode));
		if (t == NULL)
		{
			printf("Out of space!!\n");
		}
		else
		{
			t->Element = x;
			t->Left = t->Right = NULL;
		}
	}
	else if (x < t->Element)
	{
		t->Left = Insert(x,t->Left);
	}
	else
	{
		t->Right = Insert(x,t->Right);
	}

	return t;
}

//删除元素
SearchTree Delete(ElementType x,SearchTree t)
{
	Position TmpCell;

	if (t == NULL) 
	{
		printf("Element not found!\n");
	}
	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;
}

//////////////////////////////////////////////////////////////////////////
int main(void)
{
	int i = 0;
	SearchTree st = NULL;
	Position min = NULL;
	Position max = NULL;
	for(i=0;i<20;i++)
	{
		st = Insert(i,st);
	}
	Inorder_TreePrint(st);
	min = FindMin(st);
	max	= FindMax(st);
	printf("min=%d  max=%d\n",min->Element,max->Element);
	return 0;
}