#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef struct BSTNode {
int data;
struct BSTNode *lchild;
struct BSTNode *rchild;
} BSTNode, *BSTree;
//动态查找算法:查找插入位置
Status searchBSTForInsert(BSTree T, int key, BSTree &q) {
BSTree p, f;
p = T;
f = NULL;
if (p == NULL)
return FALSE;
while (p) {
if (key == p->data) {
p = q;
return TRUE;
}else if (key, p->data) {
f = p;
p = p->lchild;
}
else {
f = p;
p = p->rchild;
}
}
q = f;
return FALSE;
}
//创建二叉树
void createBSTree(BSTree & T) {
DataType e;
BSTNode *q,*p;
T=NULL;
scanf("%d",&e);
while(!e!=0)
{if(!searchBSTForInsert(T,e.key,q))
{ p=(BSTree)malloc(sizeof(BSTNode));
p->data=e;
p->lchild=p->rchild=NULL;
if(!p)T=p;
else if(e.key<q->data.key)q->lchild=p;
else q->rchild=p;
}
inputElem(e);
}
}
//中序输出
void inorderOutput(BSTree T) {
if (T) {
inorderOutput(T->lchild);
int(T->data);
inorderOutput(T->rchld);
}
}
//静态查找
BSTNode *searchBST(BSTree T, int key) {
BSTNode *p=T;
while(p)
{
if(key==p->data)return p;
else if(key<p->data)p=p->lchild;
else p=->rchild;
}
return NULL;
}
//测试主程序
int main() {
BSTree T;
printf("输入数据序列(以零结束),创建BST:\n");
createBSTree(T);
printf("BST的中序序列:\n");
inorderOutput(T);
printf("\n");
int key;
printf("********BST上查找测试*******\n");
printf("\n输入关键字查找(0结束查找)");
scanf("%d", &key);
while (key != 0) {
BSTNode *p = searchBST(T, key);
if (p)
printf("查找成功,其值为:%d\n", p->data);
else
printf("值为%d的结点不存在!\n", key);
printf("输入关键字值(0结束查找)");
scanf("%d", &key);
}
return 0;
}