数据结构与算法分析--学习笔记（5）

struct TreeNode
{
       int Element;
       SearchTree Left;
       SearchTree Right;
};

typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree
MakeEmpty( SearchTree T )
{
           if( T != NULL )
           {
               MakeEmpty( T->Left );
               MakeEmpy( T->Right );
               free( T );
           }
           return NULL;
}

Position
Find( int X, SerachTree T )
{
      if( T == NULL )
      {
          printf( "EmptyTree!No such Position" );
          return NULL;
      }
      if( X < T->Element )
          return Find( int X, T->Left );
      else
      if( X > T->Element )
          return Find( int X, T->Right );
      else
          return T;
}

Position
FindMin( SearchTree T )
{
         if( T == NULL )
         {
             printf( "EmptyTree!" );
             return NULL;
         }
         else
         if( T->Left == NULL )
             return T;
         else
             return FindMin( T->Left );
}

Position
FindMax( SearchTree T )
{
         if( T == NULL )
         {
             printf( "EmptyTree!" );
             return NULL;
         }
         else
         if( T->Right == NULL )
             return T;
         else
             return FindMax( T->Right );
}

SearchTree
Insert( int X, SearchTree T )
{
        if( T == NULL )
        {
            T = malloc( sizeof( struct TreeNode ) );
            if( T == NULL )
                printf( "OUT OF SPACE!" ):
            else
            {
                T->Element = X;
                T->Left = T->Right = NUL;
            }
        }
        else
        if( X < T->Element )
            T->Left = Insert( X, T->Left );
        else
        if( X > T->Element )
            T->Right = Insert( X, T->Right );
        else
            return T;
}

SearchTree
Delete( int X, SearchTree T )
{
        Position TmpCell;
        
        if( T == NULL )
            printf( "Element not found!" );
        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->Right;
            free( TmpCell );
        }
        
        return T;
}