程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 二叉搜索樹實現——C++

二叉搜索樹實現——C++

編輯：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 )
{
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 );
}
}

BinaryTree.cpp

[cpp]
#include "BinaryTree.h"

void main()
{
    SearchTree T;
    Position P;
    int n = 0;
    int x = 0;

    T = MakeEmpty( NULL );
    cout << "輸入二叉樹大小："<< endl;
    cin >> n;
    while( n-- )
    {
        cout << "輸入插入結點：";
        cin >> x;
        T = Insert( x, T );
    }

    //for( int i=0; i < n; i++ )

    cout << "最大元素：" << FindMax( T )->data << endl;
    cout << "最小元素：" << FindMin( T )->data << endl;

    cout << "中序遍歷：";
    InOrderPrint( T );
    cout << endl;

    cout << "前序遍歷：";
    PreOrderPrint( T );
    cout << endl;

    /*
    cout << "輸入要刪除的結點："<< endl;
    cin >> x;
    //Delete( x, T );
    T = Delete( x, T );
    InOrderPrint( T );
    */

    system("PAUSE");
}