/*  二叉查找树 基本操作  */
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;

struct TNode {
    ElementType Element;
    BinTree Left;
　　BinTree Right;
};

int PreOrderJudge( BinTree T );        /*  判断是否满足BST */
void PreorderTraversal( BinTree BST ); /* 先序遍历 */ 
void InorderTraversal( BinTree BST ); /* 中序遍历 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main() { 　　
 BinTree BST, MinP, MaxP, Tmp; 　　
 ElementType X; 　
 　int N, i; 　　

　　/* Insert node to build a BST */
 BST = NULL; 　　scanf("%d", &N); 　　for ( i = 0; i < N; i++ ) { 　　　　scanf("%d", &X); 　　　　BST = Insert(BST, X); 　　} 　　printf("Preorder: "); 　　PreorderTraversal(BST); 　　printf("\nInorder: "); 
　　InorderTraversal(BST); 　　
　　printf("\n");　　　　

　　MinP = FindMin(BST); 　 
　　MaxP = FindMax(BST);　　
　　scanf("%d", &N); /* search N numebr */

　　for ( i = 0; i < N; i++ ) { 　　　　scanf("%d", &X); 　　　　Tmp = Find(BST, X); 　　　　if ( Tmp == NULL ) 　　　　　　printf("%d is not found\n", X); 　　　　else { 　　　　　　printf("%d is found\n", Tmp->Element); 　　　　　　if ( Tmp == MinP ) 　　　　　　　　printf("%d is the smallest key\n", Tmp->Element); 　　　　　　if ( Tmp == MaxP ) 　　　　　　　　printf("%d is the largest key\n", Tmp->Element); 　　　　} 　　} /* for */

 /* Delete all nodes */ 　　scanf("%d", &N); 　　for ( i = 0; i < N; i++ ) { 　　　　scanf("%d", &X); 　　　　BST = Delete(BST, X); 　　}
 　　return 0; } BinTree Insert( BinTree BST, ElementType X ) { 　　if ( !BST ) {
　　　　/* 若原树为空，生成并返回一个结点的二叉搜索树 */ 　　　　BST = (BinTree)malloc(sizeof(struct TNode)); 　　　　BST->Element = X; 　　　　BST->Left = BST->Right = NULL; 　　}　else { 
　　　　/* 开始找要插入元素的位置 */ 　　　　if ( X < BST->Element ) 　　　　　　BST->Left = Insert( BST->Left, X ); /*递归插入左子树*/ 　　　　else if ( X > BST->Element ) 　　　　　　BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/ 　　　　　　/* else X已经存在，什么都不做 */ 　　} 　　return BST; } BinTree Delete( BinTree BST, ElementType X ) { 　　Position Tmp; 　　if ( !BST ) 　　　　printf("Not Found\n"); 　　else { 　　　　if ( X < BST->Element ) 　　　　　　BST->Left = Delete( BST->Left, X ); /* 从左子树递归删除 */ 　　　　else if ( X > BST->Element ) 　　　　　　BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */ 　　　　else { /* BST就是要删除的结点 */ 　　　　　　/* 如果被删除结点有左右两个子结点 */ 　　　　　　if ( BST->Left && BST->Right ) { 　　　　　　　　/* 从右子树中找最小的元素填充删除结点 */ 　　　　　　　　Tmp = FindMin( BST->Right ); 　　　　　　　　BST->Element = Tmp->Element; 　　　　　　　　/* 从右子树中删除最小元素 */ 　　　　　　　　BST->Right = Delete( BST->Right, BST->Element ); 　　　　　　}　else {
　　　　　　　　/* 被删除结点有一个或无子结点 */ 　　　　　　　　Tmp = BST; 　　　　　　　　if( !BST->Left ) /* 只有右孩子或无子结点 */ 　　　　　　　　　　BST = BST->Right; 　　　　　　　　else /* 只有左孩子 */ 　　　　　　　　　　BST = BST->Left; 　　　　　　　　free( Tmp ); 　　　　　　} 　　　　} /* else */ 　　} 　　return BST; } Position Find( BinTree BST , ElementType X ) { 　　if ( !BST ) return NULL; /*查找失败*/ 　　if ( X > BST->Element ) 　　　　return Find( BST->Right, X ); /*在右子树中继续查找*/ 　　else if ( X < BST->Element ) 　　　　return Find( BST->Left, X); /*在左子树中继续查找*/ 　　else /* X == BST->Element */ 　　　　return BST; /*查找成功，返回结点的找到结点的地址*/ }  Position FindMin( BinTree BST ) { 　　if ( !BST ) return NULL; /*空的二叉搜索树，返回NULL*/ 　　else if ( !BST->Left ) 　　　　return BST; /*找到最左叶结点并返回*/ 　　else 　　　　return FindMin( BST->Left ); /*沿左分支继续查找*/ } Position FindMax( BinTree BST ) { 　　if ( BST ) { 　　　　while( BST->Right ) 　　　　　　BST = BST->Right; 　　　　　　/*沿右分支继续查找，直到最右叶结点*/ 　　　　return BST;
　　} } void InorderTraversal( BinTree BST ) { 　　if ( BST ) { 　　　　InorderTraversal( BST->Left ); 　　　　printf("%d", BST->Element); 　　　　InorderTraversal( BST->Right ); 　　} } void PreorderTrav