二叉排序树实验报告.docx

《二叉排序树实验报告.docx》由会员分享，可在线阅读，更多相关《二叉排序树实验报告.docx（19页珍藏版）》请在三一文库上搜索。

1、二叉排序树的实现实验内容与要求1) 实现二叉排序树，包括生成、插入，删除；2) 对二叉排序树进行先根、中根、和后根非递归遍历；3) 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。二、 实验方案1. 选择链表的方式来构造节点，存储二叉排序树的节点。/ 树的结构struct BSTNode/ 定义左右孩子指针struct BSTNode *lchild,*rchild;/ 节点的关键字TElemType key;int depth=0;/ 定义一个struct BSTNode类型的指针typedef BSTNode *Tree;2. 对树的操作有如下方法：/ 创建二叉排序

2、树Tree CreatTree(Tree T) ；/ 二叉树的深度，返回一个int 值为该树的深度int TreeDepth(Tree T)/ 树状输出二叉树，竖向输出void PrintTree(Tree T , int layer)；/ 查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点Status SearchBST(Tree T , TElemType key , Tree f,Tree &p)；/ 向树中插入节点Status InsertBST(Tree &T , TElemType e) ；/ 删除节点Status Delete(Tree &T)

3、；/ 删除指定节点，调用Delete(Tree &T) 方法Status DeleteData(Tree &T , TElemType key) ；/ 非递归先序遍历void x_print(Tree T);/ 非递归中序遍历Void z_print(Tree T );/ 非递归后序遍历void h_print(Tree T);3. 对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现/ 自定义类型以 SElemType 作为栈中指针返回的值的类型/ 也就是要返回一个节点的指针typedef Tree SElemType;/ 栈的结构struct Stack/

4、栈底指针SElemType *base;/ 栈顶指针SElemType *top;/ 栈的容量int stacksize;4. 栈的操作方法：/ 创建一个空栈Status InitStack(Stack &S)；/ 获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemType &elem)/ 获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem) / 删除栈顶元素Status DeleteTop(Stack &S)/ 往栈中压入数据Status Push(Stack &S,SElemTyp

5、e elem)/ 判断栈是否为空Status IsEmpty(Stack S)三、代码实现#include #include using namespace std;/ 定义宏# define OK 1# define ERROR 0# define STACK_INIT_SIZE 10# define STACK_INCREMENT 2/ 定义宏 分别为栈的初始容量和栈的增加容量# define STACK_INIT_SIZE 10# define STACK_INCREMENT 2 typedef int TElemType;/ 树的结构struct BSTNode/ 定义左右孩子指针st

6、ruct BSTNode *lchild,*rchild;/ 节点的关键字TElemType key;int depth=0;/ 定义一个struct BSTNode 类型的指针typedef BSTNode *Tree;/ 自定义类型以 SElemType 作为栈中指针返回的值的类型/ 也就是要返回一个节点的指针 typedef Tree SElemType;/ 栈的结构struct Stack/ 栈底指针SElemType *base;/ 栈顶指针SElemType *top;/ 栈的容量int stacksize;/ 自定义类型typedef int Status;/ 创建一个空栈Sta

7、tus InitStack(Stack &S)/ 给栈指针分配空间S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);/ 如果分配空间失败则退出if(!S.base)exit(OVERFLOW);/ 栈底、栈顶指针相等表示栈为空/S.base=S.top;/ 此句代码若以如上句格式则在执行时会出现内存非法访问的错误S.top=S.base;/ 初始化栈的容量S.stacksize=STACK_INIT_SIZE;return OK;/ 获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemT

8、ype &elem)if(S.top=S.base) coutgai zhan yi jing wei kong endl; return ERROR; elseelem=*-S.top;return elem;/ 获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem)/ 如果为空栈则返回 ERRORif(S.base=S.top)coutgai zhan yi jing wei kongendl; return ERROR;/ 如果栈不为空则返回栈顶元素elseelem=*(S.top-1); return elem;/ 删

9、除栈顶元素Status DeleteTop(Stack &S)/ 判断栈是否为空if(S.base=S.top)coutgai zhan yi jing wei kong =S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;/ 添加数据*S.top+=elem;return OK;/ 判断栈是否为空S

10、tatus IsEmpty(Stack S) if(S.base=S.top) return OK;elsereturn ERROR;/ 以下的代码主要是对树的操作/ 创建空树Status InitTree(Tree &T) T=NULL;return OK;/ 查找关键字/ 如果关键字存在则返回所在节点的父节点/ 如果关键字不存在则返回叶子所在的节点Status SearchBST(Tree T,TElemType key,Tree f,Tree &p) if(!T)p=f;return ERROR;else if(T-key=key)p=T;return OK;else if(T-keyk

11、ey)return SearchBST(T-lchild,key,T,p);else if(T-keyrchild,key,T,p);/ 向树中插入节点Status InsertBST(Tree &T,TElemType e)Tree p;if(!SearchBST(T,e,NULL,p)Tree s=(Tree)malloc(sizeof(BSTNode);s-key=e;s-lchild=s-rchild=NULL;if(!p)T=s;else if(p-keye) p-lchild=s;else if(p-keyrchild=s;elsereturn ERROR;/ 创建二叉排序树Tre

12、e CreatTree(Tree T) TElemType elem;cout 请输入数据，以0 结束输入操作elem;while(elem!=0 & elem0)int k= InsertBST(T,elem);if(k)cout 请输入数据，以0 结束输入操作elem; else cout 插入错误或存在重复元素lchild!=NULL & T-rchild!=NULL)p=T;q=T-lchild;T=q;while(q-rchild!=NULL)q=q-rchild;q-rchild=p-rchild;free(p);return OK;if(T-rchild=NULL & T-lch

13、ild!=NULL)p=T;T=T-lchild;free(p);return OK;else if(T-lchild=NULL & T-rchild!=NULL)p=T;T=T-rchild;free(p);return OK;else if(T-rchild=NULL & T-lchild=NULL)T=NULL;free(T);return OK;/ 删除指定节点Status DeleteData(Tree &T,TElemType key)if(!T)cout 找不到要删除的元素，请重新选择!key=key)Delete(T);else if(T-keykey)DeleteData(T

14、-lchild,key);else if(T-keyrchild,key);return OK;/ 先序遍历void x_print(Tree T)/Tree f;Stack S;InitStack(S);if(T=NULL)cout 树为空 endl;while(T!=NULL | !IsEmpty(S) if(T!=NULL)coutkeylchild; elsePop(S,T); T=T-rchild;/z 中序遍历void z_print(Tree T )/ Tree f;Stack S;InitStack(S);if(T=NULL)cout 树为空 lchild; elsePop(S

15、,T); coutkeyrchild;/ 后序遍历void h_print(Tree T)Stack S;InitStack(S);Tree f=NULL;if(T=NULL)cout 树为空 lchild;getTop(S,T);if(T-rchild=NULL | T-rchild=f) coutkeyrchild;/ 二叉树的深度int TreeDepth(Tree T)int left,right,max;if(T!=NULL)left=TreeDepth(T-lchild);right=TreeDepth(T-rchild);max=leftright?left:right;retu

16、rn max+1;elsereturn ERROR;/ 竖向输出/ 树状输出二叉树void PrintTree(Tree T,int layer)int k;if(T=NULL)return ;PrintTree(T-rchild,layer+1);for(k=0;klayer;k+) cout ;coutkeylchild,layer+1);void main() int key;int h;Tree tree;InitTree(tree);tree=CreatTree(tree);h=TreeDepth(tree);cout 树状输出为：endl;PrintTree(tree,h);if(

17、!tree)exit(-1);coutnn 请nendl;couta. 删除二叉树中的元素b.coutc. 先根遍历二叉树d.coute. 后根遍历二叉树o.输入你要选择的操作coutnn向二叉树中添加元素endl;中根遍历二叉树endl;退出操作endl;nselect;while(select!=o)switch(select)case o:exit(0);break;case a:if(!tree)cout 树以为空，请重新选择操作!select;elsecout 请输入要删除的元素key;DeleteData(tree,key);cout 树状输出为：endl;PrintTree(tr

18、ee,h);break;case b:cout 请输入要插入的元素key;InsertBST(tree,key);cout 树状输出为：endl;PrintTree(tree,h);break;case c:cout 先根遍历结果为：endl;x_print(tree);coutendl;break;case d:cout 中根遍历结果为：endl;z_print(tree);coutendl;break;case e:cout 后根遍历结果为：endl;h_print(tree);coutendl;break;default:cout 输入错误endl;exit(-1);break;cout

19、 请输入你要选择的操作 endl;couta.删除二叉树中的元素 b.向二叉树中添加元素 endl;coutc.先根遍历二叉树 d.中根遍历二叉树endl;coute.后根遍历二叉树 o. 退出操作 endl;coutselect;四、实验结果和数据处理T:vc-hc-r4-MSD ev9 BMy P reject 凯写 huj uj i ego u匚请输入数据，以结束输入操作詈输入数揖以马结束输入操作32请输入数据，以囱结束输入操作22请输入数据，以0结束输入操作49请输入数据，以旧结束输入操作39请输入数据，以结束输入操作80请输入数据，以国结束输入操作青输入数据,以0结束输入操作0树状输

20、出为二88904945393222D:vc+c+MSDev98MyProject5shujujiegouDebugshujujiegou.exeI请输入你要选择的操作，型脍三叉树中典元素h .向厂区树中添加元素，.羌迪福历二叉树d.出根厚近二叉树6.后他道历二叉树。.盅出藻柞 蓍输入要删除的元素22树状输出为；888049453932ace-r的M 中叉叉 一树二二 一叉历历 一二鬻 .除强 一里后一中二 操叉禹 的二电 择向黑 过b 口。请输入要插入的元素50树状输出为：8880504?453932一加树 一受 一生一 前叉覆 用向濯 词b.d.o.T的-中叉叉 一树三一一 E4s 历 -1

21、 一除 一里后先根遍历结果为， 45 32 39 49 80 50 88素 元一中二 操叉量 的二事 选b.d.O. 要 你T的、 中叉叉 i三 一叉历历 一二米通除禧 里后中根遍历结果为，32 39 45 49 50 80 88一加树 一添叉 一中二 梯艾福 的二畲 择向强 石一 一 a 上b d 口中X叉 树二二 叉历历 -S 除强里后输入数据同选择操作结果如上图所示操作现象：输入操作的时候如果输入的不是数值（比如字母）就会出现插入操作错误的提示，然后异常退出操作；或者当输入的关键字已在树中存在，也会提示“重复输 入”然后异常退出（这点存在不足，应该修改为提示之后重新输入操作）删除现象：如果要删除的关键字不存在则会提示不存在该关键字然后重新输入，如果树为空则会提示树为空并重新选择操作遍历现象：如果树为空，则不会退出操作，而是提示“树为空”。选择操作：如果不是按要求输入字符a,b,c,d,e,o 则会提示输入错误并异常退出；注：对于树的一些删除、增加、遍历操作的详细文字解释省略。参考文献：数据结构算法实现及解析西安电子科技大学出版社出版严蔚敏 吴伟民编著数据结构（c语言版） 清华大学出版社严蔚敏 吴伟民编著