二叉排序树的查找实验报告.docx

二叉排序树的查找实验报告 　　附件　　深圳大学实验报告　　课程名称：　　学院：计算机与软件学院　　实验时间：　　实验报告提交时间：　　教务处制　　二叉排序树的实现　　一、实验内容与要求　　1）实现二叉排序树，包括生成、插入，删除；　　2）对二叉排序树进行先根、中根、和后根非递归遍历；　　3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。　　二、实验方案　　1.选择链表的方式来构造节点，存储二叉排序树的节点。　　//树的结构　　structBSTNode　　{　　//定义左右孩子指针　　structBSTNode*lchild,*rchild;　　//节点的关键字　　TElemTypekey;　　};　　intdepth=0;　　//定义一个structBSTNode类型的指针　　typedefBSTNode*Tree;　　2.对树的操作有如下方法：　　//创建二叉排序树　　TreeCreatTree(TreeT)；　　//二叉树的深度，返回一个int值为该树的深度　　intTreeDepth(TreeT)　　//树状输出二叉树，竖向输出　　voidPrintTree(TreeT,intlayer)；　　//查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点　　StatusSearchBST(TreeT,TElemTypekey,Treef,Treep)；　　//向树中插入节点　　StatusInsertBST(TreeT,TElemTypee)；　　//删除节点　　StatusDelete(TreeT)；　　//删除指定节点，调用Delete(TreeT)方法　　StatusDeleteData(TreeT,TElemTypekey)；　　//非递归先序遍历　　voidx_print(TreeT);　　//非递归中序遍历　　Voidz_print(TreeT);　　//非递归后序遍历　　voidh_print(TreeT);　　3.对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现　　//自定义类型以SElemType作为栈中指针返回的值的类型　　//也就是要返回一个节点的指针　　typedefTreeSElemType;　　//栈的结构　　structStack　　{　　//栈底指针　　SElemType*base;　　//栈顶指针　　SElemType*top;　　//栈的容量　　intstacksize;　　};　　4.栈的操作方法：　　//创建一个空栈　　StatusInitStack(StackS)；　　//获取栈顶元素并删除栈中该位置的元素　　SElemTypePop(StackS,SElemTypeelem)　　//获取栈顶元素返回栈顶元素不对栈做任何修改　　SElemTypegetTop(StackS,SElemTypeelem)　　//删除栈顶元素　　StatusDeleteTop(StackS)　　//往栈中压入数据　　StatusPush(StackS,SElemTypeelem)　　//判断栈是否为空　　StatusIsEmpty(StackS)　　三、代码实现　　#include　　#include　　usingnamespacestd;　　//定义宏　　#defineOK1　　#defineERROR0　　#defineSTACK_INIT_SIZE10　　#defineSTACK_INCREMENT2　　//定义宏分别为栈的初始容量和栈的增加容量　　#defineSTACK_INIT_SIZE10　　#defineSTACK_INCREMENT2(转载于:写论文网:二叉排序树的查找实验报告)　　typedefintTElemType;　　//树的结构　　structBSTNode　　{　　//定义左右孩子指针　　structBSTNode*lchild,*rchild;　　//节点的关键字　　TElemTypekey;　　};　　intdepth=0;　　//定义一个structBSTNode类型的指针　　typedefBSTNode*Tree;　　//自定义类型以SElemType作为栈中指针返回的值的类型　　//也就是要返回一个节点的指针　　typedefTreeSElemType;　　//栈的结构　　structStack　　{　　//栈底指针　　SElemType*base;　　//栈