二叉排序树的创建、删除、插入等操作及二杈线索存储表示

武 汉 工 程 大 学计算机科学与工程学院数据结构实验报告专业班级09计算机工程01实验地点419学生学号0905080116指导教师蔡琼学生姓名沈亮实验时间实验项目查找技术综合应用实验类别操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ）实验目的及要求（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决比较简单的实际问题。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明： 评阅教师： 日 期： 年 月 日实验内容：二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;二叉排序树插入算法伪代码如下：1. 若root是空树，则将结点s作为根结点插入；否则2. 若s-dataroot-data，则把结点s插入到root的左子树中；否则3. 把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1. 若结点p是叶子，则直接删除结点p； 2. 若结点p只有左子树，则只需重接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 3. 若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删除结点s；1.实验分析：程序的主要流程图： 否是开始建树： 依次输入n个关键字 插入二叉排序树中 中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束主要模块： 1）主函数模块 Main()建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于 key2 的数据元素；2）创建二叉排序树模块BiTree CreatBST(int n)建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用InsertBST1（插入函数）； 返回根结点T； 输出过程； 3）删除模块DeleteNode(BiTree &T, int x)从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能； 4）插入模块void InsertBST1(BiTree &T,BiTNode *s)在二叉树排序树T中，插入一个结点s(递归算法)； 被CreatBST函数调用； 5）查找模块BiTree searchBST1(BiTree T,TElemType key)在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据元素结点的指针； 否则返回空指针；2.源程序代码：#includeusing namespace std;typedef int KeyType;typedef struct tree/声明树的结构 struct tree *left; /存放左子树的指针struct tree *right; /存放又子树的指针KeyType key; /存放节点的内容 BSTNode, * BSTree; /声明二叉树的链表BSTree insertBST(BSTree tptr,KeyType key)/ 在二叉排序树中插入结点 /若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回BSTree f,p=tptr; /p的初值指向根结点while(p) /查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲if(p-key=key) /树中已有key，无须插入return tptr;f=p; /f保存当前查找的结点，即f是p的双亲p=(keykey)?p-left:p-right; p=(BSTree )malloc(sizeof(BSTNode); /生成新结点p-key=key; p-left=p-right=NULL;if(tptr=NULL) /原树为空，新插入的结点为新的根tptr=p;elseif(keykey)f-left=p;elsef-right=p;return tptr;BSTree createBST()/建立二叉树 BSTree t=NULL; /根结点KeyType key;cinkey;while(key!=-1)t=insertBST(t,key);cinkey;return t;void inorder_btree(BSTree root)/ 中序遍历打印二叉排序树BSTree p=root;if(p!=NULL) inorder_btree(p-left );cout keyright );int searchBST(BSTree t,KeyType key)/查找if(key=t-key)return 1;if(t=NULL)return 0;if(keykey)return searchBST(t-left,key);elsereturn searchBST(t-right,key);BSTree deleteBST(BSTree tptr,KeyType key)/删除 BSTree p,tmp,parent=NULL; p=tptr; while(p) if(p-key=key) break; parent=p; p=(keykey)?p-left:p-right; if(!p) return NULL; tmp=p; if(!p-right&!p-left) /*p的左右子树都为空*/ if(!parent) /要删根，须修改根指针 tptr=NULL; else if(p=parent-right) parent-right=NULL; else parent-left=NULL; free(p); else if(!p-right) /p的右子树为空，则重接p的左子树 p=p-left; if(!parent) /要删根，须修改根指针 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(!p-left) /的左子树为空，则重接p的左子树 p=p-right; if(!parent) /要删根，须修改根指针 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(p-right&p-left) /p有左子树和右子树，用p的后继覆盖p然后删去后继 /另有方法：用p的前驱覆盖p然后删去前驱|合并p的左右子树 parent=p; /由于用覆盖法删根，则不必特殊考虑删根 p=p-right; while(p-left) parent=p; p=p-left; tmp-key=p-key; if(p=parent-left) parent-left=NULL; else parent-right=NULL; free(p); return tptr;int main()KeyType key;int flag,test;char cmd;BSTree root;docoutnnendl;couttt*请选择你要执行的操作:*endl;coutnendl;couttt C.创建一棵二叉排序树n;couttt E.结束本程序n;coutnntt*endl;flag=0;doif(flag!=0)coutcmd;flag+; while(cmd!=c&cmd!=C&cmd!=a&cmd!=A);if(cmd=c|cmd=C)cout请输入你所要创建的二叉树的结点的值，以-1结束：n;root=createBST();doflag=0;coutnn中序遍历二叉树：endl; inorder_btree(root);coutnendl;couttt*请选择你要对这棵二叉树所做的操作:*endl;couttt* *endl;couttt* S.查找你想要寻找的结点 *endl;couttt* I.插入你想要插入的结点 *endl;couttt* D.删除你想要删除的结点 *endl;couttt* Q.结束对这棵二叉树的操作 *endl;couttt* *endl;couttt*endl;doif(flag!=0)cout选择操作错误！请重新选择！n;fflush(stdin);scanf(%c,&cmd);flag+;while(cmd!=s&cmd!=S&cmd!=i&cmd!=I&cmd!=d&cmd!=D&cmd!=q&cmd!=Q);switch(cmd)case s:case S:coutkey;test=searchBST(root,key);if(test=0)coutn对不起，你所查找的结点 key不存在!;elsecoutn成功找到结点nkey ;break;case i:case I:coutkey;root=insertBST(root,key); /注意必须将值传回根break;case d:case D:coutkey;root=deleteBST(root,key); /注意必须将值传回根if(root=NULL)coutn对不起，你所删除的结点 key 不存在!n;elsecoutn成功删除结点 key ;break;while(cmd!=q&cmd!=Q);while(cmd!=e&cmd!=E);return 0;实 验 内 容3.测试用例：1,程序运行时菜单显示如下： 当输入的二叉树序列为：2,6,9,8,4时，创建二叉排序树，并输出结果如下： 1.查找9结点时，运行结果如下：2.删除结点6时运行结果如下：3.插入结点7时运行结果如下：实 验 内 容#include using namespace std;/二杈树的二杈线索存储表示typedef char ElemType;typedef enum PointerTag Link, Thread; /Link:指针,Thread:线索typedef struct BiThrNode ElemType data; struct BiThrNode *lchild, *rchild;/左，右孩子指针 PointerTag LTag, RTag; /左，右标志 *BiThrTree;void InOrderTraverse_Thr(BiThrTree T);/中序遍历线索二杈树的非递归算法, T 指向头结点void InThreading(BiThrTree & p, BiThrTree & pre); /中序线索化BiThrTree InOrderThreading(BiThrTree T);/中序遍历二杈树，并将其中序线索化void CreateBTree(BiThrTree & bt);/生成一棵二杈排序树（输入单个字符，以#结束）BiThrTree NewBTree(ElemType x);/构造一个数据域为x的新结点void Insert(BiThrTree & b, BiThrTree s);/在二杈排序树中插入新结点svoid InOrderPrint_1(BiThrTree p); /中序遍历输出结点（递归）int main() BiThrTree bt = NULL; CreateBTree(bt);/生成一棵二杈排序树（输入单个字符，以#结束） InOrderPrint_1(bt); /中序遍历输出结点（递归） cout lchild; /p指向根结点 while (p != T) /空树或遍历结束时，p = T while (p-LTag = Link)/寻找第一个结点 p = p-lchild; cout data RTag = Thread & p-rchild != T)/访问后继结点 p = p-rchild; cout data rchild; void InThreading(BiThrTree & p, BiThrTree & pre) /中序线索化 if (p) InThreading(p-lchild, pre); /左子树线索化 if (! p-lchild)/若当前结点的左子树为空，则建立前驱线索 p-LTag = Thread; p-lchild = pre; else p-LTag = Link; if (pre & !pre-rchild)/若前驱结点非空，且其右孩子为空，则建立后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; /中序向前遍历接点 ，保持pre指向p的前驱 pre-RTag = Link;/默认前驱结点右孩子非空 InThreading(p-rchild, pre); /右子树线索化 BiThrTree InOrderThreading(BiThrTree T)/中序遍历二杈树，并将其中序线索化 BiThrTree Thrt = new BiThrNode; /建立头结点 if (!Thrt) printf(Out of space!); return NULL; Thrt-LTag = Link; Thrt-RTag = Thread; Thrt-rchild = Thrt; /右指针回指 if (!T)/若二杈树为空，则左指针回指 Thrt-lchild = Thrt; else Thrt-lchild = T; BiThrTree pre = Thrt; InThreading(T, pre);/中序线索化 pre-rchild = Thrt; /最后一个结点线索化 pre-RTag = Thread; Thrt-rchild = pre; /此时pre指向最后一个结点 return Thrt;void CreateBTree(BiThrTree & bt)/生成一棵二杈排序树（输入单个字符，以#结束） ElemType x; cin x; while (x != #) BiThrTree s = NewBTree(x);/构造一个数据域为x的新结点 Insert(bt, s);/在二杈排序树中插入新结点s cin x; BiThrTree NewBTree(ElemType x)/构造一个数据域为x的新结点 BiThrTree s = new BiThrNode; if (!s) printf(Out of space!); exit (1); s-data = x; s-lchild = s-rchild = NULL; s-LTag = s-RTag = Link; return s;void Insert(BiThrTree & b, BiThrTree s)/在二杈排序树中插入新结点s if (b = NULL) b = s; else if (b-data = s-data)/不做任何插入操作 return; else if(b-data s-data)/把s所指结点插入到左子树中 Insert(b-lchild, s); else /把s所指结点插入到右子树中 Insert(b-rchild, s);void InOrderPrint_1(BiThrTree p) /中序遍历输出结点（递归） if (p != NULL) InOrderPrint_1(p-lchild); /遍历左子树 cout data rchild); /遍历右子树