#include<iostream>
using namespace std;
typedef struct node
{
        int date , key;
        struct node * left;
        struct node * right;
        struct node * father;
}Bsttree, *Bst_tree;
void BST_Insert( Bst_tree &T , Bsttree nod );
Bst_tree Max_tree( Bst_tree T );
Bst_tree Min_tree( Bst_tree T );
void delete_node( Bst_tree T );
void Transport_tree( Bst_tree T , Bst_tree K );
Bst_tree  root = NULL;
int main()
{
    int bzhi;  
    while( scanf("%d",& bzhi) && bzhi!=0 )
    {
              if( bzhi==1 )  
              {
                         Bsttree t;
                         scanf("%d%d", &t.date, &t.key);
                         BST_Insert( root , t );
              }
              else if( bzhi==2 )
                          Max_tree( root );
              else        Min_tree( root );
    }
    //system("pause");
    return 0;
}
void BST_Insert( Bst_tree & T , Bsttree nod )
{
     if( !T )
     {
                 T = new  Bsttree;
                 T->date = nod.date;
                 T->key  = nod.key;
                 T -> left = NULL;
                 T -> right = T ->father = NULL;
     }
     else
     {
                 if( nod.key <= T->key )
                 {
                            if( T -> left == NULL )
                            {
                                      Bst_tree  new_node;
                                      new_node = new Bsttree;
                                      T -> left = new_node;
                                      new_node->date = nod.date;
                                      new_node->key = nod.key;
                                      new_node -> left = new_node ->right = NULL;
                                      new_node -> father = T;
                            }
                            else
                            {
                                      BST_Insert( T->left , nod );
                            }
                 }
                 else
                 {
                            if( T -> right == NULL )
                            {
                                      Bst_tree  new_node;
                                      new_node  =  new Bsttree;
                                      T -> right = new_node;
                                      new_node->date = nod.date;  
                                      new_node->key = nod.key;
                                      new_node -> left = new_node ->right =NULL;
                                      new_node -> father = T;
                            } 
                            else
                            {
                                      BST_Insert( T->right , nod ); 
                            }
                 }
     }
}
Bst_tree Max_tree( Bst_tree T )
{
    if( !T )    printf("0\n");
    else
    { 
       if( T->right )
       {
              Max_tree( T->right );
       }
       else         
       {
                     Bst_tree nod = T;
                     printf( "%d\n" ,T->date ); 
                     delete_node( T );
                     return nod;
       }
    }
}
Bst_tree Min_tree( Bst_tree T )
{
    if( !T )     printf("0\n");
    else
    { 
       if( T->left )
       {
              Min_tree( T->left );
       }
       else
       {
                      Bst_tree nod = T;
                      printf("%d\n" ,T->date );
                      delete_node( T ); 
                      return nod ;
       }
    }
}
void delete_node( Bst_tree T )
{
       if( T->left == NULL )
                   Transport_tree( T , T->right );
       else if( T->right == NULL )
                   Transport_tree( T , T->left ); 
       else
       {
                   Bst_tree nod = Min_tree( T->right );
                   if( nod->father!=T )
                   {
                           Transport_tree( nod , nod->right );
                           nod->right = T->right;
                           nod->right->father = nod;
                   }    
                   Transport_tree( T , nod );
                   nod->left = T->left;
                   nod->left->father = nod;
       }                        
}
void Transport_tree( Bst_tree T , Bst_tree K )
{
     if( T->father==NULL )
                 root = K;
     else if( T == T->father->left )
                 T->father->left = K;
     else        T->father->right = K;  
     if( K )
                 K->father = T->father;                     
}

• Re:第一次完整的写出 二叉搜索树 的所有操作，320ms过，不要用cin和cout， (13) 390467054 2013-11-30 19:22:56