二叉排序树实验.doc

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