二叉树是一棵树，其中每个节点都不能有多余两个的儿子；

二叉查找树，对树中的每个节点X，它的左子树所有关键字值小于X的关键字，它的右子树所有关键字值大于X的关键字，满足该条件的二叉树成为二叉查找书

二叉查找书的ADT
头文件

#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 );

#endif /* _Tree_H */

/* Place in the implementation file */
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->Right );
	else
		if( X < T->Element )
			return Find( X, T->Left );
		else
			return T;
}

Position FindMin( SearchTree T )
{
	if( T != NULL )
		while( T->Left != NULL )
			T = T->Left;

	return T;
}

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 )
		{
			printf( "Out of space!!!" );
			exit( 1 );
		}
		else
		{
			T->Element = X;
			T->Left = T->Right = NULL;
		}
	}
	else
	{
		if( T->Element < X )
			Insert( X, T->Right );
		else
			if( T->Element > X )
				Insert( X, T->Left );
			/* else T->Element == X, do nothing */
	}
	return T;
}

SearchTree Delete( ElementType X, SearchTree T )
{
	Position P;

	if( T == NULL )
	{
		printf( "Element not found" );
		exit( 1 );
	}
	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 )
			{
				P = FindMin( T->Right );
				T->Element = P->Element;
				T->Right = Delete( P->Element, T->Right );
			}
			else
			{
				P = T;
				if( T->Left == NULL )
					T = T->Right;
				else
					T = T->Left;
				free( P );
			}

	return T;
}

ElementType Retrieve( Position P )
{
	if( P != NULL )
		return P->Element;
	return 0;/* make sure retrun something */
}