PTA 查找算法设计 2 树表查找算法设计

作者 张鏖烽单位 湖南工程学院计算机与通信学院编程实现树表查找相关算法的函数1InsertBT(b,key):在二叉排序树bt中插入关键字key2CreateBT(A,n):创建二叉排序树2BTSearch(b,key):在二叉排序树bt中查找关键字key函数接口定义在这里描述函数接口。例如 void InsertBT(BTnode *bt,int key); BTnode * CreateBT(int A[],int n); int BTSearch(BTnode *bt,int key);其中bt 为二叉排序树key为待操作关键字A[]为输入的关键字序列n为关键字序列的长度裁判测试程序样例在这里给出函数被调用进行测试的例子。例如 #includestdio.h #includemalloc.h #define MaxSize 100 typedef struct Node{ int key; struct Node *lchild,*rchild; }BTnode; void InsertBT(BTnode *b,int key); BTnode * CreateBT(int A[],int n); int BTSearch(BTnode *b,int key); int main() { int k,i,n; int A[MaxSize]; BTnode *btNULL; //输入关键字序列长度n scanf(%d,n); //输入关键字序列 for(i0;in;i) scanf(%d,A[i]); btCreateBT(A,n); //输入待查找关键字k scanf(%d,k); printf(\n树形查找关键字%d需要依次比较,k); iBTSearch(bt,k); if(i0) printf(\n关键字%d查找失败,k); else printf(\n关键字%d查找成功,k); return 0; } /* 请在这里填写答案 */输入样例在这里给出一组输入。例如第1行关键字个数第2行关键字序列第3行待查找关键字k9 10 5 14 8 7 12 16 9 20 12输出样例在这里给出相应的输出。例如树形查找关键字12需要依次比较10 14 12 关键字12查找成功参考代码void InsertBT(BTnode *b,int key){ if(bNULL){ b(BTnode *)malloc(sizeof(BTnode)); b-keykey; b-lchildb-rchildNULL; }else if(keyb-key){ InsertBT(b-lchild,key); }else if(keyb-key){ InsertBT(b-rchild,key); } } BTnode *CreateBT(int A[],int n){ BTnode *btNULL; for(int i0;in;i) InsertBT(bt,A[i]); return bt; } int BTSearch(BTnode *b,int key){ if(bNULL) return 0; printf(%d ,b-key); if(keyb-key) return 1; else if(keyb-key) return BTSearch(b-lchild,key); else return BTSearch(b-rchild,key); }