数据结构：3.4 二叉搜索树、平衡二叉树

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

Position Find( BinTree BST, ElementType X ) {
    while (BST) {
        if( X > BST->Data )
            BST = BST->Right;
        else if( X < BST->Data )
            BST = BST->Left;
        else
            return BST;
    }
    return NULL;
}

Position FindMin( BinTree BST ) {
    if( BST )
        while( BST->Left ) BST = BST->Left;
    return BST;
}

Position FindMax( BinTree BST ) {
    if( BST )
        while( BST->Right ) BST = BST->Right;
    return BST;
}

//插入
BinTree Insert( BinTree BST, ElementType X ) {
    if( !BST ) {       //若原树为空，则生成一个
        BST = malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else {
        if( X < BST->Data )
            BST->Left = Insert( BST->Left,X );
        else if( X > BST->Data )
            BST->Right = Insert( BST->Right,X );
    } //若X已经存在，就不插入
    return BST;
}

//删除
BinTree Delete( BinTree BST, ElementType X ) {
    Position Tmp;
    if(!BST) printf("Not Found\n"); 
    else if( X < BST->Data )
        BST->Left = Delete(BST->Left,X);  //左子树递归删除
    else if( X > BST->Data )
        BST->Right = Delete(BST->Right,X);  //右子树递归删除
    else   //找到了要删除的结点
        if( BST->Left && BST->Right ) {   //被删除结点有左、右两个子结点
            Tmp = FindMin ( BST->Right );
                                   //在右子树中找到最小元素填充被删处
            BST->Data = Tmp->Data;
            BST->Right = Delete( BST->Right,BST->Data );  //删除右子树中最小的元素
        }
        else {   //被删结点有 一个或无 子结点
            Tmp = BST;
            if( !BST->Left )
                BST = BST->Right;
            else if( !BST->Right )
                BST = BST->Left;
            free( Tmp );
        }
    return BST;
}