实验三二叉排序树的建立和查找
一、实验目的
1．掌握二叉排序树的建立算法
2．掌握二叉排序树查找算法。

二、实验环境
操作系统和C语言系统
三、预习要求
复习二叉排序树的生成及查找算法，编写完整的程序。

四、实验内容
实现二叉排序树上的查找算法。

具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。

五、参考算法
#include <stdio.h>
#include <stdlib.h>
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(key<T->key)
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key); /*继续在右子树中查找*/
}
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->key<key)
p=q->rchild;
else
{
printf("\n 该二叉排序树中含有关键字为%d的节点!\n",key);
return;
}
}
p=(BSTree)malloc(sizeof(BSTNode));
p->key=key;
p->lchild=p->rchild=NULL;
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!=NULL)
{
printf("(");
ListBinTree(T->lchild);
if(T->rchild!=NULL)
printf(",");
ListBinTree(T->rchild);
printf(")");
}
}
}
void main()
{
BSTNode *SearchBST(BSTree T,KeyType key);
void InsertBST(BSTree *Tptr,KeyType key);
BSTree CreateBST();
void ListBinTree(BSTree T);
BSTree T;
BSTNode *p;
int key;
printf("请输入关键字（输入0为结束标志）：\n");
T=CreateBST();
ListBinTree(T);
printf("\n");
printf("请输入欲查找关键字:");
scanf("%d",&key);
p=SearchBST(T,key);
if(p==NULL)
printf("没有找到%d！\n",key);
else
printf("找到%d！\n",key);
ListBinTree(p);
printf("\n");
}
实验中出现的问题及对问题的解决方案
输入数据时，总是不能得到结果，原因是在建立二叉树函数定义中，是对指针的值进行了修改。

解决方案：用指向指针的指针。

其次，实验中经常会出现前后字符不一致的情况，主要原因是自己在编程时比较马虎，遇到比较长的程序，就容易出错。

可以通过评审多加练习，仔细认真检查自己是否出现错误。

同时在类似(*T)->key=key的语句中，括号没加，程序无法运行。

解决方案同上一条。

六、思考题
请思考采用其他存储结构实现的二叉排序树建立算法。

用下列程序代替源程序中的相应部分。

void InsertBST(BSTree *Tptr,KeyType key)
{
BSTBode *f,*p=*Tptr;
while(p)
{
if(p->key==key)
return;
f=p;
p=(key<p->key)?p->lchild:p->rchild;
}
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=key;
p->lchild=p->rchild=NULL;
if(*Tptr==NULL)
*Tptr=pp;
else
if(key<f->key)
f->lchild=p;
else
f->rchild=p;
}
BSTree CreateBST(void)
{
BSTree T=NULL;
KeyType key;
scanf("%d",&key);
while(key)
{
InsertBST(&T,key);
scanf("%d",&key);
}
return T;
}
七、实验总结
在开始编程时，不知道从何入手，自己在上课听讲了，也听懂了。

在编程是想自己独立完成，但看到要求之后突然感觉很迷茫，不得已借鉴了老师提供的代码。

其中有诸多原因，首先自己在编程经验上严重欠缺，这使得自己在接到一道题时无从下手，另外对二叉排序树的理解不够深入，所以编程都是建立在对其算法结构有深入理解的基础上的。

而且听懂不意味着理解，只有在自己亲自编程的时间过程中，才能逐渐加深理解。

自己C语言的底子不够厚实，今后要加强C语言知识的理论学习，系统地掌握C语言。

这样才能给实践提供良好的理论基础。