《二叉排序树实验报告》由会员分享，可在线阅读，更多相关《二叉排序树实验报告（19页珍藏版）》请在金锄头文库上搜索。
1、二叉排序树的实现一、实验内容与要求1) 实现二叉排序树，包括生成、插入，删除；2) 对二叉排序树进行先根、中根、和后根非递归遍历；3) 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。二、实验方案1. 选择链表的方式来构造节点，存储二叉排序树的节点/树的结构structBSTNode/定义左右孩子指针structBSTNode*lchild,*rchild;/节点的关键字TElemTypekey;intdepth=0;/定义一个structBSTNode类型的指针typedefBSTNode*Tree;2. 对树的操作有如下方法：/创建二叉排序树TreeCreatTre
2、e(TreeT)；二叉树的深度，返回一个int值为该树的深度intTreeDepth(TreeT)/树状输出二叉树，竖向输出voidPrintTree(TreeT,intlayer)；/查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点StatusSearchBST(TreeT,TElemTypekey,Treef,Tree&p)；/向树中插入节点StatusInsertBST(Tree&T,TElemTypee)；/删除节点StatusDelete(Tree&T)；删除指定节点，调用Delete(Tree&T)方法StatusDeleteData(Tree
3、&T,TElemTypekey)；/非递归先序遍历voidx_print(TreeT);/非递归中序遍历Voidz_print(TreeT);/非递归后序遍历voidh_print(TreeT);3. 对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现/自定义类型以SElemType作为栈中指针返回的值的类型/也就是要返回一个节点的指针typedefTreeSElemType;/栈的结构structStack/栈底指针SElemType*base;/栈顶指针SElemType*top;/栈的容量intstacksize;4. 栈的操作方法：/创建一个空栈Sta
4、tusInitStack(Stack&S)；/获取栈顶元素并删除栈中该位置的元素SElemTypePop(Stack&S,SElemType&elem)/获取栈顶元素返回栈顶元素不对栈做任何修改SElemTypegetTop(StackS,SElemType&elem)/删除栈顶元素StatusDeleteTop(Stack&S)/往栈中压入数据StatusPush(Stack&S,SElemTypeelem)/判断栈是否为空StatusIsEmpty(StackS)三、代码实现#include#includeusingnamespacestd;/定义宏#defineOK1#defineERR
5、OR0#defineSTACK_INIT_SIZE10#defineSTACK_INCREMENT2/定义宏分别为栈的初始容量和栈的增加容量#defineSTACK_INIT_SIZE10#defineSTACK_INCREMENT2typedefintTElemType;/树的结构structBSTNode/定义左右孩子指针structBSTNode*lchild,*rchild;/节点的关键字TElemTypekey;intdepth=0;/定义一个structBSTNode类型的指针typedefBSTNode*Tree;/自定义类型以SElemType作为栈中指针返回的值的类型/也就是
6、要返回一个节点的指针typedefTreeSElemType;/栈的结构structStack/栈底指针SElemType*base;/栈顶指针SElemType*top;/栈的容量intstacksize;/自定义类型typedefintStatus;/创建一个空栈StatusInitStack(Stack&S)/给栈指针分配空间S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);/如果分配空间失败则退出if(!S.base)exit(OVERFLOW);/栈底、栈顶指针相等表示栈为空/S.base=S.top;/此句代码若
7、以如上句格式则在执行时会出现内存非法访问的错误S.top=S.base;/初始化栈的容量S.stacksize=STACK_INIT_SIZE;returnOK;/获取栈顶元素并删除栈中该位置的元素SElemTypePop(Stack&S,SElemType&elem)if(S.top=S.base)coutgaizhanyijingweikongendl;returnERROR;elseelem=*-S.top;returnelem;/获取栈顶元素返回栈顶元素不对栈做任何修改SElemTypegetTop(StackS,SElemType&elem)/如果为空栈则返回ERRORif(S.ba
8、se=S.top)coutgaizhanyijingweikongendl;returnERROR;/如果栈不为空则返回栈顶元素elseelem=*(S.top-1);returnelem;/删除栈顶元素StatusDeleteTop(Stack&S)/判断栈是否为空if(S.base=S.top)coutgaizhanyijingweikong=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top
9、=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;/添加数据*S.top+=elem;returnOK;/判断栈是否为空StatusIsEmpty(StackS)if(S.base=S.top)returnOK;elsereturnERROR;/以下的代码主要是对树的操作/创建空树StatusInitTree(Tree&T)T=NULL;returnOK;/查找关键字/如果关键字存在则返回所在节点的父节点/如果关键字不存在则返回叶子所在的节点StatusSearchBST(TreeT,TElemTypekey,Treef,Tree&p)if(!T
10、)p=f;returnERROR;elseif(T-key=key)p=T;returnOK;elseif(T-keykey)returnSearchBST(T-lchild,key,T,p);elseif(T-keyrchild,key,T,p);/向树中插入节点StatusInsertBST(Tree&T,TElemTypee)Treep;if(!SearchBST(T,e,NULL,p)Trees=(Tree)malloc(sizeof(BSTNode);s-key=e;s-lchild=s-rchild=NULL;if(!p)T=s;elseif(p-keye)p-lchild=s;e
11、lseif(p-keyrchild=s;elsereturnERROR;/创建二叉排序树TreeCreatTree(TreeT)TElemTypeelem;coutvv请输入数据，以0结束输入操作vvendl;cinelem;while(elem!=0&elem0)intk=InsertBST(T,elem);if(k)coutvv请输入数据，以0结束输入操作vvendl;cinelem;elsecoutvv插入错误或存在重复元素vvendl;/异常退出returnERROR;returnT;/删除节点StatusDelete(Tree&T)Treep,q;if(T-lchild!=NULL&
12、T-rchild!=NULL)p=T;q=T-lchild;T=q;while(q-rchild!=NULL)q=q-rchild;q-rchild=p-rchild;free(p);returnOK;if(T-rchild=NULL&T-lchild!=NULL)p=T;T=T-lchild;free(p);returnOK;elseif(T-lchild=NULL&T-rchild!=NULL)p=T;T=T-rchild;free(p);returnOK;elseif(T-rchild=NULL&T-lchild=NULL)T=NULL;free(T);returnOK;/删除指定节点StatusDeleteData(Tree&T,TElemTypekey)if(!T)coutvv找不到要删除的元素，请重新选择!vvendl;returnERROR;if(T-key=key)Delete(T);elseif(T-keykey)DeleteData(T-lchild,key);elseif(T-keyrchild,key);returnOK;/先序遍历voidx_print(TreeT)/Treef;StackS;InitStack(S);if(T=NULL)coutvv树为空vven
