二叉查找树

//SearchTree.h
typedef int ElementType;

#ifndef _TREE_H_
#define _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

//SearchTree.c
#include "SearchTree.h"
#include <stdio.h>
#include <stdlib.h>


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->Left );
    else if( X > T->Element )
        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);
}

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

SearchTree Insert( ElementType X, SearchTree T )
{
    if(T == NULL)
    {
        T = (SearchTree)malloc( sizeof( struct TreeNode ) );
        if( T == NULL)
            printf("Malloc error!\n");
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }
    else if( X < T->Element )
        T->Left = Insert( X, T->Left );
    else if( X > T->Element )
        T->Right = Insert( X, T->Right );
    return T;
}

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

    if( T == NULL )
        printf( " Element not found!\n" );
    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->Left;
        free( TmpCell );
    }

    return T;
}

//main.c
#include "SearchTree.h"
#include <stdio.h>
#include <stdlib.h>

int main()
{
    SearchTree t1 = NULL;
    Position pmax, pmin;

    t1 = MakeEmpty( t1 );
    t1 = Insert( 1, t1 );
    t1 = Insert( 2, t1 );
    t1 = Insert( 6, t1 );
    t1 = Insert( 4, t1 );

    pmax = FindMax( t1 );
    pmin = FindMin( t1 );
    printf( "pmax = %d\n", pmax->Element );
    printf( "pmin = %d\n", pmin->Element );

    return 0;
}