1 一、上机实验的问题和要求： 复习二叉排序树的生成及查找算法，编写完整的程序。 实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。 二、源程序及注释： #include #include typedef int InfoType; typedef int KeyType; //假定关键字类型为整数 typedef struct node //结点类型 { KeyType key; //关键字项 InfoType otherinfo; //其它数据域，InfoType 视应用情况而定 下面不处理它 struct node *lchild,*rchild;//左右孩子指针 } BSTNode; typedef BSTNode *BSTree; //BSTree 是二叉排序树的类型 BSTNode *SearchBST(BSTree T,KeyType key) { //在二叉排序树 T 上查找关键字为 key的结点，成功时返回该结点位置，否则返回 NULL if(T==NULL||key==T->key) //递归的终结条件 return T; //若 T 为空，查找失败；否则成功，返回找到的结点位置 if(keykey) return SearchBST(T->lchild,key); else return SearchBST(T->rchild,key); //继续在右子树中查找 2 } void InsertBST(BSTree *T,int key) { //插入一个值为 key 的节点到二叉排序树中 BSTNode *p,*q; if((*T)==NULL) { //树为空树 (*T)=(BSTree)malloc(sizeof(BSTNode)); (*T)->key=key; (*T)->lchild=(*T)->rchild=NULL; } else { p=(*T); while(p) { q=p; if(p->key>key) p=q->lchild; else if(p->keyrchild; else { printf("\n 该二叉排序树中含有关键字为%d 的节点!\n",key); return; } } p=(BSTree)malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; 3 if(q->key>key) q->lchild=p; else q->rchild=p; } } BSTree CreateBST(void) { //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回 BSTree T=NULL; //初始时 T 为空树 KeyType key; scanf("%d",&key); //读入一个关键字 while(key) { //假设 key=0 是输入结束标志 InsertBST(&T,key); //将 key 插入二叉排序树 T scanf("%d",&key); //读入下一关键字 } return T; //返回建立的二叉排序树的根指针 } void ListBinTree(BSTree T) //用广义表表示二叉树 { if (T!=NULL) { printf("%d",T->key); if (T->lchild!=NULL||T->rchild!...
