浙教版 高中信息技术选修1 5.4 查找算法的程序实现 课件(共14张PPT)

二叉树在对分查找中的应用
玉环中学 林巍
【多选】如下对分查找程序：
i = 1: j = 10: nx = 0
Key = Int(Rnd * 100) + 0.5
Do While i <= j
m = (i + j) \ 2
If Key = a(m) Then
Exit Do
ElseIf Key < a(m) Then
j = m - 1: nx = nx - 1
Else
i = m + 1: nx = nx + 1
End If
Loop
Text1.Text = Str(nx)
已经数组元素a(1)到a(10)分别为“11,26,37,49,55,62,78,79,85,98”，按照该程序执行后，Text1中的内容不可能的数字有（ ）
A．-4　　B．-3　　C．-2　　D．-1　　E．0
F．1　　G．2　　H．3　　I．4
典型题
对分查找模型
Key = Val(Text1.Text)
i = 1: j = 10 : s = ""
Do While i <= j
m = (i + j) \ 2
If Key = a(m) Then
Exit Do 'Exit Do表示退出循环
ElseIf Key < a(m) Then
j = m - 1
Else
i = m + 1
End If
s = s + Str(a(m))
Loop
二叉树的概念
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。
根结点：最上面的结点
叶子结点：没有子结点的结点
二叉树的子树有左右之分
建树——对分查找模型
Key = Val(Text1.Text)
i = 1: j = 10 : s = ""
Do While i <= j
m = (i + j) \ 2
If Key = a(m) Then
Exit Do 'Exit Do表示退出循环
ElseIf Key < a(m) Then
j = m - 1
Else
i = m + 1
End If
s = s + Str(a(m))
Loop
建树
key = Val(Text1.Text)
i = 1: j = 10
Text2.Text = ""
Do While i <= j
m = Int((i + j) / 2 + 0.5)
If key = a(m) Then Exit Do
If key < a(m) Then j = m - 1 Else i = m + 1
Text2.Text = Text2.Text + Str(a(m))
Loop
第3题
探究二叉树的性质
性质1：从每节点出发，往左走数字______，往右走数字______。
性质2：每个节点为每次计算的m值。m、i、j的关系是什么？
若存在左子树，最左边的结点序号就是______，若不存在，就是______。
若存在右子树，最右边的结点序号就是______，若不存在，就是______。
性质3：如果数据找不到，m、i、j的关系是什么？
若往左走出，则__________
若往右走出，则__________
变大
变小
i值
m值
j值
m值
j=m-1
i=m+1
探究二叉树的性质
性质4：每个数所在的______，就是对分查找需要的______；如果找不到，最后走出的__________就是__________。
层数
次数
结点层数
查找次数
【多选】如下对分查找程序：
i = 1: j = 10: nx = 0
Key = Int(Rnd * 100) + 0.5
Do While i <= j
m = (i + j) \ 2
If Key = a(m) Then
Exit Do
ElseIf Key < a(m) Then
j = m - 1: nx = nx - 1
Else
i = m + 1: nx = nx + 1
End If
Loop
Text1.Text = Str(nx)
已经数组元素a(1)到a(10)分别为“11,26,37,49,55,62,78,79,85,98”，按照该程序执行后，Text1中的内容不可能的数字有（ ）
A．-4　　B．-3　　C．-2　　D．-1　　E．0
F．1　　G．2　　H．3　　I．4
解决问题1
第1题
解决问题2
对数组a中6个有序数据“11,22,33,44,55,66”，用下面的程序代码查找数据“23”，程序执行完毕后，下列各变量值正确的是
a(1) = 11: a(2) = 22: a(3) = 33: a(4) = 44: a(5) = 55: a(6) = 66
i = 1: j = 6: p = 0: Key = 23
Do While i <= j
p = p + 1
m = (i + j) \ 2
If j Mod 2 = 0 Then m = m + 1
If a(m) = Key Then Exit Do
If Key < a(m) Then j = m - 1 Else i = m + 1
Loop
A．i = 5 B．j = 4 C．m = 3 D．p = 2
第2题
解决问题3
（2017年4月选考）某对分查找算法的VB程序段如下：
key = Val(Text1.Text)
i = 1: j = 10
Text2.Text = ""
Do While i <= j
m = Int((i + j) / 2 + 0.5)
If key = a(m) Then Exit Do 'Exit Do表示退出循环
If key < a(m) Then j = m - 1 Else i = m + 1
Text2.Text = Text2.Text + Str(a(m))
Loop
数组元素a(1)到a(10)的值依次为“8,17,24,30,36,40,55,58,61,66”，文本框Text1中输入的值是30，执行该程序段，文本框Text2中显示的是
A．40　24 B．40　24　36 C．36　24 D．36　17　24
第3题
小结
二叉树：提供高效解决对分查找的一种新方法，希望同学在今后学习中结合实际情况灵活运用各种方法解决问题
课后思考
如果数据是降序排序，如何建树？
二叉树的建立
常规题型
判断程序运行后的结果
变式题型
任意输入，判断输出的可能结果
通过循环次数推断可能的输入值
M值变化的
……