文档介绍：系别
计算机系
班级
B104
学号
B6
姓名
课程名称
数据结构
实验日期
实验名称
二叉排序树的非递归查找算法设计
成绩
实验目的:
熟悉掌握二叉排序树的概念与特点,掌握与应用二叉排序树的查找、插入算法,训练和提高结构化程序设计能力及程序调试能力。
实验条件:
计算机一台,Visual C++
实验内容:
【问题描述】
利用二叉排序树的非递归查找算法实现二叉树的插入、生成及查找,对二叉排序树进行中序遍历,输出中序遍历序列。
程序代码:
#include <>
#include <>
typedef struct node
{
int key ;
struct node *lchild,*rchild;
}BSTNode, *BSTree;
int InsertBST(BSTree *bst, int k) //插入函数
{
BSTree r,s,pre;
r=(BSTree)malloc(sizeof(BSTNode));
r->key=k;
r->lchild=NULL;
r->rchild=NULL;
if (*bst == NULL)
{
*bst=r;
return 1;
}
pre=NULL;
s=*bst;
while(s)
{
if(k==s->key)
return 0;
else
if(k<s->key) //插入左子树
{
pre=s;
s=s->lchild;
}
else
{
pre=s;
s=s->rchild; // 插入右子树
}
}
if(k<pre->key)
pre->lchild=r;
else
pre->rchild=r;
return 1;
}
void CreateBST(BSTree *bst)
{
int key;
*bst=NULL;
scanf("%d", &key);
while (key!=-1)
{
InsertBST(bst, key); // 插入结点Key
scanf("%d", &key);
}
}
void InOrder(BSTree root) //中序遍历
{
if (root!=NULL)
{
InOrder(root->lchild);
printf("%d ",root->key);
InOrder(root->rchild);
}
}
BSTree SearchBST(BSTree bst, int key)
{
BSTree q;
q=bst;
while(q)
{
if (q->key==key)
return q; //查找成功
if(q->key>key)
q