二叉排序树实验报告

《二叉排序树实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：二叉排序树实验学院：计算机与软件学院专业：指导教师：报告人：学号：班级：3班实验时间：2012-11-28实验报告提交时间：2012-12-5教务部制实验目的与要求：实验目的：掌握二叉排序树的定义和特性掌握二叉排序树的建立方法实现二叉排序树的查找技术掌握二叉排序树的查找功能实验要求：熟悉C++语言编程了解二叉排序树的原理方法、步骤：1、问题描述给定一个关键字序列，生成一个二叉排序树；并对给定的关键字进行查找；返回查找是否成功，关键字所在的位置以及查找次数。2、算法给定值与根结点比较：⑴、若相等，查找成功⑵、若小于，查找左子树

2、；如果左子树为空，作插入操作；⑶、若大于，查找右子树；如果右子树为空，作插入操作。实验过程及内容：Description1、问题描述给定一个关键字序列，生成一个二叉排序树；并对给定的关键字进行查找；返回查找是否成功，关键字所在的位置以及查找次数。2、算法给定值与根结点比较：⑴、若相等，查找成功⑵、若小于，查找左子树；如果左子树为空，作插入操作；⑶、若大于，查找右子树；如果右子树为空，作插入操作。Input第一行：测试次数。每个样本分2行：第1行：第一个数字m表示样本数目，其后跟m个样本；第2行：查找的关键字的值。Output查找是否成功（1—表示成功，0表示不成功），所在位置（在BisC

3、ount层中的第几个位置（以完全二叉树为准，根结点为1结点）），查找次数（相当于树的层数）。SampleInput2524357462684317SampleOutput122074数据处理分析：程序代码：#includeusingnamespacestd;structBiNode{intdata;BiNode*lChild,*rChild;};classBiSortTree{public:voidCreateBST(int*,int);voidSearchBST(int);intBisSuccess;intBisPos;intBisCount;private:BiN

4、ode*root;BiNode*GetNode(int);voidSearchNode(BiNode*,int);voidInsertNode(BiNode*,BiNode*);};voidBiSortTree::CreateBST(int*r,intn)//GreateBST{inti;root=NULL;BiNode*s;for(i=0;i

5、{if(root->data>s->data){if(root->lChild)InsertNode(root->lChild,s);elseroot->lChild=s;}else{if(root->rChild)InsertNode(root->rChild,s);elseroot->rChild=s;}}BiNode*BiSortTree::GetNode(intk)//GetNode{BiNode*s=newBiNode;s->data=k;s->lChild=NULL;s->rChild=NULL;returns;}voidBiSortTree::SearchBST(intk)

6、//SearchBST{BisCount=0;BisPos=1;BisSuccess=0;if(root)SearchNode(root,k);}voidBiSortTree::SearchNode(BiNode*root,intk)//SearchNode{BiNode*NextBiNode;BisCount++;if(root->data==k){BisSuccess=1;return;}else{if(root->data>k){BisPos=2*BisPos-1;NextBiNode=root->lChild;}else{BisPos=2*BisPos;NextBiNode=ro

7、ot->rChild;}}if(NextBiNode)SearchNode(NextBiNode,k);else{BisSuccess=0;BisCount++;if(root->data>k)root->lChild=GetNode(k);elseroot->rChild=GetNode(k);}}intmain(intargc,char*argv[]){intt[32];inti,j,Key;intTestNum,SampleN