二叉排序树运算-数据结构与算法课程设计报告_l

中北大学数据结构课程设计说明书2011年12月20日1.设计任务概述：功能描述：(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。

2.本设计所采用的数据结构二叉树及二叉链表3.功能模块详细设计3.1 详细设计思想建立二叉排序树采用边查找边插入的方式。

查找函数采用递归的方式进行查找。

如果查找到相等的则插入其左子树。

然后利用插入函数将该元素插入原树。

对二叉树进行中序遍历采用递归函数的方式。

在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

删除结点函数，采用边查找边删除的方式。

如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。

3.2 核心代码（1）主菜单模块int main(){LNode root=NULL;int Num,a,x;printf("\n\n *******************************\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 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(x<=p->date){p=p->lch;}else{p=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的左孩子作为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;}else{q->rch = p->rch;}free(p);return q;}}3.3 程序运行结果4.课程设计心得、存在问题及解决方法通过这次课程设计，我进一步的懂得了二叉链表的建立方法，进一步的了解了二叉排序树的构造方法。

深圳大学实验报告
课程名称：数据结构实验与课程设计
实验项目名称：二叉排序树实验
学院：计算机与软件学院
专业：
指导教师：
报告人：学号：班级： 3班
实验时间： 2012-11-28 实验报告提交时间： 2012-12-5
教务部制
int main(int argc,char *argv[])
{
int t[32];
int i,j,Key;
int TestNum,SampleNum;
// freopen("cin.txt","r",stdin);
// freopen("cout.txt","w",stdout);
BiSortTree *BST=new BiSortTree;
cin>>TestNum;
for(i=0;i<TestNum;i++){
cin>>SampleNum;
for(j=0;j<SampleNum;j++) cin>>t[j];
BST->CreateBST(t,SampleNum);
cin>>Key;
BST->SearchBST(Key);
cout<<BST->BisSuccess<<" "<<BST->BisPos <<" "<<BST->BisCount<<endl;
}
return 0;
}
运行截图：
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。

实验报告课程名：数据结构（C语言版）实验名：二叉排序树姓名：班级：学号：撰写时间：一实验目的与要求1.掌握二叉排序树上进行插入和删除的操作2.利用 C 语言实现该操作二实验内容•对于一个线形表, 利用不断插入的方法, 建立起一株二叉排序树•从该二叉排序树中删除一个叶子节点, 一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。

三实验结果与分析#include<>#include<>删结点是叶子结点，直接删除if(p->left == NULL && p->right == NULL){删结点只有左子树else if(p->left && !(p->right)){p->left->parent=p->parent;删结点只有右孩子else if(p->right && !(p->left)){p->right->parent=p->parent;删除的结点既有左孩子，又有右孩子//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)//删掉后继结点,后继结点的值代替该结点else{//找到要删除结点的后继q=searchSuccessor(p);temp=q->key;//删除后继结点deleteNode(root,q->key);p->key=temp;}return 1;}//创建一棵二叉查找树void create(PNode* root,KeyType *keyArray,int length) {int i;//逐个结点插入二叉树中for(i=0;i<length;i++)inseart(root,keyArray[i]);}int main(void){int i;PNode root=NULL;KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9}; create(&root,nodeArray,11);for(i=0;i<2;i++)deleteNode(&root,nodeArray[i]);printf("%d\n",searchPredecessor(root)->key);printf("%d\n",searchSuccessor(root)->key);printf("%d\n",searchMin(root)->key);printf("%d\n",searchMax(root)->key);printf("%d\n",search(root,13)->key);return 0;}图1：二叉树排序实验结果。

二叉排序数课程设计一、课程目标知识目标：1. 学生能理解二叉排序树的基本概念，掌握其结构特点及性质；2. 学生能掌握二叉排序树的插入、删除及查找操作，并理解其时间复杂度；3. 学生能运用二叉排序树解决实际问题，如排序、查找等。

技能目标：1. 学生能通过实际操作，构建并修改二叉排序树；2. 学生能运用二叉排序树进行数据排序和查找，提高解决问题的能力；3. 学生能运用所学知识，对二叉排序树进行优化，提高算法效率。

情感态度价值观目标：1. 学生通过学习二叉排序树，培养对数据结构和算法的兴趣，激发学习积极性；2. 学生在合作学习过程中，培养团队协作能力和沟通能力，增强集体荣誉感；3. 学生通过解决实际问题，体会算法在实际应用中的价值，提高对计算机科学的认识。

分析课程性质、学生特点和教学要求：本课程为数据结构与算法领域的内容，旨在让学生掌握二叉排序树的基本概念和操作。

针对初中年级学生的特点，课程设计注重实际操作和问题解决能力的培养。

教学要求注重理论与实践相结合，引导学生通过动手实践，深入理解二叉排序树的特点和应用。

通过分解课程目标为具体的学习成果，为后续教学设计和评估提供依据。

二、教学内容1. 二叉排序树基本概念：定义、性质、应用场景；2. 二叉排序树的构建：插入操作、删除操作、查找操作；3. 二叉排序树的遍历：前序遍历、中序遍历、后序遍历；4. 二叉排序树的查找：查找最小值、查找最大值、查找特定值；5. 二叉排序树的删除：删除叶子节点、删除只有一个子节点的节点、删除有两个子节点的节点；6. 二叉排序树的优化：平衡二叉排序树的概念及特点；7. 二叉排序树在实际问题中的应用：排序、查找等。

教学大纲：第一课时：二叉排序树基本概念、性质、应用场景；第二课时：二叉排序树的构建与插入操作；第三课时：二叉排序树的删除操作；第四课时：二叉排序树的查找操作；第五课时：二叉排序树的遍历；第六课时：平衡二叉排序树的概念及特点；第七课时：二叉排序树在实际问题中的应用。

《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。

问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。

由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。

处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。

算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。

输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。

对二叉树的一些运算结果以整型输出。

程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。

计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。

对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。

测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。

二叉排序树课程设计一、课程目标知识目标：1. 理解二叉排序树的概念和特点；2. 掌握二叉排序树的插入、删除和查找操作；3. 能够分析二叉排序树的时间复杂度；4. 了解二叉排序树在实际应用中的优势。

技能目标：1. 能够手动构建二叉排序树并进行基本操作；2. 能够运用编程语言实现二叉排序树的基本功能；3. 能够分析并解决二叉排序树相关的问题；4. 能够运用二叉排序树解决实际排序和查找问题。

情感态度价值观目标：1. 培养学生对数据结构和算法的兴趣，激发学习热情；2. 培养学生的逻辑思维能力和问题解决能力；3. 培养学生的团队协作意识，学会与他人共同分析、解决问题；4. 培养学生严谨的科学态度，注重算法的正确性和效率。

课程性质：本课程为计算机科学领域的数据结构与算法课程，旨在让学生掌握二叉排序树的基本概念和操作，提高学生的编程能力和逻辑思维能力。

学生特点：学生具备基本的计算机知识和编程基础，对数据结构有一定了解，但对二叉排序树的认识可能较浅。

教学要求：结合学生特点，采用讲解、实践和讨论相结合的教学方法，使学生在理解二叉排序树理论知识的基础上，能够动手实践并解决实际问题。

在教学过程中，注重培养学生的自主学习能力和团队合作精神，提高学生的综合素质。

通过本课程的学习，使学生能够达到上述课程目标，为后续相关课程打下坚实基础。

二、教学内容1. 引入二叉排序树的概念，阐述其定义、性质和应用场景；- 教材章节：第三章第一节“二叉排序树的定义和性质”2. 讲解二叉排序树的插入、删除、查找操作及其实现方法；- 教材章节：第三章第二节“二叉排序树的操作”3. 分析二叉排序树的性能特点，包括时间复杂度和空间复杂度；- 教材章节：第三章第三节“二叉排序树的性能分析”4. 介绍二叉排序树在实际应用中的优势，如排序、查找等；- 教材章节：第三章第四节“二叉排序树的应用”5. 结合实例，让学生动手实践二叉排序树的构建和操作；- 教材章节：第三章实例分析与编程练习6. 总结二叉排序树的特点和适用场景，与其他排序方法进行对比；- 教材章节：第三章总结与拓展教学进度安排：1. 第1课时：引入二叉排序树的概念、性质和应用场景；2. 第2课时：讲解二叉排序树的插入、删除、查找操作；3. 第3课时：分析二叉排序树的性能特点；4. 第4课时：介绍二叉排序树在实际应用中的优势；5. 第5课时：结合实例，学生动手实践二叉排序树的构建和操作；6. 第6课时：总结二叉排序树，与其他排序方法进行对比。

淮阴工学院数据结构课程设计报告选题名称:二叉排序树（二叉链表结构存储）系（院）:计算机工程系专业:计算机科学与技术班级:计算机1091姓名:黄磊学号:1091301108指导教师:张亚红周海岩学年学期:2010 ~ 2011 学年第 1 学期2010 年12 月31 日设计任务书摘要：数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。

当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。

相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。

本次课程设计，程序中的数据采用“树形结构”作为其数据结构。

而二叉搜索树又是一种特殊的二叉树。

本课程设中的二叉排序树是基于二叉链表作存储结构的，一共要实现五项基本的功能。

它们分别是二叉搜索树的创建、中序遍历、查找结点、删除结点和计算二叉排序树搜索成功时的平均查找长度。

关键词：二叉排序树；中序遍历；搜索结点；删除结点；平均查找长度目录1需求分析 (1)1.1课程设计题目、任务及要求 (1)1.2课程设计思想 (1)2概要设计 (2)2.1 二叉排序树的定义 (2)2.2二叉链表的存储结构 (2)2.3建立二叉排序树 (2)2.4二叉排序树的生成过程 (3)2.5中序遍历二叉树 (3)2.6二叉排序树的查找 (3)2.7二叉排序树的插入 (4)2.8平均查找长度 (4)3详细设计和实现 (4)3.1主要功能模块设计 (4)3.2主程序设计 (5)4调试与操作说明 (12)4.1程序调试 (12)4.2程序操作说明 (12)总结 (16)致谢 (17)参考文献 (18)1需求分析1.1课程设计题目、任务及要求二叉排序树。

用二叉链表作存储结构(1)以(0)为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历,输出结果；(3)计算二叉排序树T查找成功的平均查找长度,输出结果；(4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；1.2课程设计思想建立二叉排序树采用边查找边插入的方式。