动态生成的二叉排序树_二叉排序树查找

心若幽兰 　　1 //https://www.cnblogs.com/aimmiao/p/a.out 45 12 53 3 37 100 24 61 90 78 2 3 //测试 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 8 #define DEBUG 9 10 #define MAX_SIZE 50 11 #define TRUE 1 12 #define FALSE 0 13 14 #define EQ(a, b) ((a)==(b)) 15 #define LT(a, b) ((a)< (b)) 16 #define LQ(a, b) ((a)<=(b)) 17 18 /*定义关键字key为int型*/ 19 typedef int KeyType; 20 /*数据素类型*/ 21 typedef struct{ 22 KeyType key; 23 }ElemType; 24 /*二叉链表结构*/ 25 typedef struct{ 26 ElemType data; 27 struct BiTNode *lchild; 28 struct BiTNode *rchild; 29 }BiTNode, *BiTree; 30 31 /*二叉排序树查找算法 32 * 33 *在根指针T所指二叉排序树中递归地查找其关键字等于key。 34 *若查找成功，则指针p指向该数据素结点，指针f2指向p的父亲结点，并返回TRUE 35 *若查找失败，则指针p指向查找路径上访问的最后一个结点，并返回FALSE。 36 * 37 *注意： 38 *指针f是传入参数，指向T的双亲，其初始调用值为NULL 39 *指针f2是传出参数，若查找成功，则指向p的父亲结点 40 */ 41 int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p, BiTree *f2){ 42 if(!T){ 43 //查找不成功 44 *p = f; 45 return FALSE; 46 }else if(EQ(key, T->data.key)){ 47 //查找成功 48 *p = T; 49 //f2指向结点p的父亲结点 50 if(f2){ 51 *f2 = f; 52 } 53 return TRUE; 54 }else if(LT(key, T->data.key)){ 55 //在左子树上继续查找 56 return SearchBST((BiTree)T->lchild, key, T, p, f2); 57 }else{ 58 //在右子树上继续查找 59 return SearchBST((BiTree)T->rchild, key, T, p, f2); 60 } 61 } 62 63 /*二叉排序树插入算法 64 * 65 *当二叉排序树T中不存在关键字等于e.key的数据素时，插入e并返回TRUE，否则返回FALSE。 66 */ 67 int InsertBST(BiTree *T, ElemType e){ 68 //提示：这儿必须用malloc给p分配堆，否则调用的SearchBST函数里无法给*p赋值。 69 BiTree *p = (BiTree*)malloc(sizeof(BiTree*)); 70 if(!SearchBST(*T, e.key, NULL, p, NULL)){ 71 //查找不成功，所以不存在关键字等于e.key的数据素，需要插入 72 BiTree s = (BiTree)malloc(sizeof(BiTNode)); 73 s->data = e; 74 s->lchild = s->rchild = NULL; 75 if(!(*p)){ 76 //被插结点*s为新的根结点 77 *T = s; 78 }else if(LT(e.key, (*p)->data.key)){ 79 //被插结点*s为左孩子 80 (*p)->lchild = s; 81 }else{ 82 //被插结点*s为右孩子 83 (*p)->rchild = s; 84 } 85 free(p); 86 return FALSE; 87 }else{ 88 //查找成功，说明树中已有关键字相同的结点，不需要再插入。 89 free(p); 90 return TRUE; 91 } 92 } 93 94 /*二叉排序树删除算法 95 * 96 *若二叉排序树T中存在关键字等于key的数据素，则删除该数据素结点，并返回TRUE。 97 *否则返回FALSE 98 */ 99 int DeleteBST(BiTree *T, KeyType key){ 100 int ret = FALSE; 101 102 BiTree *p = (BiTree*)malloc(sizeof(BiTree*)); 103 BiTree *father = (BiTree*)malloc(sizeof(BiTree*)); 104 105 if(SearchBST(*T, key, NULL, p, father)){ 106 //找到关键字等于key的数据素，需要删除 107 108 if(!(*p)->lchild){ 109 //左子树空，则只需重接它的右子树 110 111 if(*father){ 112 //被删结点不是根结点，因为其父亲结点father非空 113 if((*p) == (BiTree)(*father)->lchild){ 114 //被删结点是其父亲结点的左子树 115 (*father)->lchild = (*p)->rchild; 116 }else{ 117 //被删结点是其父亲结点的右子树 118 (*father)->rchild = (*p)->rchild; 119 } 120 }else{ 121 //被删结点是根结点，因为其父亲结点father空 122 *T = (BiTree)((*p)->rchild); 123 } 124 free(*p); 125 *p = NULL; 126 }else if(!(*p)->rchild){ 127 //右子树空，则只需重接它的左子树 128 129 if(*father){ 130 //被删结点不是根结点，因为其父亲结点father非空 131 if((*p) == (BiTree)(*father)->lchild){ 132 //被删结点是其父亲结点的左子树 133 (*father)->lchild = (*p)->lchild; 134 }else{ 135 //被删结点是其父亲结点的右子树 136 (*father)->rchild = (*p)->lchild; 137 } 138 }else{ 139 //被删结点不是根结点，因为其父亲结点father空 140 *T = (BiTree)((*p)->lchild); 141 } 142 free(*p); 143 *p = NULL; 144 }else{ 145 //左右子树都不为空 146 BiTNode *q, *s; 147 q = (BiTNode*)*p; 148 //转左 149 s = (BiTNode*)(*p)->lchild; 150 //然后向右走到尽头 151 while(s->rchild){ 152 q = s; 153 s = (BiTNode*)s->rchild; 154 } 155 //s指向被删除结点的”前驱” 156 (*p)->data = s->data; 157 if(q!=(BiTNode*)(*p)){ 158 //重接*q的右子树 159 q->rchild = s->lchild; 160 }else{ 161 //重接*q的左子树 162 q->lchild = s->lchild; 163 } 164 free(s); 165 } 166 167 ret = TRUE; 168 }else{ 169 //不存在关键字等于key的数据素，不需要删除，返回FALSE。 170 ret = FALSE; 171 } 172 free(p); 173 free(father); 174 return ret; 175 } 176 177 /*先序遍历二叉树算法声明*/ 178 int PreOrderTraverse(BiTree T); 179 /*中序遍历二叉树算法声明*/ 180 int InOrderTraverse(BiTree T); 181 /*后序遍历二叉树算法声明*/ 182 int PostOrderTraverse(BiTree T); 183 184 /*分别用先、中、后序遍历算法顺序打印二叉排序树*/ 185 void print(BiTree T) 186 { 187 printf(“先序遍历二叉排序树: 　　”); 188 PreOrderTraverse(T); 189 printf(” 　　”); 190 191 printf(“中序遍历二叉排序树: 　　”); 192 InOrderTraverse(T); 193 printf(” 　　”); 194 195 printf(“后序遍历二叉排序树: 　　”); 196 PostOrderTraverse(T); 197 printf(” 　　”); 198 } 199 200 int main(int argc, char *argv[]) 201 { 202 if(argc < 2) 203 return FALSE; 204 int i = 0; 205 BiTree T = NULL; 206 ElemType e; 207 //动态创建二叉排序树 208 for(i=1; i<argc; i++){ 209 e.key = atoi(argv[i]); 210 //如果素e不存在，就插入到二叉排序树T中 211 InsertBST(&T, e); 212 } 213 #ifdef DEBUG 214 print(T); 215 #endif 216 217 KeyType k = 0; 218 while(1){ 219 printf(” 　　输入要删除的key(负值表示结束):”); 220 scanf(“%d”, &k); 221 if(k<0) 222 break; 223 if(DeleteBST(&T, k)){ 224 printf(“删除key(%d)成功!!!!!! 　　”, k); 225 #ifdef DEBUG 226 print(T); 227 #endif 228 }else{ 229 printf(“删除key(%d)失败!!!!!! 　　”, k); 230 } 231 } 232 return 0; 233 } 234 235 /*先序遍历二叉树算法实现*/ 236 int PreOrderTraverse(BiTree T){ 237 if(T){ 238 printf(“%d “, ((BiTNode*)T)->data.key); 239 PreOrderTraverse((BiTree)T->lchild); 240 PreOrderTraverse((BiTree)T->rchild); 241 } 242 return 0; 243 } 244 245 /*中序遍历二叉树算法实现*/ 246 int InOrderTraverse(BiTree T){ 247 if(T){ 248 InOrderTraverse((BiTree)T->lchild); 249 printf(“%d “, ((BiTNode*)T)->data.key); 250 InOrderTraverse((BiTree)T->rchild); 251 } 252 return 0; 253 } 254 255 /*后序遍历二叉树算法实现*/ 256 int PostOrderTraverse(BiTree T){ 257 if(T){ 258 PostOrderTraverse((BiTree)T->lchild); 259 PostOrderTraverse((BiTree)T->rchild); 260 printf(“%d “, ((BiTNode*)T)->data.key); 261 } 262 return 0; 263 }