#include<bits/stdc++.h>
#define MaxSize 100
using namespace std;
typedef struct TreeNode
{//定义二叉树结构
    char Data;
    struct Node *lchild,*rchild;
}*BiTree,BiTNode;

//查找1
BiTNode Find( int X, BiTree BST ) {
    if( !BST ) 
        return NULL; /*查找失败*/ 
    if( X > BST->Data ) 
        return Find( X, BST->rchild ); /*在右子树中继续查找*/
    else if( X < BST->Data ) 
        return Find( X, BST->lchild ); /*在左子树中继续查找*/
    else /* X == BST->Data */ 
        return BST; /*查找成功，返回结点的找到结点的地址*/
}
//查找2（非递归）
BiTNode IterFind( int X, BiTree BST ) {
    while( BST ) { 
        if( X > BST->Data ) BST = BST->rchild; /*向右子树中移动，继续查找*/
        else if( X < BST->Data ) 
            BST = BST->lchild; /*向左子树中移动，继续查找*/
        else /* X == BST->Data */ 
            return BST; /*查找成功，返回结点的找到结点的地址*/
    } 
    return NULL; /*查找失败*/ 
}

//查最小(递归)
BiTNode FindMin(BiTree BST){
    if(!BST)
        return NULL;
    else if(!BST->lchild)
        return BST;
    else
        return FindMin(BST->lchild);
}
//查最大（迭代）
BiTNode FindMax(BiTree BST){
    if(BST)
        while(BST->rchild)
            BST = BST->rchild;
    return BST;
}
//插入
BiTree Insert( int X, BiTree BST ) {
    if( !BST ){
        /*若原树为空，生成并返回一个结点的二叉搜索树*/
        BST = malloc(sizeof(struct TreeNode)); 
        BST->Data = X; 
        BST->lchild = BST->rchild = NULL;
    }else /*开始找要插入元素的位置*/ 
        if( X < BST->Data ) 
            BST->lchild = Insert( X, BST->lchild); 
        /*递归插入左子树*/
        else if( X > BST->Data ) 
            BST->rchild = Insert( X, BST->rchild); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */ 
    return BST; 
}
//删除
BiTree Delete( int X, BiTree BST ) {
    BiTNode Tmp; 
    if( !BST ) printf("要删除的元素未找到"); 
    else if( X < BST->Data )
        BST->lchild = Delete( X, BST->lchild); /* 左子树递归删除 */
    else if( X > BST->Data ) 
        BST->rchild = Delete( X, BST->rchild); /* 右子树递归删除 */
    else /*找到要删除的结点 */ 
        if( BST->lchild && BST->rchild ) { /*被删除结点有左右两个子结点 */ 
            Tmp = FindMin( BST->rchild );
            /*在右子树中找最小的元素填充删除结点*/
            BST->Data = Tmp->Data; 
            BST->rchild = Delete( BST->Data, BST->rchild); 
            /*在删除结点的右子树中删除最小元素*/
        } else { /*被删除结点有一个或无子结点*/ 
            Tmp = BST;
            if( !BST->lchild ) /* 有右孩子或无子结点*/ 
                BST = BST->rchild;
            else if( !BST->rchild ) /*有左孩子或无子结点*/ 
                BST = BST->lchild;
            free( Tmp );
        }
    return BST;
}