二叉查找树插入、查找、删除、前中后序遍历、操作【C语言实现】

代码：

#include 
#include 
#include 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
typedef int Status;

struct TreeNode
{
    int Element;
    SearchTree Left;
    SearchTree 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->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 )
        while(T->Right != NULL)
            T = T->Right;
    return T;
}

SearchTree Insert(int X, SearchTree T)
{
    if (T == NULL)
    {

        
        T = (TreeNode*)malloc(sizeof( struct TreeNode ));
        if ( T == NULL )
            printf("Out of space!!!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(int X, SearchTree T)
{
    Position TmpCell;
    if (T == NULL)
        printf("Element not foundn");
    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;
}

int Retrieve(Position P)
{
    return P->Element;
}


void PreorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        printf("%d", T->Element);
        PreorderTravel(T->Left);
        PreorderTravel(T->Right);
    }
}


void InorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        InorderTravel(T->Left);
        printf("%d", T->Element);
        InorderTravel(T->Right);
    }
}


void PostorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        PostorderTravel(T->Left);
        PostorderTravel(T->Right);
        printf("%d", T->Element);
    }
}

void PrintTree(SearchTree T, int Element, int direction)
{
    if (T != NULL)
    {
        if (direction == 0)
            printf("%2d is rootn", T->Element);
        else
            printf("%2d is %2d's %6s childn", T->Element, Element, direction == 1 ? "right" : "left");

        PrintTree(T->Left, T->Element, -1);
        PrintTree(T->Right, T->Element, 1);
    }
}
int main(int argc, char const *argv[])
{
    SearchTree T;
    MakeEmpty(T);

    T = Insert(6, T);
    T = Insert(4, T);
    T = Insert(2, T);
    T = Insert(8, T);
    T = Insert(5, T);
    T = Insert(9, T);
    
    T = Delete(5, T);
    
    printf("树的详细信息:");
    PrintTree(T, T->Element, 0);
    
    printf("前序遍历二叉树:");
    PreorderTravel(T);
    printf("n");
    
    printf("中序遍历二叉树:");
    InorderTravel(T);
    printf("n");
    
    printf("后序遍历二叉树:");
    PostorderTravel(T);
    printf("n");
    
    printf("最大值: %dn", FindMax(T)->Element);
    printf("最小值: %dn", FindMin(T)->Element);

    return 0;
}

结果：