《二叉排序树的实现_课程设计汇本报告》由会员分享,可在线阅读,更多相关《二叉排序树的实现_课程设计汇本报告(7页珍藏版)》请在金锄头文库上搜索。
1、 中北大学数 据 结 构课 程 设 计 说 明 书学生:程亚男学 号:1021011616学 院:软件学院专 业:软件工程题 目:二叉排序树的实现指导教师何志英2011年12月20日1. 设计任务概述:NO!无结点x二叉排序树T是否为平衡二叉树存在含x的结点,则删除该结点,并作中序遍历找到该节点x输入元素x,查找二叉排序树TOK!对二叉排序树T作中序遍历,并输出结果二叉链表作存储结构和顺序表作存储结构输入数列L, 以回车(n)为输入结束标志生成二叉排序树T;功能描述:(1)以回车(n)为输入结束标志,输入数列L,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历,输出结果;(3)输入元素x,
2、查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”。2.本设计所采用的数据结构二叉树及二叉链表3.功能模块详细设计3.1 详细设计思想建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下,先访问左子树,再访问根结点,最后访问右子树。删除结点函数,采用边查找边删除的方式。如果没有查找到,进行提示;如果查找到结点则将其左子树最右边的节点的数据传给它,然后删除其左子树最右边的节点。3.2 核心代码(1)主菜单
3、模块int main()LNode root=NULL;int Num,a,x; printf(nn *n);printf( *主菜单*n); printf( *1:进行中序排列 *n);printf( *2:进行删除操作 *n); printf( *3:退出 *n);printf( *n);printf(请输入要进行操作的数字以0结束:n);运行结果(3)中序遍历模块void view(LNode p)/中序遍历函数if(p)view(p-lch);printf(%d ,p-date);view(p-rch);/递归调用return;return;运行结果(3)删除模块LNode DelNo
4、de(LNode t,int x) LNode p=t;LNode q=NULL;LNode s; LNode f; while(p!=NULL)if(p-date=x)break;q=p;if(xdate)p=p-lch;elsep=p-rch;if(p=NULL)printf(不存在您要删除的数 %d !,x);return p;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的左孩子作
5、为r的父亲的右孩子 f- rch=s-lch; else p-lch = s-lch; /否则结点p的左子树指向s的左子树 free(s); return p; else if(q-lch=p)q-lch = p-rch; elseq-rch = p-rch;free(p); return q; 3.3 程序运行结果4.课程设计心得、存在问题及解决方法通过这次课程设计,我进一步的懂得了二叉链表的建立方法,进一步的了解了二叉排序树的构造方法。对函数的构造以及调用有了更进一步的掌握,让我在调试程序是有了一定的经验。多考虑算法的可行性。在遇到问题是认真考虑。同时让我意识到数据结构在编程中的重要作用。算法的优越性对程序的重要性。让我在调试程序是有了一定的经验。