二叉排序树实验报告.doc

二叉排序树的实现一、 实验内容与要求 1） 实现二叉排序树，包括生成、插入，删除；2） 对二叉排序树进行先根、中根、和后根非递归遍历；3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 二、 实验方案 1.选择链表的方式来构造节点，存储二叉排序树的节点。/树的结构struct BSTNode/定义左右孩子指针struct BSTNode *lchild,*rchild;/节点的关键字TElemType key;int depth=0;/定义一个 struct BSTNode 类型的指针typedef BSTNode *Tree;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)；/删除指定节点，调用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/栈底指针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,SElemType 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 2typedef int TElemType;/树的结构struct BSTNode/定义左右孩子指针struct 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;/创建一个空栈Status 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,SElemType &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;/删除栈顶元素 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;/判断栈是否为空Status IsEmpty(Stack S)if(S.base=S.top)return OK;else return 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-keykey)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;/ 创建二叉排序树Tree 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-lchild!=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-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,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;return 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(!tree)exit(-1);coutnn-请输入你要选择的操作-nendl; couta.删除二叉树中的元素 b.向二叉树中添加元素endl;coutc.先根遍历二叉树 d.中根遍历二叉树 endl;coute.后根遍历二叉树 o.退出操作 endl;coutnn-nselect;while(select!=o)switch(select)case o:exit(0);break;case a:if(!tree)cout树以为空，请重新选择操作!select;else cout请输入要删除的元素key; DeleteData(tree,key);cout树状输出为：endl;PrintTree(tree,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-请输入你要选择的操作-endl; couta.删除二叉树中的元素 b.向二叉树中添加元素endl; coutc.先根遍历二叉树 d.中根遍历二叉树 endl; coute.后根遍历二叉树 o.退出操作 endl; cout-select;四、实验结果和数据处理 输入数据同选择操作结果如上图所示操作现象：输入操作的时候 如果输入的不是数值（比如字母）就会出现插入操作错误的