构建一棵二叉排序树的C程序的设计方案

1 构建一棵二叉排序树的 C 程序的设计方案 与目标 一、目的 数据结构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。 二、目标 1、结合 c 和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。 2、学会查阅资料，熟悉常用算法的用途与技巧。 3、认真撰写课 程设计报告，培养严谨的作风和科学态度。 本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。 实现本程序需要 解决以下几个问题： 1、 如何构造二叉排序树。 2、 如何通过中序遍历输出二叉排序树。 3、 如何实现多种查找。 4、 如何实现插入删除等操作。 二叉排序树的定义： 其左子树非空，则左子树上所有结点的值均小于根结点的值。 若其右子树非空，则右子树上所有结点的 值大于根结点的值。 其左右子树也分别为二叉排序树。 本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关 2 键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。 本问题的难点在于二叉排序树的删 除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排 序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。 用二叉链表作为二叉排序树的存储结构，其中 结点关键值， *程序的流程图所示： N Y 开始 输入节点值 节点是否为 0 进入主菜单 输入 i I=0 I=1 I=2 I=3 I=4 退出 查找 插入 删除 显示 输入 J=1 J=2 2 3 总流 程图 首先定义二叉排序树的数据类型如下： *然后按一定顺序来编写算法程序： 归 查查 找找 算算 法法 具体思想如下： （ 1）若二叉树为空，则查找失败。 （ 2）否则，将根结点的关键值与待查关键字进行比较，若相等，则查找成功；若根结点关键值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤；若在查找过程的中遇到二叉排序树的 叶子结点时，还没有找到待查结点，则查找不成功。 if(t=if(t-x) t; if(t-x); t-x); 4 二叉排序树归查找算法流程图 递 归归 查查 找找 算算 法法 查找过程是从根结点开始逐层向下进行的。并定义一个标记量记录是否找到结点。 t,x) p;p=t;/定义 *p 结点用于逐层查找，丛根结点开始查找 p!= if(p-x)/查找成功 该结点值存在 !); /查找不成功，到下一层继续查找 if(p=p- if(0) 找不到值为 %d 的结点 !,x); p= p; 5 Y Y N 二叉排序树非递归查找算法流程图 入 算算 法法 从根结点开始，根据比较规则，逐一与待插入结点的值比较，查找到插入结点在二叉排序树中的未来位置，然后插入该结点。 将一个关键字的值为 x 的结点 s 插入到二叉排序树中，方法如下： （ 1）若二叉排序树为空，则关键字值为 x 的结点 s 成为二叉排序树 的根。 （ 2）若二叉排序树非空，则将 x 与二叉排序树的根进行比较，如果 x 的值等于根结点关键字的值，则停止插入；如果 x 的值小于根结点关键字的值，则将 果 x 的值大于根结点关键字的值，则将 x 插入右子树。在左右子树中插入方法与整个二叉排序树相同。 t,x)/ 插入关键值为 x 的元素 s,*p,*f;/*s 为待插结点， *p 为逐层查找结点， *f 为待插结点的父结点 p=t; p!= f=p;/查找过程中， f 指向 *p 的父结点 if(x=p-，无需插入 t; if( p=p- p=p- (p-x) 查找成功 下一层？ p=p-p=p-不到节点 6 s=(); s-x; s-s-if(t=，新结点作为二叉排序树 的根 s; if(f-s;/新结点作为 *f 左孩子 f-s;/新结点作为 *f 右孩子 t; 插入算法流程图 叉 排排 序序 树树 的的 生生 成成 算算 法法 建立二叉排序树，就是反复在二叉排序树中插入新的结点。插入的原则是如果待插入结点的值小于根结点的值，则插入到左子树中，否则插入到右子树中。 大致方法是：首先建一棵空二叉排序树，然后逐个读入元素，每读入一个元素，就建一个新结 点，并调用上述二叉排序树的插入算法，将新结点插入到当前已生成的二叉排序树中，最终生成一棵二叉排序树。 t; t=(%d,& t=t, %d,& 开始 输入节点数 n 调用插入函数 结束 7 t; 序 遍遍 历历 算算 法法 t) if(t!= t- %4dn”,t- t- 先遍历左孩子，再遍历父结点，最后遍历右孩子。由于是 对一个二叉排序树进行中序遍历，遍历结果则是一个有序序列 除 算算 法法 p 无左孩子，也无右孩子，则 *p 的 父结点对应的孩子指针置空； p 有左孩子，无右孩子，则 *p 的左孩子替代自己； p 无左孩子，有右孩子，则 *p 的右孩子替代自己； p 有左孩子，也有右孩子， 本课程（数据结构与算法）给出了两种法： 方法一： 首先找到待删结点 *p 的前驱结点 *s，然后将 *p 的左子树改为 *p 父结点的左子树，而 *p 的右子树改为 *s 的右子树： p-s-p-p); 方法二： 首先找到待删结点 *p 的前驱结点 *s，然后用结点 *s 的值替代结点 *p 的值，再将结点 *s 删除，结点 *s 的原左子树改为 *s 的双亲结点 *q 的右子树： p-s-q-s-s); 我采用的是第二种算法。 8 N Y 删除算法流程图 函 数数 i,j,k; p; ; 请先建立一棵二叉排序树 nn); 输入其结点信息 (输入一组正整数 ,当输入 0 时结束 ):n); ; 中序遍历的二叉排序树 :n); 二叉排序树的根为 :%dn, ;) i=) :); :j=) :n 请输入要查找的结点的值 :); %d,&k);p=k); n); (输入有误 !); :开始 p=p=s 结束 T-s=-)s=-)9 :n); 二叉排序树的根为 :%dn, 中序遍历后的序列为 :n); 中序遍历的二叉排序树 :n); n); (输入有误 !); 意 事事 项项 ： 其中，某些函数顺序一定不能颠倒。例 如建立二叉排序树函数一定是在插入算法之后。 编写完基本操作算法后，为最后主函数的输出模块作准备，又分别写了递归查找模块、插入模块、删除模块、显示模块。 + 010 法 错错 误误 及及 修修 改改 在编写程序时，很容易出现分号漏写和括号不匹配的现象，以及缺少返回值的问题。 例如：在编写非递归查找算法时： t,x) p; p=t; p!= if(p-x) 10 找到了 !); p; if(p=p-p=p- if(0) 找不到值为 %d 的结点 ,x); 结果编译时出现了警告 : a 后我做了改动，改后程序如下： t,x) p;p=t; p!= if(p-x) 该结点值存在 !); if(p=p-p=p- if(0) 找不到值为 %d 的结点 !,x); p= 11 p; 将 赋给指针 p，再在程序结尾返回 p，此时，编译结果就正确了！ 序 输输 出出 调调 整整 ： 在递归查找算法 (针对查找结果如何 ,没有用明确的输出函数表示出来。于是我添加了一个递归查找模块如下： t) s; p; n 请输入要查找的结点的值 :); %d,&s); if(s!=0) p=t,s); if(p= 该结点值不存在 !n); 找不到值为 %d 的结点 !n,s); 这样主函数便可直接调用该函数来实现查找过程。 间 和和 空空 间间 性性 能能 分分 析析 ： 由于二叉排序树的中序遍历序列为一个递增的有序序列，这样可以将二叉排序树看作是一个有序表。其查找过程：若查找成功，则是 从根结点出发走了一条从根到某个结点的路径；若查找不成功，则是从根结点出发走了一条从根到某个叶子结点的路径。和关键字比较次数不超过二叉排序树的深度。二叉排序树的平均查找长度与其形态有关。最坏情况是具有 n 个结点的单支树，其平均查找长度与顺序查找相同，为（ n+1） /2；即平均查找长度的数量级为 O（ n）。在最好情况下，二叉排序树形态均匀，它的平均查找长度与二分查找相似，大约是 平均查找长度的数量级为 O（ 1、 经验与体会： 由于该设计问题是对数据结构与算法课程中二叉树章节的灵活应用，所以课 本给了我很大的帮助，结合所学知识以及对二叉排序树的理解，来编写该程序。 12 1、 建立如图（ a）的二叉排序树，输入的数据依次为： 45 24 53 12 28 90 0（ 0 为输入结束符），屏幕（图（ 1）上显示的是横置的二叉树 图（ a） 图（ b） 图（ 1） 2、选择方框中给定的项目（输入 04 中任 意数）。 若输入错误会有提示，可以重新输入。 45 24 53 12 28 90 45 24 53 12 28 90 13 图（ 2） 3、 输入 1，则出现查找菜单。选择查找方法。 图（ 3） 4、在查找菜单选 1，则进行递归查找。 14 图（ 4） 5、同理，若选择 2，则进行非递归查找。查找的值存在与否都会有显示。图（ 5） 6、选 2，则进行插入操作。插入关键值为 13 的结点后，显示如图（ 6），即插入 13 后的横置的二叉排序树（图（ c） 图（ d）。 15 图（ c） 图（ d） 图（ 6） 1、 选 3，进行删除操作。删除关键值为 24 的结点后，显示如图（ 7），即删除 24 后的横置的二叉排序树（图（ e） 图（ f） 、 45 24 53 12 28 90 13 45 24 53 12 28 90 13 16 图（ e） 图（ f） 图（ 7） 2、 选 4 则显示详细信息。如图（ 8）所示，按中序遍历（从小到大）依次输出，并显示每个结点的孩子情况，最后打印出横置的二叉排序树。45 13 53 12 28 90 45 13 53 12 28 90 17 图（ 8） 3、 选 0 则退出程序。 图 （ 9） 18 用户可以根据本程序运行过程中出现的提示性语句来进行操作。要注意括号中的提示，若没有按照提示输入的话，程序可能将无法继续进行下去。例如开始输入数据时直到输入 0时才算结束输入，从而进行下一步操作。在遇到选项时，选择错误会给你重新选择的机会。提示：进行一系列插入删除等操作后，可以选择显示项来显示最后的二叉排序树状态 (二叉排序树显示的是中序遍历后的序列 ) 。 (1)王昆仑 数据结构与算法 国铁道出版社， 2)王昆仑 数据结构与算法试验指 导， 2009 (3)谭浩强 序设计 华大学出版社， 4)严蔚敏 语言版 华大学出版社， 2002 (5)耿国华 数据结构 :用 c 语言描述 等教育出版社， 2004 19 设计过程中质疑（或答辩）记载： 1 二叉树运行过程中用了什么排序？ 答：运用了中序遍历排序。 2中序遍历排序是怎样的？ 答：先遍历左孩子，再遍历父结点，最后遍历右孩子。 答 :在编程序的过程的程序一直不能正确 运行，最后发现函数的调用出现了问题。最后通过修改解决。 指导教师评语： 签名： 2016 年 7 月 5 日 20 附录 # *（递归） t,x) if(t=，查找失败 if(t-x)/查找成功，返回当前结点 t; if(t-x);/进入左子树递归查找 t-x);/进入右子树递归查找 /递归查找函数（显示查找结果） t) s;/定义待查结点的关键值 p;/定义待查的结点 n 请输入要查找的结点的值 :); 21 %d,&s); if(s!=0) p=t,s);/递归查找 if(p!= 该结点值存在 !n); 找不到值为 %d 的结点 !n,s); /二叉排序树的查找算法之二（非递归） t,x) p;p=t;/定义 *p 结点用于逐层查找，丛根 结点开始查找 p!= if(p-x)/查找成功 该结点值存在 !); /查找不成功，到下一层继续查找 if(p=p- if(0) 找不到值为 %d 的结点 !,x); p= p; /二叉排序树的结点插入算法 t,x)/ 插入关键值为 x 的元素 s,*p,*f;/*s 为待插结点， *p 为逐层查找结点， *f 为待插结点的父结点 p=t; p!= f=p;/查找过程中， f 指向 *p 的父结点 if(x=p-，无需插入 22 t; if( p=p- p=p- s=(); s-x; s-s-if(t=，新结点作为二叉排序树的根 s; if(f-s;/新结点作为 *f 左孩子 f-s;/新结点作为 *f 右孩子 t; /中序遍历（递归法） t) if(t!= t-(%4d,t- t- /二叉排序树的结点删除算法 t,k)/删除关键值为 k 的元素 p,*f,*s,*q;/*p 为待删结点， *f 为 *p 父结点， *s 为 *p 的中序前驱结点， *q 为*s 的父结点 p=t;f=，并将 *f 置空 /查找关键值为 k 的待删结点 *p p!= if(p-k) ，则退出循环 23 f=p;/未找到时将 *f 替代 *p， *p 则下移进入左右子树继续查找 if(p-k) p=p-p=p- if(p=t;/若找不到，则返回原二叉排序树的根指针 /查找成功后，对 *p 的删除过程 if(p-p-*p 无左子树或无右子树 if(f=*p 是原二叉排序树的根 if(p-t=p-，右孩子做根 t=p-/无右孩子，左孩子做根 if(p-*p 无左子树 if(f-p) f-p-*f 的左孩子 f-p-*f 的右孩子 *p 无右子树 if(f-p) f-p-*f 的左孩子 f-p-*f 的右孩子 p); 若 *p 有左右子树 q=p;s=p-s-*p 的左子树中查找最右下结点 (即其中序前驱结点 ) q=s;s=s- if(q=p) q-s-q-s-p-s-*s 的值赋给 *p s); t; /插入函数（显示插入结果） t) 24 s;/定义待插结点的关键值 p;/定义待插的结点 n); 请输入要插入的结点的值 :); %d,&s); if(s!=0) p=t,s); if(p= t=t,s); 插入结点中序遍历后的二叉排序树 :n); t); n 二叉排序树的根为 :%dn,t- 该结点值存在 ,不插入 !n); t; /删除函数（显示删除结果） t) s;/定义待删结点的关键值 p;/定义待删的结点 n 请输入要删除的结点的值 :); %d,&s); if(s!=0) p=t,s); if(p=找不到值为 %d 的结点 !,s); t=t,s); 删除结点后中序遍历的二叉排序树 :n); t); n 二叉排序树的根为 :%dn,t- t; 25 /设置二叉排序树的初值 t; s; t=(%d,&s