二叉搜索树的操作集

总代码：
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 
  5 typedef int ElementType;
  6 typedef struct TNode *Position;
  7 typedef Position BinTree;
  8 struct TNode{
  9     ElementType Data;
 10     BinTree Left;
 11     BinTree Right;
 12 };
 13 
 14 void PreorderTraversal( BinTree BT );
 15 void InorderTraversal( BinTree BT );
 16 void PostorderTraversal( BinTree BT );
 17 
 18 BinTree Insert( BinTree BST, ElementType X );
 19 BinTree Delete( BinTree BST, ElementType X );
 20 Position Find( BinTree BST, ElementType X );
 21 Position FindMin( BinTree BST );
 22 Position FindMax( BinTree BST );
 23 
 24 int main()
 25 {
 26     BinTree BST, MinP, MaxP, Tmp;
 27     ElementType X;
 28     int N,i;
 29 
 30     BST = NULL;
 31     scanf("%d",&N);
 32     for(int i=0;i<N;i++){
 33         scanf("%d",&X);
 34         BST = Insert(BST,X);
 35     }
 36     printf("Preorder: "); PreorderTraversal(BST); printf("
");
 37     MinP = FindMin(BST);
 38     MaxP = FindMax(BST);
 39     scanf("%d",&N);
 40     for(int i=0;i<N;i++){
 41         scanf("%d",&X);
 42         Tmp = Find(BST,X);
 43         if( Tmp==NULL ) printf("%d is not found
",X);
 44         else{
 45             printf("%d is found
",Tmp->Data);
 46             if( Tmp==MinP ) printf("%d is the smallest key
", Tmp->Data);
 47             if( Tmp==MaxP ) printf("%d is the largest key
", Tmp->Data);
 48         }
 49     }
 50     scanf("%d",&N);
 51     for(int i=0;i<N;i++){
 52         scanf("%d",&X);
 53         BST = Delete(BST,X);
 54     }
 55     printf("Inorder:"); InorderTraversal(BST); printf("
");
 56 }
 57 
 58 BinTree Insert(BinTree BST, ElementType X){
 59     if( !BST ){
 60         BST = (BinTree)malloc(sizeof(struct TNode));
 61         BST -> Data = X;
 62         BST -> Left = BST -> Right = NULL;
 63     }
 64     else{
 65         if( X<BST->Data ){
 66             BST -> Left = Insert(BST->Left, X);
 67         }else if( X>=BST->Data ){
 68             BST -> Right = Insert(BST->Right,X);
 69         }
 70     }
 71     return BST;
 72 }
 73 
 74 BinTree Delete(BinTree BST, ElementType X){
 75     Position Temp;
 76     if( !BST ) printf("Not Found
");
 77     else if( X>BST->Data ) BST->Right = Delete(BST->Right,X);
 78     else if( X<BST->Data ) BST->Left = Delete(BST->Left,X);
 79     else{
 80         if( BST->Left && BST->Right ){
 81             Temp = FindMax(BST->Left);
 82             BST->Data = Temp->Data;
 83             BST->Left = Delete(BST->Left,BST->Data);
 84         }else{
 85             Temp = BST;
 86             if( !BST->Left ) BST = BST->Right;
 87             else BST = BST->Left;
 88             free(Temp);
 89         }
 90     }
 91     return BST;
 92 }
 93 
 94 void PreorderTraversal(BinTree BST){
 95     if( BST ){
 96         printf("%d ",BST->Data);
 97         PreorderTraversal(BST->Left);
 98         PreorderTraversal(BST->Right);
 99     }
100 }
101 
102 void InorderTraversal(BinTree BST){
103     if( BST ){
104         InorderTraversal(BST->Left);
105         printf("%d ",BST->Data);
106         InorderTraversal(BST->Right);
107     }
108 }
109 
110 Position FindMin(BinTree BST){
111     if( !BST ) return NULL;
112     else if( !BST->Left ) return BST;
113     else return FindMin(BST->Left);
114 }
115 
116 Position FindMax(BinTree BST){
117     if( !BST ) return NULL;
118     else if( !BST->Right ) return BST;
119     else return FindMax(BST->Right);
120 }
121 
122 Position Find(BinTree BST, ElementType X){
123     if( !BST ) return NULL;
124     else if( BST->Data==X ) return BST;
125     else{
126         if( X>BST->Data ) return Find(BST->Right,X);
127         else if( X<BST->Data ) return Find(BST->Left,X);
128     }
129 }