中小学教育资源及组卷应用平台
第四单元挑战
使用二叉树解简单背包问题
教材分析
本节的主要内容是使用二叉树解简单背包问题。本项目开展的学习、讨论和实践，让学生体验分析问题、提炼方法、建立模型、优化策略的过程，进一步使用二叉树解决实际问题。提升信息意识，提高数据素养，肩负起信息社会责任，从容应对数据时代的各项挑战。
教学目标
1.了解二叉树的概念及其基本操作方法；
2.不同的物品排列顺序对构建二叉树的影响；
3.二叉树的构建；
教学重点
1.不同的物品排列顺序对构建二叉树的影响；
2.二叉树的构建；
教学难点
1.二叉树的构建；
教学方法
体验法、讲授法、讨论法、示例法
教学准备
计算机教室、多媒体设备、多媒体广播软件、教学课件、学生上机练习的程序文件等。
教学过程
一、新课导入
复习二叉树的基本操作，二叉树算术表达式转换为方便计算机处理的后缀表达式的方法以及二叉树如何构建。
二、项目任务
假设现有一个载重量最多为10千克的背包，以及5件物品。其中，第一件物品的重量和价值分别为了千克和9元；第二件物品的重量和价值分别为2千克和8元；第三件物品的重量和价值分别为4千克和7元；第四件物品的重量和价值分别为7千克和16元；第五件物品的重量和价值分别为6千克和15元。那么，此背包中可以放哪些物品，使得重量总和不超过10千克，而价值总和最大呢？
请构建二叉树，列出所有可能的物品放置策略，并选出其中的最优策略(背包里所有物品的价值总和最大，比比哪一组的速度快。
三、项目指引
本项目求解的关键是，判断如果当前背包里的重量与下一件要放入物品的重量的和未超过重量限制，则放入下一件物品；超过重量限制，则不放入下一件物品，而后在两种情况下分别继续同样的判断，如此反复，直至考虑完所有物品。过程中的每一次判断相当于产生了两条策略路径，这与二叉树的树形很像，如图4-12所示。每一个分支结点都表示背包的一种状态，而叶结点表示得出的一种策略。每个结点的左孩子表示放入下一件物品的背包状态(一旦无法放下一件物品则无左孩子)，每个结点的右孩子表示不放入下一件物品的背包状态。
1.假设根结点为背包空的状态，画出二叉树。为方便计算和加快速度，将物品以重量、价值)的形式，按物品顺序从上到下排列在二叉树对应的每一层旁，思考物品的排列顺序对构建二叉树有何影响。
参考答案：
学生可以按照不同的排列顺序将五样物品依次放人背包，不同的排列顺序将构建出不同的二叉树，但列出的所有可能的物品放置策略的总数相同。
假设根节点为背包空的状态，若按照物品、物品2、物品3、物品4、物品5的次序放置，可画出如下二叉树(a)。
假设根节点为背包空的状态，若按照价值最大物品、价值次大物。...值最小物品的次序放置，可画出如下二叉树(b)。
写出最优策略。
参考答案：
装入第一件物品和第四件物品，重量总和为10千克，价值总和为25元。
（a）
(b)
四、交流评价与反思
以自己熟悉的信息表达工具(如演示文稿等)制作电子作品，通过网络或课堂展示交流构建的二叉树和求得的最优策略。并对他人的作品进行评价。
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)(共24张PPT)
使用二叉树解简单背包问题
信息技术沪教版 选择性必修1
第四单元挑战
一、新课导入
二、项目任务
三、项目指引
四、交流评价与反思
一、新课导入
二叉树的基本操作主要有二叉树的创建、二叉树的遍历、求二叉树的深度等。其中二叉树的遍历方法主要有以下几种。
①先序遍历：先访问二叉树根结点，然后先序遍历左子树，再先序遍历右子树。
②中序遍历：先中序遍历左子树，然后访问二叉树根结点，再中序遍历右子树。
③后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问二叉树根结点。
④层次遍历：对二叉树从上到下，逐层从左到右访问每个结点。
前三种属于深度优先遍历，而层次遍历属于广度优先遍历，具体示例如图所示。
先序遍历序列为：ABCDEGF
中序遍历序列为：CBECDFA
后序遍历序列为：CCEFDBA
层次遍历序列为：ABCDEFG
图中所示的左子树和右子树是根结点A的左子树和右子树，在左子树中，结点B可以看成是该子树的根结点。而叶结点D和可以看成是结点B的左子树和右子树(只有个结点的子树)，也是左孩子和右孩子。
了解了二叉树后，依据某一规则对二叉树的结点依次进行访问，就可以得到一个序列。假设有图所示二叉树我们采用先访问其左子树，然后访问根结点，再访问右子树的规则(所有子树也按此规则进行访问)。
具体就是先访问根结点“－”的左子树，由于该左子树的根结点“*”也有自己的左子树即结点3，而结点3并无左子树，所以最先访问的是结点3，继而是“*”……最后访问的是根结点“－”的右子树，即结点7。
通过以上规则访问结点后，便可以得到3*4＋5－7的序列。这样的序列称为中缀表达式，中缀表达式的运算符都位于运算对象的中间。中缀表达式的顺序是和算术表达式一致的，只是缺了括号。
二、项目任务
假设现有一个载重量最多为10千克的背包，以及5件物品。其中，第一件物品的重量和价值分别为了千克和9元；第二件物品的重量和价值分别为2千克和8元；第三件物品的重量和价值分别为4千克和7元；第四件物品的重量和价值分别为7千克和16元；第五件物品的重量和价值分别为6千克和15元。那么，此背包中可以放哪些物品，使得重量总和不超过10千克，而价值总和最大呢？
请构建二叉树，列出所有可能的物品放置策略，并选出其中的最优策略（背包里所有物品的价值总和最大），比比哪一组的速度快。
三、项目指引
本项目求解的关键是，判断如果当前背包里的重量与下一件要放入物品的重量的和未超过重量限制，则放入下一件物品；超过重量限制，则不放入下一件物品，而后在两种情况下分别继续同样的判断，如此反复，直至考虑完所有物品。过程中的每一次判断相当于产生了两条策略路径，这与二叉树的树形很像，如图所示。
每一个分支结点都表示背包的一种状态，而叶结点表示得出的一种策略。每个结点的左孩子表示放入下一件物品的背包状态（一旦无法放下一件物品则无左孩子），每个结点的右孩子表示不放入下一件物品的背包状态。
1.假设根结点为背包空的状态，画出二叉树。为方便计算和加快速度，将物品以（重量、价值）的形式，按物品顺序从上到下排列在二叉树对应的每一层旁，思考物品的排列顺序对构建二叉树有何影响。
学生可以按照不同的排列顺序将五样物品依次放人背包，不同的排列顺序将构建出不同的二叉树，但列出的所有可能的物品放置策略的总数相同。
假设根节点为背包空的状态，若按照物品、物品2、物品3、物品4、物品5的次序放置，可画出如下二叉树(a)。
假设根节点为背包空的状态，若按照价值最大物品、价值次大物。...值最小物品的次序放置，可画出如下二叉树(b)。
2.写出最优策略。
装入第一件物品和第四件物品，重量总和为10千克，价值总和为25元。
（a）
装入第一件物品和第四件物品，重量总和为10千克，价值总和为25元。
（b）
四、交流评价与反思
以自己熟悉的信息表达工具（如演示文稿等）制作电子作品，通过网络或课堂展示交流构建的二叉树和求得的最优策略。并对他人的作品进行评价。
谢谢
21世纪教育网（www.21cnjy.com) 中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php
