下载文档原格式
题目:二叉排序树的实现1 内容和要求1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进展先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩3 项),比照查找效率，并说明在什么情况下二叉排序树效率高,为什么?2 解决方案和关键代码2.1 解决方案：先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。
前中后根遍历需要用到栈的数据构造，分模块编写栈与遍历代码。
要求比照二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock〔〕函数记录查找时间来比照查找效率。
2.2关键代码树的根本构造定义及根本函数typedef struct{KeyType key;} ElemType;typedef struct BiTNode//定义链表{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree, *SElemType;//销毁树int DestroyBiTree(BiTree &T){if (T != NULL)free(T);return 0;}//清空树int ClearBiTree(BiTree &T){if (T != NULL){T->lchild = NULL;T->rchild = NULL;T = NULL;}return 0;}//查找关键字,指针p返回int SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {if (!T){p = f;return FALSE;}else if EQ(key, T->data.key){p = T;return TRUE;}else if LT(key, T->data.key)return SearchBST(T->lchild, key, T, p);elsereturn SearchBST(T->rchild, key, T, p);}二叉树的生成、插入，删除生成void CreateBST(BiTree &BT, BiTree p){int i;ElemType k;printf("请输入元素值以创立排序二叉树:\n");scanf_s("%d", &k.key);for (i = 0; k.key != NULL; i++){//判断是否重复if (!SearchBST(BT, k.key, NULL, p)){InsertBST(BT, k);scanf_s("%d", &k.key);}else{printf("输入数据重复！\n");return;}}}插入int InsertBST(BiTree &T, ElemType e){BiTree s, p;if (!SearchBST(T, e.key, NULL, p)){s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;if (!p)T = s;else if LT(e.key, p->data.key)p->lchild = s;elsep->rchild = s;return TRUE;}else return FALSE;}删除//某个节点元素的删除int DeleteEle(BiTree &p){BiTree q, s;if (!p->rchild) //右子树为空{q = p;p = p->lchild;free(q);}else if (!p->lchild) //左子树为空{q = p;p = p->rchild;free(q);}else{q = p;s = p->lchild;while (s->rchild){q = s;s = s->rchild;}p->data = s->data;if (q != p)q->rchild = s->lchild;elseq->lchild = s->lchild;delete s;}return TRUE;}//整棵树的删除int DeleteBST(BiTree &T, KeyType key) //实现二叉排序树的删除操作{if (!T){return FALSE;}else{if (EQ(key, T->data.key)) //是否相等return DeleteEle(T);else if (LT(key, T->data.key)) //是否小于return DeleteBST(T->lchild, key);elsereturn DeleteBST(T->rchild, key);}return 0;}二叉树的前中后根遍历栈的定义typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;int InitStack(SqStack &S) //构造空栈{S.base = (SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}//InitStackint Push(SqStack &S, SElemType e) //插入元素e为新栈顶{if (S.top - S.base >= S.stacksize){S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}//Pushint Pop(SqStack &S, SElemType &e) //删除栈顶,应用e返回其值{if (S.top == S.base) return ERROR;e = *--S.top;return OK;}//Popint StackEmpty(SqStack S) //判断是否为空栈{if (S.base == S.top) return TRUE;return FALSE;}先根遍历int PreOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);if (!Visit(p->data)) return ERROR;p = p->lchild;}else{Pop(S, p);p = p->rchild;}}return OK;}中根遍历int InOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);p = p->lchild;}else{Pop(S, p);if (!Visit(p->data)) return ERROR;p = p->rchild;}}return OK;}后根遍历int PostOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S, SS;BiTree p;InitStack(S);InitStack(SS);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);Push(SS, p);p = p->rchild;}else{if (!StackEmpty(S)){Pop(S, p);p = p->lchild;}}}while (!StackEmpty(SS)){Pop(SS, p);if (!Visit(p->data)) return ERROR;}return OK;}利用数组存储一个班学生信息ElemType a[] = { 51, "陈继真", 88,82, "黄景元", 89,53, "贾成", 88,44, "呼颜", 90,25, "鲁修德", 88,56, "须成", 88,47, "孙祥", 87, 38, "柏有患", 89, 9, " 革高", 89, 10, "考鬲", 87, 31, "李燧", 86, 12, "夏祥", 89, 53, "余惠", 84, 4, "鲁芝", 90, 75, "黄丙庆", 88, 16, "李应", 89, 87, "杨志", 86, 18, "李逵", 89, 9, "阮小五", 85, 20, "史进", 88, 21, "秦明", 88, 82, "杨雄", 89, 23, "刘唐", 85, 64, "武松", 88, 25, "李俊", 88, 86, "卢俊义", 88, 27, "华荣", 87, 28, "杨胜", 88, 29, "林冲", 89, 70, "李跃", 85, 31, "蓝虎", 90, 32, "宋禄", 84, 73, "鲁智深", 89, 34, "关斌", 90, 55, "龚成", 87, 36, "黄乌", 87, 57, "孔道灵", 87, 38, "张焕", 84, 59, "李信", 88, 30, "徐山", 83, 41, "秦祥", 85, 42, "葛公", 85, 23, "武衍公", 87, 94, "范斌", 83, 45, "黄乌", 60, 67, "叶景昌", 99, 7, "焦龙", 89, 78, "星姚烨", 85, 49, "孙吉", 90, 60, "陈梦庚", 95,};数组查询函数void ArraySearch(ElemType a[], int key, int length){int i;for (i = 0; i <= length; i++){if (key == a[i].key){cout << "学号：" << a[i].key << " 姓名：" << a[i].name << " 成绩：" << a[i].grade << endl;break;}}}二叉树查询函数上文二叉树根本函数中的SearchBST()即为二叉树查询函数。
“数据结构”课程设计报告二叉排序树的查找与性能分析学生姓名：段晓宣，张静指导教师：陈少军所在系：电子信息系所学专业：计算机科学与技术年级： 2010级计算机（1）班目录第一章需求分析1.1选题要求 (3)1.2选题的背景与意义 (3)1.3本组课程设计的目标 (3)1.4人员组成和分工 (3)第2章概要分析 (4)2.1系统数据流图 (4)2.2原始数据 (4)2.3输出数据 (4)2.4对数据的处理 (5)2.5数据结构 (5)2.6模块划分 (5)第3章详细设计 (6)3.1二叉排序树的创建 (6)3.2二叉排序树的插入 (7)3.3二叉排序树的查找 (7)3.4计算多数据的平均查找长度 (9)3.5主函数 (9)第4章用户手册 (10)4.1 用户须知 (10)第5章系统测试 (11)项目总结 (12)参考文献 (13)二叉树排序树的查找与性能分析摘要：21世纪是信息化的时代，计算机深入到生活的各个领域。
随着计算机的发展，许多高科技产品如雨后春笋应运而生。
但究其本质而言，无非是以前的理论加以包装。
对于数据控制、管理及处理等方面也可见一斑。
在如今应用的计算机的数据存储方式仍然主要以线性，树型，图型等为主要的及结构。
因此了解并掌握数据结构的知识是很有必要的。
在此次实训期间，本组人员通过运用所学数据结构的知识，进行以二叉排序树的查找与性能分析为题的课程设计，在同组人员的共同努力下，基本实现了：1.创建二叉排序树2.利用文件存储二叉排序树3.二叉排序树的插入4.二叉排序树的查找5.二叉排序树平均查找长度的算法第1章需求分析1.1选题要求（1）根据输入的先序及递归建立二叉排序树；（2）通过文件，向二叉排序树插入结点，并生成二叉树；（3）设置报名号为关键字，可以根据关键字进行查找；（5）查找的同时可以判断比较的次数；（6）根据查找的算法计算出10000个数据平均查找长度；1.2选题的背景与意义（1）树型存储结构数据存储结构中重要的组成部分，二叉树由是树的重点。
二叉排序树操作一、设计步骤1）分析课程设计题目的要求2）写出详细设计说明3）编写程序代码，调试程序使其能正确运行4）设计完成的软件要便于操作和使用5）设计完成后提交课程设计报告（一）程序功能：1）创建二叉排序树2）输出二叉排序树3）在二叉排序树中插入新结点4）在二叉排序树中删除给定的值5）在二叉排序树中查找所给定的值（二）函数功能：1） struct BiTnode 定义二叉链表结点类型包含结点的信息2） class BT 二叉排序树类，以实现二叉排序树的相关操作3） InitBitree() 构造函数，使根节点指向空4) ~BT () 析构函数，释放结点空间5) void InsertBST(&t,key) 实现二叉排序树的插入功能6) int SearchBST(t,key) 实现二叉排序树的查找功能7) int DelBST(&t,key) 实现二叉排序树的删除功能8) void InorderBiTree (t) 实现二叉排序树的排序（输出功能）9) int main() 主函数，用来完成对二叉排序树类中各个函数的测试二、设计理论分析方法（一）二叉排序树定义首先，我们应该明确所谓二叉排序树是指满足下列条件的二叉树：（1）左子树上的所有结点值均小于根结点值；（2）右子数上的所有结点值均不小于根结点值；（3）左、右子数也满足上述两个条件。
根据对上述的理解和分析，我们就可以先创建出一个二叉链表结点的结构体类型（struct BiTNode）和一个二叉排序树类（class BT），以及类中的构造函数、析构函数和其他实现相关功能的函数。
（二）插入函数（void InsertBST(&t,key)）首先定义一个与BiTNode<k> *BT同一类型的结点p，并为其申请空间，使p->data=key,p->lchild和p->rchild=NULL。
二叉树教案一、教学目标：1.了解二叉树的定义和性质。
2.学会二叉树的遍历算法（前序遍历、中序遍历、后序遍历）。
3.掌握二叉树的基本操作（创建二叉树、插入节点、删除节点）。
二、教学重点和难点：1.二叉树的定义和性质。
2.二叉树的遍历算法。
3.二叉树的基本操作。
三、教学准备：1.教师准备：PPT、计算机、投影仪。
2.学生准备：课前预习、纸笔。
四、教学过程：Step 1 导入新课教师通过提问的方式，引导学生回顾树的基本概念，并激发学生对二叉树的兴趣。
Step 2 二叉树的定义和性质教师给出二叉树的定义，并带领学生讨论二叉树的性质（每个节点最多有两个子节点，左子树和右子树）。
Step 3 二叉树的遍历算法1.前序遍历：先访问根节点，然后递归遍历左子树，再递归遍历右子树。
2.中序遍历：先递归遍历左子树，然后访问根节点，再递归遍历右子树。
3.后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。
Step 4 二叉树的基本操作1.创建二叉树：教师通过示例向学生展示二叉树的创建过程。
2.插入节点：教师通过示例向学生展示如何插入节点，并解释插入节点的规则。
3.删除节点：教师通过示例向学生展示如何删除节点，并解释删除节点的规则。
Step 5 练习与拓展1.教师设计练习题，让学生运用所学知识进行练习。
2.鼓励学生拓展二叉树的其他应用领域，并进行讨论。
五、教学反思本节课通过讲解二叉树的定义和性质，以及二叉树的遍历算法和基本操作，使学生对二叉树有了基本的了解和掌握。
通过练习和拓展，巩固了学生的学习成果，并培养了学生的分析和解决问题的能力。
但是，由于时间有限，学生的实际操作机会较少，可以在课后布置相关的作业，加深学生的理解和应用能力。
《用二叉树排序》作业设计方案（第一课时）一、作业目标本作业设计旨在通过实践操作，使学生能够理解二叉树的基本概念，掌握二叉树的创建与遍历方法，特别是掌握二叉树排序的原理和实现过程。
通过本次作业，期望学生能够达到对二叉树排序的深入理解和应用能力。
二、作业内容1. 理论学习：学生需认真阅读教材中关于二叉树的相关知识，包括二叉树的定义、性质、创建及遍历方法等，并理解二叉树排序的基本原理。
2. 编程实践：学生需使用编程语言（如Python、Java等）实现二叉树的创建及遍历功能，并尝试实现二叉树排序算法。
具体要求包括：（1）创建一个简单的二叉树数据结构；（2）实现先序、中序、后序及层序遍历；（3）实现二叉树排序算法，并对比其他排序算法的效率和稳定性。
3. 案例分析：学生需分析一个实际场景中二叉树排序的应用案例，如数据库索引、文件系统目录结构等，并撰写分析报告。
三、作业要求1. 独立完成：本次作业需学生独立完成，不得抄袭他人成果。
2. 详细记录：在编程实践过程中，学生需详细记录代码实现过程及遇到的问题解决方案。
3. 规范编写：代码编写需符合规范，注释清晰，易于阅读。
4. 案例分析：案例分析报告需包括场景描述、二叉树排序的应用方式及效果分析等，字数不少于500字。
四、作业评价1. 理论掌握：评价学生对二叉树相关理论知识的掌握程度。
2. 编程实践：评价学生编程实践过程中的代码实现及问题解决能力。
3. 案例分析：评价学生对二叉树排序在实际应用中的理解和分析能力。
五、作业反馈1. 教师批改：教师需认真批改学生作业，指出存在的问题及改进建议。
2. 学生互评：鼓励学生之间互相评价作业，取长补短，提高学习效果。
3. 课堂讨论：在下一课时中，组织学生对本次作业进行课堂讨论，分享经验和心得。
六、附加建议为帮助学生更好地完成本次作业，建议学生利用课外时间查阅相关资料，参加线上或线下的编程实践课程，提高编程能力和算法理解。
同时，可与同学组成学习小组，共同探讨和解决作业中的问题。
二叉排序树（二叉链表结构存储）数据结构课程设计报告目录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程序操作说明 (13)总结 (16)致谢 (17)参考文献 (19)1需求分析1.1课程设计题目、任务及要求二叉排序树。
用二叉链表作存储结构(1)以(0)为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历,输出结果；(3)计算二叉排序树T查找成功的平均查找长度,输出结果；(4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；1.2课程设计思想建立二叉排序树采用边查找边插入的方式。
查找函数采用递归的方式进行查找。
如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。
然后利用插入函数将该元素插入原树。
对二叉排序树进行中序遍历采用递归函数的方式。
在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。
由于二叉排序树自身的性质，左子树小于根结点，而根结点小于右子树，所以中序遍历的结果是递增的。
计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。
平均查找长度就等于s/i(i为树中结点的总个数)。
删除结点函数，采用边查找边删除的方式。
如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。
二叉排序书课程设计一、课程目标知识目标：1. 让学生理解二叉排序树的概念、性质和基本操作，掌握二叉排序树的插入、删除和查找过程。
2. 使学生能够运用二叉排序树解决实际问题，如数据排序和查找。
技能目标：1. 培养学生运用二叉排序树进行数据组织和分析的能力。
2. 培养学生编写和调试二叉排序树相关程序的能力。
情感态度价值观目标：1. 培养学生对数据结构和算法的兴趣，激发学生学习主动性和积极性。
2. 培养学生勇于克服困难、独立解决问题的精神，增强团队合作意识。
3. 培养学生认识到二叉排序树在实际应用中的价值，提高对计算机科学的认识。
课程性质：本课程为计算机科学领域的数据结构与算法课程，以二叉排序树为主题，结合实际案例，使学生掌握二叉排序树的相关知识。
学生特点：学生已具备一定的编程基础和逻辑思维能力，但对二叉排序树的概念和操作尚不熟悉。
教学要求：1. 通过讲解、示例和练习，使学生掌握二叉排序树的基本原理和操作。
2. 注重理论与实践相结合，提高学生解决实际问题的能力。
3. 鼓励学生主动思考、提问，培养良好的学习习惯。
4. 强化编程实践，提高学生的编程技能和逻辑思维能力。
二、教学内容1. 引言：介绍二叉排序树的基本概念，及其在数据结构和算法中的应用。
- 相关章节：课本第X章“二叉树与二叉排序树”2. 二叉排序树的性质与定义：- 内容：二叉排序树的定义、性质、特点- 相关章节：课本第X章“二叉排序树的性质与定义”3. 二叉排序树的插入操作：- 内容：插入过程、算法实现、示例演示- 相关章节：课本第X章“二叉排序树的插入操作”4. 二叉排序树的删除操作：- 内容：删除过程、算法实现、示例演示- 相关章节：课本第X章“二叉排序树的删除操作”5. 二叉排序树的查找操作：- 内容：查找过程、算法实现、示例演示- 相关章节：课本第X章“二叉排序树的查找操作”6. 二叉排序树的应用实例：- 内容：实际案例、程序编写、问题解决- 相关章节：课本第X章“二叉排序树的应用”7. 二叉排序树的遍历：- 内容：遍历方法、算法实现、示例演示- 相关章节：课本第X章“二叉树的遍历”8. 总结与拓展：- 内容：二叉排序树的优缺点、拓展知识、高级话题- 相关章节：课本第X章“二叉排序树的总结与拓展”教学进度安排：1. 引言与基本概念（1课时）2. 二叉排序树的性质与定义（1课时）3. 插入与删除操作（2课时）4. 查找操作（1课时）5. 应用实例与程序编写（2课时）6. 遍历方法（1课时）7. 总结与拓展（1课时）三、教学方法1. 讲授法：- 通过对二叉排序树的基本概念、性质和操作进行系统讲解，使学生建立完整的知识体系。
