二叉搜索树实现——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;
