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

第五单元挑战

使用二叉树查找树查找学生成绩信息

❑教材分析

本节的主要内容是使用二叉树查找树查找学生成绩信息。本项目开展的学习、讨论和实践，让学生学习二叉树查找树的算法，进一步运用二叉查找树算法解决实际问题，并讨论使用二叉查找树的优缺点。提升信息意识，提高数据素养，肩负起信息社会责任，从容应对数据时代的各项挑战。

❑教学目标

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=None

self.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,parent

if node.score==score:

return True,node.address,node.count

if 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_node

else:

p.lchild=new_node

bst=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+2

count1=count1-1

else:

print('not exist')

*4.讨论使用二叉查找树的优缺点。

图5-17示例

(4)讨论使用二叉查找树的优缺点。

优点：二叉查找树查找速度快，采用链式存储结构，在增加结点时比较方便

缺点：二叉查找树在删除结点时，需要对以该结点为根的左右子树上的结点进行修改，删除结点的算法比较复杂

四、交流评价与反思

以自己熟悉的信息表达工具(如演示文稿等)制作电子作品，通过网络或课堂展示交流自己的算法和程序，并对他人的作品进行评价。