课程设计（论文）PAGE\*MERGEFORMAT21编号：D04710043学号：201540410126课程设计教学院计算机学院课程名称数据结构与算法设计B题目二叉排序树与平衡二叉排序树专业计算机科学与技术班级2015级（1）班姓名甘全中同组人员指导教师2016年12月26日目录TOC\o"1-4"\h\z\uHYPERLINK\l"_Toc470076608"一概述PAGEREF_Toc470076608\h2HYPERLINK\l"_Toc470076609"1.1课程设计的目的PAGEREF_Toc470076609\h2HYPERLINK\l"_Toc470076610"1.2课程设计的要求PAGEREF_Toc470076610\h2HYPERLINK\l"_Toc470076611"二总体方案设计PAGEREF_Toc470076611\h3HYPERLINK\l"_Toc470076612"2.1二叉排序树的建立PAGEREF_Toc470076612\h3HYPERLINK\l"_Toc470076613"2.2二叉排序树的中序遍历PAGEREF_Toc470076613\h4HYPERLINK\l"_Toc470076614"2.3二叉排序树中元素的查找PAGEREF_Toc470076614\h4HYPERLINK\l"_Toc470076615"2.4二叉排序树中元素的删除PAGEREF_Toc470076615\h5HYPERLINK\l"_Toc470076616"2.5二叉排序树的平均查找长度PAGEREF_Toc470076616\h5HYPERLINK\l"_Toc470076617"2.6平衡二叉树（AVL）PAGEREF_Toc470076617\h5HYPERLINK\l"_Toc470076618"2.7中序输出平衡二叉树PAGEREF_Toc470076618\h7HYPERLINK\l"_Toc470076619"2.8在平衡二叉排序树上插入一个新元素PAGEREF_Toc470076619\h8HYPERLINK\l"_Toc470076620"2.9在平衡二叉排序树上删除一个元素PAGEREF_Toc470076620\h8HYPERLINK\l"_Toc470076621"2.10求平衡二叉树的平均查找长度PAGEREF_Toc470076621\h8HYPERLINK\l"_Toc470076622"三详细设计PAGEREF_Toc470076622\h9HYPERLINK\l"_Toc470076623"四程序的调试与运行结果说明PAGEREF_Toc470076623\h12HYPERLINK\l"_Toc470076624"五课程设计总结PAGEREF_Toc470076624\h13HYPERLINK\l"_Toc470076625"参考文献PAGEREF_Toc470076625\h14一概述1.1课程设计的目的1．理解和掌握该课程中的有关基本概念，程序设计思想和方法。2．培养综合运用所学知识独立完成课题的能力。3．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。5.本课程是数据结构课程的实践环节。主要目的在于加强学生在课程中学习的相关算法和这些方法的具体应用，使学生进一步掌握在C或其他语言中应用这些算法的能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解。另外，数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。1.2课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('\n')为