/************************************************************* 二叉排序树的查找 实现文件 更新于2020年7月5日 **************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "search.h" BiTree Search_BST(BiTree T, KeyType key, BiTNode **parent) {/*在二叉排序树T上查找其关键字等于key的记录结点。若找到返回该结点指针，parent指向其双亲；否则返回空指针，parent指向访问路径上最后一个结点。*/ // 请在这里补充代码，完成本关任务 /********** Begin *********/ /********** End **********/ } void Insert_BST(BiTree *T, RedType r)/*若二叉排序树T中没有关键字为r.key的记录，则插入*/ { BiTNode *p,*q,*parent; parent=NULL; p=Search_BST(*T,r.key,&parent); /*查找*/ if(p) printf("BST中有结点r，无需插入\n"); else { p=parent; q=(BiTNode *)malloc(sizeof(BiTNode)); q->data=r; q->lchild=q->rchild=NULL; if(*T==NULL) *T=q; /*若T为空，则q为新的根*/ else if(r.key<p->data.key) p->lchild=q; else p->rchild=q; } } BiTree Create_BST( ) /*二叉排序树的构造*/ {/*输入若干记录的关键字（以-1标志结束），生成一棵BST，采用二叉链表存储，返回其根指针T*/ BiTree T; RedType r; T=NULL; /*建空树*/ scanf("%d",&r.key); while(r.key!=-1) { Insert_BST(&T, r); scanf("%d",&r.key); } return T; } void PreOrder(BiTree bt) /*先序遍历*/ { if(bt) { printf("%d ",bt->data.key); PreOrder(bt->lchild); PreOrder(bt->rchild); } } void InOrder(BiTree bt) /*中序遍历*/ { if(bt) { InOrder(bt->lchild); printf("%d ",bt->data.key); InOrder(bt->rchild); } }

这段代码是实现二叉排序树的查找和插入操作的。具体来说，其中的函数Search_BST实现在一棵二叉排序树中查找指定关键字的节点，并返回该节点的指针以及其父节点的指针；Insert_BST函数实现向一棵二叉排序树中插入一个新节点；Create_BST函数实现根据输入的关键字生成一棵二叉排序树；PreOrder和InOrder函数分别实现先序遍历和中序遍历二叉排序树。