#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct Node {
KeyType key;
struct Node *lchild, *rchild;
} BSTNode;
void InsertBST(BSTNode **bst, int key) {
BSTNode *s;
if (*bst == NULL) {
s = (BSTNode *)malloc(sizeof(BSTNode));
s->key = key;
s->lchild = NULL;
s->rchild = NULL;
*bst = s;
} else {
if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key);
else if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key);
}
}
void CreateBST(BSTNode **bst) {
int key;
*bst = NULL;
printf("请输入一系列整数(以0结束):\n");
scanf("%d", &key);
while (key != 0) {
InsertBST(bst, key);
scanf("%d", &key);
}
}
BSTNode *SearchBST(BSTNode *bst, int key) {
if (!bst)
return NULL;
else if (bst->key == key)
return bst;
else if (bst->key > key)
return SearchBST(bst->lchild, key);
else
return SearchBST(bst->rchild, key);
}
void InOrderTraverse(BSTNode *bst) {
if (bst) {
InOrderTraverse(bst->lchild);
printf("%d ", bst->key);
InOrderTraverse(bst->rchild);
}
}
int main() {
BSTNode *bst = NULL;
int key;
CreateBST(&bst);
printf("\n中序遍历结果(应为升序排列):");
InOrderTraverse(bst);
printf("\n");
printf("\n请输入要查找的关键字(输入0结束查找):\n");
scanf("%d", &key);
while (key != 0) {
BSTNode *result = SearchBST(bst, key);
if (result)
printf("找到关键字 %d\n", key);
else
printf("未找到关键字 %d\n", key);
scanf("%d", &key);
}
return 0;
}