04-树7 二叉搜索树的操作集

　　此题要求实现给定二叉搜索树的5种常用操作。
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef int ElementType;
  5 typedef struct TNode *Position;
  6 typedef Position BinTree;
  7 struct TNode{
  8     ElementType Data;
  9     BinTree Left;
 10     BinTree Right;
 11 };
 12 
 13 void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
 14 void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */
 15 
 16 BinTree Insert( BinTree BST, ElementType X );
 17 BinTree Delete( BinTree BST, ElementType X );
 18 Position Find( BinTree BST, ElementType X );
 19 Position FindMin( BinTree BST );
 20 Position FindMax( BinTree BST );
 21 
 22 int main()
 23 {
 24     BinTree BST, MinP, MaxP, Tmp;
 25     ElementType X;
 26     int N, i;
 27 
 28     BST = NULL;
 29     scanf("%d", &N);
 30     for ( i=0; i<N; i++ ) {
 31         scanf("%d", &X);
 32         BST = Insert(BST, X);
 33     }
 34     printf("Preorder:"); PreorderTraversal(BST); printf("
");
 35     MinP = FindMin(BST);
 36     MaxP = FindMax(BST);
 37     scanf("%d", &N);
 38     for( i=0; i<N; i++ ) {
 39         scanf("%d", &X);
 40         Tmp = Find(BST, X);
 41         if (Tmp == NULL) printf("%d is not found
", X);
 42         else {
 43             printf("%d is found
", Tmp->Data);
 44             if (Tmp==MinP) printf("%d is the smallest key
", Tmp->Data);
 45             if (Tmp==MaxP) printf("%d is the largest key
", Tmp->Data);
 46         }
 47     }
 48     scanf("%d", &N);
 49     for( i=0; i<N; i++ ) {
 50         scanf("%d", &X);
 51         BST = Delete(BST, X);
 52     }
 53     printf("Inorder:"); InorderTraversal(BST); printf("
");
 54 
 55     return 0;
 56 }
 57 /* 你的代码将被嵌在这里 */
 58 BinTree Insert( BinTree BST, ElementType X )
 59 {
 60     if ( !BST ) {
 61         BST = (BinTree)malloc(sizeof(struct TNode));
 62         BST->Left = BST->Right = NULL;
 63         BST->Data = X;
 64     } 
 65     else {
 66         if ( X < BST->Data )        
 67             BST->Left = Insert(BST->Left, X);  // 递归插入左子树 
 68         else if ( X > BST->Data )    
 69             BST->Right = Insert(BST->Right, X); // 递归插入右子树
 70         /* else X 已经存在，什么也不做 */ 
 71     }    
 72     
 73     return BST;
 74 }
 75 
 76 BinTree Delete( BinTree BST, ElementType X )
 77 {
 78     BinTree Tmp;
 79     
 80     if ( !BST )    printf("Not Found
"); // 要删除元素未找到 
 81     else {
 82         if ( X < BST->Data )
 83             BST->Left = Delete(BST->Left, X); // 从左子树递归删除 
 84         else if ( X > BST->Data )
 85             BST->Right = Delete(BST->Right, X);// 从右子树递归删除 
 86         else {  // BST 就是要删除的节点 
 87             // 被删除节点有左右两个子节点 
 88             if ( BST->Left && BST->Right ) {
 89                 // 从右子树中找到最小元素填充被删除节点 
 90                 Tmp = FindMin(BST->Right);
 91                 BST->Data = Tmp->Data;
 92                 // 删除 右子树中的最小元素 
 93                 BST->Right = Delete(BST->Right, BST->Data); 
 94             }
 95             else { // 被删除节点有一个或无子节点 
 96                 Tmp = BST;
 97                 if ( !BST->Left ) //  只有右节点或无子节点 
 98                     BST = BST->Right;
 99                 else              //  只有左孩子
100                     BST = BST->Left;
101                 free(Tmp); 
102             }
103         } 
104     }
105     
106     return BST;
107 }
108 
109 Position Find( BinTree BST, ElementType X )
110 {    
111     if ( !BST )        return NULL; // 没找着，返回空指针 
112     if ( X < BST->Data ) 
113         return Find(BST->Left, X);
114     else if ( X > BST->Data )
115         return Find(BST->Right, X);
116     else 
117         return BST;
118 }
119 
120 Position FindMin( BinTree BST )
121 {
122     if ( !BST )    return NULL;
123     else if ( !BST->Left )    
124         return BST;
125     else
126         return FindMin(BST->Left);
127 }
128 
129 Position FindMax( BinTree BST )
130 {
131     if ( BST )
132         while ( BST->Right )    BST = BST->Right;
133     return BST;
134 }