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