1、深 圳 大 学 实 验 报 告课程名称： 数据结构实验与课程设计 实验项目名称： 二叉排序树 学院： 数学与计算科学学院 专业： 数计班 指导教师： 张艳 报告人： 张宏宽 学号： 2013190067 班级： 数计班 实验时间： 2014/12/3 实验报告提交时间： 2014/12/7 教务部制实验目的与要求：实验目的：1、掌握二叉排序树的定义和特性2、掌握二叉排序树的建立方法3、实现二叉排序树的查找技术4、掌握二叉排序树的查找性能实验要求：1、熟悉 C+语言编程2、了解二叉排序树的原理实验内容：二叉排序树定义为：若树不空，则：左子树所有结点的值小于根结点；右子树所有结点的值大于根结点。二
2、叉排序树的中序遍历得到数据的升序排序。实验内容：给定一个关键字序列，生成一个二叉排序树；对给定的关键字进行查找；返回查找是否成功，关键字所在的位置以及查找次数实验过程：（给出算法思想，并附上代码，对代码中的变量和核心语句进行注释）#includeusing namespace std;typedef int Status;static int count;typedef struct BiTNodeint data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree;Status SearchBST(BiTree T,int key,BiTree
3、f,BiTree *p)/寻找count+;if (!T)*p = f;return false;else if (key=T-data)*p = T;return true;else if (keydata)return SearchBST(T-lchild, key, T, p);elsereturn SearchBST(T-rchild,key,T, p);Status InsertBST(BiTree *T, int key)/生成树BiTree p,s;if (!SearchBST(*T, key, NULL, s-data = key;s-lchild = s-rchild = N
4、ULL;if (!p) *T= s;else if (keydata)p-lchild = s; elsep-rchild = s; return true; elsereturn false; Status Inorder(BiTree *T)if(*T)Inorder(if(*T)-data!=NULL)coutdatarchild);return 0;Status Search(BiTree *T, int key)BiTree p;count=0;if (SearchBST(*T, key, NULL, int a10,key10;for(k=0;kn;BiTree T=NULL;fo
5、r(i=0;iai;InsertBST(Inorder(coutm;for(j=0;jkeyj;Search(return 0;实验结果及分析：对数组进行排序并且生成树对给定的关键字进行查找；返回-1 则表示查找是不成功，返回非-1 则表示关键字所在的位置并且返回查找次数深圳大学学生实验报告用纸实验总结：在这次实验中更好的掌握了树的相关知识，更加熟悉了 c+的编程操作，实验中还是出现的问题都将会加深我们对着门课的印象，多动手才会更熟练。指导教师批阅意见：成绩评定：指导教师签字：年 月 日备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后 10 日内。
