二叉排序树的基本运算试验报告

本文格式为Word版，下载可任意编辑——二叉排序树的基本运算试验报告

软件技术基础试验七

二叉排序树的基本运算

班级：电信0901

学号：0703090106

姓名：蒋玮珂

试验七二叉排序树的基本运算

（1）试验题目：

编写一个程序，实现二叉排序树运算,在此基础上设计一个主程序完成如下功能

(1)由指定集合创立一棵二叉排序树bt,并以括号表示法输出(2)判断bt是否是一棵二叉树

(3)采用非递归方法查找指定关键字的结点,并输出查找路径

（2）试验目的：

1、把握二叉排序树的数据类型描述及特点。2、把握二叉排序树的存储结构的建立算法。

3、把握二叉排序树的基本运算的实现，例如：查找，排序等。

（3）调试通过并正确执行给定功能要求的试验代码

#include\#include#include#includetypedefintKeyType;intCount=0;

typedefstructtnode{

KeyTypekey;

structtnode*lchild,*rchild;}BSTNode;//定义二叉排序树

BSTNode*BSTSearch(BSTNode*bt,KeyTypek)//非递归查找算法{

BSTNode*p=bt;

while(p!=NULL//沿左子树查找else

p=p->rchild;//沿右子树查找}

return(p);}

BSTNode*SearchBST(BSTNode*bt,KeyTypek,FILE*fp2){

BSTNode*p=bt;intflag=0;

while(p!=NULL)//二叉排序树不为空

{

if(p->key==k)//查找成功

{fprintf(fp2,\flag=1;break;}

if(kkey)//查找不成功，到下一层继续查找{fprintf(fp2,\fputs(\p=p->lchild;}//查找左子树else

{fprintf(fp2,\fputs(\p=p->rchild;}//查找右子树}

if(flag==0)

{fputs(\找不到值为k的结点：\\n\p=NULL;}returnp;}

intInsertBST(BSTNode*while(p!=NULL){

if(p->key==k)return(0);

f=p;//查找过程中，f指向*p的父结点if(p->key>k)

p=p->lchild;//在左子树中查找else

p=p->rchild;//在右子树中查找}

p=newBSTNode;//建立新结点p->key=k;

p->lchild=p->rchild=NULL;

if(bt==NULL)//原树为空时,*p作为根结点插入bt=p;

elseif(kkey)

f->lchild=p;//插入*p作为*f的左孩子else

f->rchild=p;//插入*p作为*f的右孩子return(1);}

voidCreateBST(BSTNode*//设置二叉排序树的初态为空inti=0;while(ilchild,b);b[Count++]=t->key;inorder(t->rchild,b);}}

voidBSTdisp(BSTNode*bt,FILE*fp2){

if(bt!=NULL)

{fprintf(fp2,\

if(bt->lchild!=NULL||bt->rchild!=NULL){putc('(',fp2);

BSTdisp(bt->lchild,fp2);if(bt->rchild!=NULL)putc(',',fp2);

BSTdisp(bt->rchild,fp2);putc(')',fp2);}}}

voidmain(){

intn,k,b[100],a[200];boolflag=false;BSTNode*bt=NULL;

FILE*fp,*fp1,*fp2,*fp3;

fp=fopen(\读入元素个数nfscanf(fp,\

fp1=fopen(\读入结点数据for(inti=0;ib[i+1])flag=true;}

if(flag)

fputs(\该二叉树不是二叉排序树!\\n\else

fputs(\该二叉树是二叉排序树!\\n\

fp3=fopen(\读入要查找的元素kfscanf(fp3,\

fprintf(fp2,\非递归查找路径如下：\\n\SearchBST(bt,