二叉排序树的实现-课程设计报告

IIrr中北大学数据结构课程设计说明书学生：程亚男学号：1021011616学院：软件学院专业：软件工程题目：二叉排序树的实现指导教师何志英II1.设计任务概述：2011年12月20日IIrr功能描述：(1)以回车('\n')为输入结束标志，输入数列L,生成一棵二叉排序树T；⑵对二叉排序树T作中序遍历，输出结果；⑶输入元素x,查找二叉排序树T,若存在含x的结点，则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。.本设计所采用的数据结构二叉树及二叉链表.功能模块详细设计详细设计思想建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。核心代码(1)主菜单模块intmain(){LNoderoot=NULL;

intNum,a,x;printf("\n\nprintf("1[qctszm**************\n");printf("*1:进行中序排列*\n");printf("*2:进行删除操作*\n");printf("*3:退出*\n");printf(*\n");printf（"请输入要进行操作的数字以0结束：\n"）；运行结果（3）中序遍历模块voidview(LNodep){//中序遍历函数if(p){view(p->lch);printf("%d",p->date);view(p->rch);//递归调用

return;return;运行结果・，口工口£101FilcsYAicxDSDft¥is-uelLStudio\MyProjcc13\binaxy^ort运行结果・，口工口£101FilcsYAicxDSDft¥is-uelLStudio\MyProjcc13\binaxy^orttrco...必群M陈携作恬输入要进行操作的数字以屋吉束.P934130隹代悻撰•'1二手ifiJ/J四喑果子;卜守？ 46 9靖选择操作，（3）删除模块LNodeDelNode(LNodet,intx){LNodep=t;LNodeq=NULL;LNodes;LNodef;while(p!=NULL){if(p->date==x){break;q=p;if(x<=p->date){p=p->lch;}else{p=p->rch;}}if(p==NULL){printf("不存在您要删除的数%d!",x);returnp;}if(p->lch){s=p->lch; //s指向其左子树；f=p->lch; //f指向其左子树；while(s->rch)//搜索左子树的最右边的叶子结点{f=s;s=s->rch;}p->date=s->date;if(f!=s){ 〃若不是p的左孩子，把r的左孩子作为r的父亲的右孩子f->rch=s->lch;}else{p->lch=s->lch; 〃否则结点p的左子树指向s的左子树}free(s);returnp;}else{if(q->lch==p){q->lch=p->rch;}else{q->rch=p->rch;}free(p);returnq;}}程序运行结果.课程设计心得、存在问题及解决方法通过这次课程设计，我进一步的懂得了二叉链表的建立方法，进一步的了解了二叉排序树的构造方法。对函数的构造以及调用有了更进一步的掌握，让我在调试程