沪教版（2019）选修1 数据与数据结构单元挑战 使用二叉查找树查找学生成绩信息完美版课件ppt

这是一份沪教版（2019）选修1 数据与数据结构单元挑战 使用二叉查找树查找学生成绩信息完美版课件ppt，文件包含第五单元挑战pptx、第五单元挑战doc、第五单元挑战mp4等3份课件配套教学资源，其中PPT共23页， 欢迎下载使用。
第五单元挑战 使用二叉树查找树查找学生成绩信息❑教材分析本节的主要内容是使用二叉树查找树查找学生成绩信息。本项目开展的学习、讨论和实践，让学生学习二叉树查找树的算法，进一步运用二叉查找树算法解决实际问题，并讨论使用二叉查找树的优缺点。提升信息意识，提高数据素养，肩负起信息社会责任，从容应对数据时代的各项挑战。❑教学目标1.了解二叉树的算法；2.运用二叉树查找树算法；3.二叉查找树的优缺点；❑教学重点1.运用二叉树查找树算法；2.二叉查找树的优缺点；❑教学难点1.二叉树查找树算法；❑教学方法体验法、讲授法、讨论法、示例法❑教学准备　　计算机教室、多媒体设备、多媒体广播软件、教学课件、学生上机练习的程序文件等。❑教学过程一、新课导入教师演示二叉查找树的查找过程。二、项目任务二叉查找树(也称二叉排序树)：对于树中的每个结点k,若k的左子树不空，则左子树上所有结点的值均小于k结点的值；若k的右子树不空，则右子树上所有结点的值均大于k结点的值。二叉查找树是适用于查找的二叉树，查找方法是：(1)若待查值等于根结点的关键字，则查找成功；(2)若待查值小于根结点的关键字，则继续在左子树上进行查找；(3)若待查值大于根结点的关键字，则继续在右子树上进行查找；图5-16 二叉树查找总是从树根开始，比如在图5-16所示二叉树中查找关键字25。先与树根28比较，25<28，往左走继续与20比较，因25>20，往右走与25比较，此时两数相等，查找结束。请以二叉查找树为索引对学生成绩进行查找二叉树存储成绩，单链表存储学生信息，数据结构形式为：树结点结构为：(分数，左孩子指针，右孩子指针，本分数学生链首指针)表结构形式为：(学号，姓名，指向下一结点指针) 三、项目指引1.根据本小组同学的成绩，画出二叉查找树的结构图(参考图5-17)。 2.设计二叉查找树根据成绩查找学生信息的算法流程。使用二叉树查找树查找成绩，查到该分数学生在主表中的地址，根据地址等信息输出该分数学生的信息民。使用二叉查找树查找成绩的算法：➯上若根结点的关键字值等于查找的关键字，查找成功。➯否则，若小于根结点的关键字值，递归查左子树：若大于根结点的关键字值，递归在右子树。➯若子树为空，查找不成功。*3.编程实现。 class Node(object)：def_init_(self,address,count,score)：self.address=address  #address表示该成绩学生在学生信息列表r中的起始下标self.count=count  #count表示该成绩学生在学生信息列表r中的人数self.score=score  #score表示成绩self.lchild=Noneself.rchild=None class BST:def_init_(self,address,count,score)：self.root=Node(address,count,score)#搜索def search(self,node,parent,score)；if node is None:return False,node,parentif node.score==score:return True,node.address,node.countif node.score>score:return self.search(node.lchild,node,score)else:return self.search(node.rchild,node,score)#插入def insert(self,address,count,score):fag,n,p=self.search(self.root, self.root,score)if not flag:new_node=Node(address,count,score)if score>p.score:p.rchild=new_nodeelse:p.lchild=new_nodebst=BST(7,2,75)  #创建二叉查找树bst.insert(3,1,65) #依次插入各个结点bst.insert(1,1,61)bst.insert(5,1,68)bst.insert(11,3,86)bst.insert(19,1,95)bst.insert(17,1,90)r=[0,1,’吴兵’,3,’李丽’,5,’赵军”,12,’张红’,25,’丁敏’,8,’王芳’,39,’黄俊’,52,’张峰’,46,‘钱军’,33,’李想']key=75 #k为查找成绩flag,address1,count1=bst.search(bst.root,bst.root,key)if flag==True:while count1>0:print(r[address1]，r[address1+1])address1=address1+2count1=count1-1else:print('not exist') *4.讨论使用二叉查找树的优缺点。图5-17示例(4)讨论使用二叉查找树的优缺点。优点：二叉查找树查找速度快，采用链式存储结构，在增加结点时比较方便缺点：二叉查找树在删除结点时，需要对以该结点为根的左右子树上的结点进行修改，删除结点的算法比较复杂 四、交流评价与反思以自己熟悉的信息表达工具(如演示文稿等)制作电子作品，通过网络或课堂展示交流自己的算法和程序，并对他人的作品进行评价。