实验二 二叉排序树的非递归查找算法设计

《实验二 二叉排序树的非递归查找算法设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程名称数据结构实验成绩实验名称二叉排序树的非递归查找算法设计学号B10050812姓名班级B100508日期12.5.8实验目的：熟悉掌握二叉排序树的概念与特点，掌握与应用二叉排序树的查找、插入算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，visualC++6.0实验内容与步骤：1.问题描述设计二叉排序树的非递归查找算法，并利用此算法实现二叉树的插入、生成及查找。2.数据结构类型定义typedefstructnode{KeyTypekey;structnode*lchild,*rchild;}BSTNode,*BSTree;3.模块划分(1).

2、插入二叉排序树:intInsertBST(BSTree*bst,KeyTypek)(2).创建二叉排序树：voidCreateBST(BSTree*bst)(3).中序遍历二叉排序树：voidInOrder(BSTreeroot)(4).查找：BSTreeSearchBST(BSTreebst,KeyTypekey)(5).主函数：voidmain()4.详细设计#include#include#defineENDKEY-1typedefintKeyType;typedefstructnode{KeyTypekey;structnode*lc

3、hild,*rchild;}BSTNode,*BSTree;intInsertBST(BSTree*bst,KeyTypek){BSTreer,s,pre;r=(BSTree)malloc(sizeof(BSTNode));r->key=k;r->lchild=NULL;r->rchild=NULL;if(*bst==NULL){*bst=r;return1;}pre=NULL;s=*bst;while(s){if(k==s->key)return0;elseif(kkey){pre=s;s=s->lchild;}else{pre=s;s=s->rchild;}}if(k

4、key)pre->lchild=r;elsepre->rchild=r;return1;}voidCreateBST(BSTree*bst){KeyTypekey;*bst=NULL;scanf("%d",&key);while(key!=ENDKEY){InsertBST(bst,key);scanf("%d",&key);}getchar();}voidInOrder(BSTreeroot){if(root!=NULL){InOrder(root->lchild);printf("%d",root->key);InOrder(root->rchild);}}BST

5、reeSearchBST(BSTreebst,KeyTypekey){if(!bst)returnNULL;elseif(bst->key==key)returnbst;elseif(bst->key>key)returnSearchBST(bst->lchild,key);elsereturnSearchBST(bst->rchild,key);}voidmain(){BSTreeT;inttag=1;intm,n;printf("建立二叉排序树，请输入序列，以-1结束：");CreateBST(&T);printf("中序遍历二叉排序树,输出序列为:");InOrde

6、r(T);printf("");while(tag!=0){printf("请输入你要查找的元素:");scanf("%d",&n);if(SearchBST(T,n)==NULL)printf("查找失败!#o#");elseprintf("查找成功!^o^由返回地址索引到%d",SearchBST(T,n)->key);printf("是否继续查找按1《是》按0《否》");scanf("%d",&tag);}}1.测试数据及结果实验总结（结论或问题分析）：通过本次试验,对二叉排序树的概念与特点有了更深的理解，并且熟悉掌握了二叉排序树的查找、插入算法，提高了

7、结构化程序设计的能力及程序调试的能力，所设计的程序变得更加合理，可以根据要求实现连续的查找某个节点的功能