二叉搜索树实现――C++ (一)

二叉搜索树的性质是：对树中的每个结点X，它的左子树的值小于X，它的右子树的值大于X。

BinaryTree.h

[cpp]
#include "Utility.h"

//typedef struct TreeNode *PtrToNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

struct TreeNode
{
int data;
TreeNode *left;
TreeNode *right;
};

SearchTree MakeEmpty( SearchTree T )
{
if( T != NULL )
{
MakeEmpty( T->left );
MakeEmpty( T->right );
free(T);
}
return NULL;
}

Position Find( int x, SearchTree T )
{
if( T == NULL )
return NULL;
if( x < T->data )
return Find( x, T->left );
else if( x > T->data )
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 );
//照着FindMax实现非递归的方法
}

Position FindMax( SearchTree T )
{
if( T != NULL )
while( T->right != NULL )
T = T->right;

return T;
}

SearchTree Insert( int x, SearchTree T )
{
if( T == NULL )
{
T = (TreeNode *)malloc(sizeof(TreeNode));
if( T == NULL )
cout << "存储空间不足！" << endl;
else
{
T->data = x;
T->left = T->right = NULL;
}
}else if( x < T->data ){
T->left = Insert( x, T->left );
}else if( x > T->data ){
T->right = Insert( x, T->right );
}

return T;
}

SearchTree Delete( int x, SearchTree T )
{
Position tmp;

if( T == NULL ){
cout << "未找到元素！" << endl;
}else if( x < T->data ){
T->left = Delete( x, T->left );
}else if( x > T->data ){
T->right = Delete( x, T->right );
}else if( T->left && T->right ){ // x == T->data
tmp = FindMin( T->right );
T->data = tmp->data;
T->right = Delete( T->data, T->right );
}else{
tmp = T;
if( T->left == NULL )
T = T->right;
else if( T->right == NULL )
T = T->left;
free( tmp );
}
return T;
}

void InOrderPrint( SearchTree T )
{
if( T != NULL )
{
InOrderPrint( T->left );
cout << T->data << " ";
InOrderPrint( T->right );
}
}

void PreOrderPrint( SearchTree T )
{
if( T != NULL )
{
cout << T->data << " ";
PreOrderPrint( T->left );
PreOrderPrint( T->right );
}
}

#include "Utility.h"

//typedef struct TreeNode *PtrToNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

struct TreeNode
{
int data;
TreeNode *left;
TreeNode *right;
};

SearchTree MakeEmpty( SearchTree T )
{
if( T != NULL )
{
MakeEmpty( T->left );
MakeEmpty( T->right );
free(T);
}
return NULL;
}

Position Find( int x, SearchTree T )
{
if( T == NULL )
return NULL;
if( x < T->data )
return Find( x, T->left );
else if( x > T->data )
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 );
//照着FindMax实现非递归的方法
}

Position FindMax( SearchTree T )
{
if( T != NULL )
while( T->right != NULL )
T = T->right;

return T;
}

SearchTree Insert( int x, SearchTree T )
{
if( T == NULL )
{
T = (TreeNode *)malloc(sizeof(TreeNode));
if( T == NULL )
cout << "存储空间不足！" << endl;
else
{
T->data = x;
T->left = T->right = NULL;
}
}else if( x < T->data ){
T->left = Insert( x, T->left );
}else if( x > T->data ){
T->right = Insert( x, T->right );
}

return T;
}

SearchTree Delete( int x, SearchTree T )
{
Posit