/*  二叉查找树 基本操作  */ #include 
     
      #include 
      
       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 PreorderTraversal( BinTree BT ){　　if( BT ) {　　　　printf("%d ", BT->Element);　　　　PreorderTraversal( BT->Left );　　　　PreorderTraversal( BT->Right );　　}} void PreOrderJudge( BinTree BST ){　　if ( BST == NULL ) {　　　　printf("Empty Tree!");　　　　return;    　　}　else if ( BST )  {　　　　if ( BST->Left ) {
        　　　　　　/* 左儿子更大 */　　　　　　if( BST->Left->Element >= BST->Element )　　　　　　　　return;　　　　}　　　　if ( BST->Right ) {
        　　   　　/* 右儿子更小 */　　　　　　if ( BST->Right->Element <= BST->Element )　　　　　　　　return;　　　　}    　　　　PreOrderJudge( BST->Left );　　　　PreOrderJudge( BST->Right );　　} }