6.2《用二叉树排序》

6.2用二叉树排序 高中信息技术/教科版/选择性必修1 目录 1.情景导入， 引入新课 2.手动操作，理解二叉排序树 3.设计算法 4.课堂小结 1.情景导入，引入新课 刚刚学过的二叉树，有什么用？ 如果二叉树的左右子树分别存储比父节点小和比父节点大的数据，这样会构造出具有什么性质的二叉树？ 本节围绕“树的递归处理”项目展开学习，通过项目活动来理解什么是二叉排序树，如何用二叉树结构实现排序。本节主要包含“通过实例认识二叉排序树”和“利用二叉树结构实现排序”两个任务。 2.手动操作，理解二叉排序树 请将如图所示的数据依照从左到右的次序，按照“左子节点<父节点<=右子节点”的规则组织成一棵二叉树。 任务一通过实例认识二叉排序树活动1用二叉树组织数据 组织过程如下。 1.首先是数据70，由于二叉树里没有节点，它自然成为唯一的根节点2.其次是数据31，我们从根节点70开始对比，由于31<70，所以31应该是70的左子节点。 3.再次是数据93，我们还从根节点70开始对比，由于70<93，所以93 应该是70的右子节点。 4.最后是数据94，我们还从根节点70开始对比，由于70<94，所以94应该是70的右子节点，但这已被93占据，我们继续将94与93对比，由于93<94，所以94应该是93 的右子节点。这样，我们就将4个数据组织成了一棵二叉树，如图所示。 任务一通过实例认识二叉排序树活动1用二叉树组织数据 任务一通过实例认识二叉排序树活动1用二叉树组织数据 请按照“左子节点<父节点<=右子节点”的规则，将剩下的 5个数据依次填进二叉树模板中。填写完毕后，模板中还会留下6个空格，请忽略这些空格。 14 23 73 71 96 二叉排序树 二叉树中的每个节点最多可能有左、右两个子节点，而二叉树的层次是没有限制的。这样，我们按照“左子节点 < 父节点 <右子节点”的顺序，将任意数量的数据组织成一棵二叉树，再有序输出二叉树的每个节点，即可实现数据排序。根据这样的大小次序规则组织成的二叉树，就叫作二叉排序树。 任务一通过实例认识二叉排序树活动1体验相同的数据，不同的树 我们发现，在组织二叉排序树的过程中，数据集里的第一个数据总是成为根节点，对于相同的一组数据，由于插入的顺序不同，会组织成不同的二叉排序树。 同样是活动1中的9个数据，我们将70和73 的位置对调一下，如图所示。 任务一通过实例认识二叉排序树活动1体验相同的数据，不同的树 将从73 开始的数据依次插入节点，会重新生成二叉排序树。请将结果填写在如图所示的模板中。 请讨论以下问题: 1.是否只要插入数据的次序有所不同，就会生成不同的二叉排序树? 2.对于一个包含 n个数据的数据集，可以生成多少种不同的二叉排序树? 73 31 93 14 70 94 23 71 96 二叉树的高度 同一个数据集，由于插入数据节点的次序不同，能够生成差异很大的二叉排序树。如所有节点都仅有左子节点，或者仅有右子节点，这样会使二叉排序树的高度等于数据的个数。而所有节点中，如果最多一个节点仅有左子节点，其余的内部节点都拥有左、右子节点，会使二叉排序树的高度最小化。 任务一通过实例认识二叉排序树 活动3输出排序结果 组织生成二叉排序树是实现排序的第一步，接着还要输出所有二叉树节点，才算最终完成数据排序。由于二叉树不是线性结构，无法按照前驱后继的次序来输出节点，为了保持“左子节点<父节点<=右子节点”的节点顺序，我们输出节点时，也要按照“左子树所有节点一父节点一右子树所有节点”的次序进行。 例如，如图所示的二叉排序树的输出为“13，45，56” 任务一通过实例认识二叉排序树 活动3输出排序结果 而下图所示的二叉排序树，由于左子树不仅仅是一个节点，我们将左子树也按照“左子树所有节点一父节点一右子树所有节点”的次序来输出。 这样，左子树输出为“9，13，30”接着输出父节点45，再输出右子树所有节点56。最后，总输出结果为“9，13，30,45，56”。 任务一通过实例认识二叉排序树 活动3输出排序结果 接下来，观察图所示的二叉排序树，注意区分左子树、父节点和右子树。直接在图中用线标示出左、右子树，并按照“左子树所有节点一父节点一右子树所有节点”的次序来输出所有数据，把结果填写在下面。 9 13 30 45 56 72 任务一通过实例认识二叉排序树 活动3输出排序结果 将活动1中组织好的二叉排序树，按照同样的方式，用线标示出每一个左、右子树，并将所有节点数据输出，把结果填写在下面。 最后，将活动 2中组织好的二叉排序树，也按照同样的方式用线标示出每一个左、右子树，并将所有节点数据输出，把结果填写在下面。 对比上面两个输出结果，它们是否相同?为什么不同的二叉排序树会输出相同的结果? 14 23 31 70 71 73 93 94 96 14 23 31 70 71 73 93 94 96 有序输出二叉排序树的节点 排序按照“子所有节点一节点一右子所有节点”的次序来输出所有节点数据，就能得到排好序的数据集。只要是同一组数据生成的二叉排序树，无论其结构有多大差异，都输出相同的有序数据集.。 任务一通过实例认识二叉排序树 活动3输出排序结果 二叉排序树用于数据查找 查找过程如下: (1) 如果当前节点数据等于要查找的数据，则查找成功，结束查找; (2)如果要查找的数据比当前节点数据小，则进入左子节点比对，如果当前节点没有左子节点，则查找失败，结束查找; (3) 如果要查找的数据比当前节点数据大，则进入右子节点比对，如果当前节点没有右子节点，则查找失败，结束查找; (4)重复(1)~(3)，直到查找成功或者失败，结束查找。 3.设计算法 任务二 利用二叉树结构实现排序 活动1建立数据结构 我们来实现一个用二叉树对数据集进行排序的函数BinaryTreeSort(lst)，函数参数lst是原始数据列表，函数返回排好序的数据列表。 我们需要构建一棵二叉树，首先将列表中的第一个数据作为二叉树的首个节点——根节点。请补全下面的代码。 01. def BinaryTreeSort(lst): 02.btree=BinaryTree（ ） lst[0] 利用二叉树结构对一组数据进行排序，需要一棵二叉树来容纳数据集里的所有数据，并通过左、右子树来体现数据之间的大小关系，即左子树所有节点的数据都小于父节点的数据，而父节点的数据小于右子树所有节点的数据。将数据集中的数据加入二叉排序树的过程中，二叉排序树应始终保持这个性质。 任务二 利用二叉树结构实现排序 活动2设计算法 如前所述，利用二叉树结构实现排序的算法分为组织二叉排序树和输出所有节点数据两个步骤。其算法描述如下。 (1)将列表lst中的每个数据项item插入二叉排序树btree中 (2)将二叉排序树 btree 中的节点数据按规则加入列表result。 (3)函数返回result。 根据上述算法，补全下面的代码。 03. for item in lst[ ]: #从第2个数据项开始 04.#调用函数，将item插入btree 05.BSTInsertItem(btree，item) 06.#调用函数，输出 btree所有节点 07.result=BSTOutput(btree) 08.return . 1: result 任务二 利用二叉树结构实现排序 活动2设计算法 接下来，我们对算法中调用的BSTInsertItem和BSTOutput 两个函数进一步细化，确定其算法。 函数 BSTInsertItem(btree,item)将数据项 item 插入二叉排序树btree中，其算法描述如下。 (1)将item与二叉排序树的根节点数据进行比对。 (2)如果item 小于根节点数据，则如果左子树存在，将item插入左子树;如果左子树不存在，将item作为新左子树插入。 (3)如果item不小于根节点数据，则如果右子树存在，将item插入右子树;如果右子树不存在，将item作为新右子树插入。 任务二 利用二叉树结构实现排序 活动2设计算法 根据上述BSTInsertItem函数的算法，补全下面的代码。 09. def BSTInsertItem(btree，item): 10.val=btree.getRootValue() #val是根节点 11.if item<val: #item小于根节点数据 12.lbtree=btree.getLeftChild() #lbtree是左子树 13.if Ibtree is None: #没有左子树 14.btree.insertLeftChild(item) 任务二 利用二叉树结构实现排序 活动2设计算法 15.else: 16.BSTInsertItem(lbtree， item) 17.else: #item不小于根节点数据 18.rbtree=btree. . 19. . 20. . 21. . 22. . getRightChild() if rbtree is None: btree.insertRight(item) else BSTInsertItem(rbtree,item) 任务二 利用二叉树结构实现排序 活动2设计算法 函数BSTOutput(btree)将二叉排序树 btree 中所有节点数据输出为列表并作为结果返回，其算法描述如下。 (1)如果 btree 有左子树，则输出左子树所有节点数据，添加到result列表中。 (2)将btree根节点数据添加到result列表中 (3)如果 btree 有右子树，则输出右子树所有节点数据，添加到result列表中。 (4)返回result列表。 任务二 利用二叉树结构实现排序 活动2设计算法 23. def BSTOutput(btree): 24.result=[] 25.lbtree=btree.getLeftChild() 26.if lbtree is not None: 27.result=result+BSTOutput(Ibtree) 28.result.append(btree.getRootValue()) 29.rbtree=btree. . 30. . 31. . 32.return result btree.getRightChild() if rbtree is not None: result.extend(BSTOutput(rbtree)) 任务二 利用二叉树结构实现排序 活动2设计算法 将新的数据插入二叉排序树，首先从根节点开始比对，如果新数据比根节点数据小，则表示它应该被插入到左子树中。这样，如果左子树为空，那么新数据就成为左子树:如果不为空，则将新数据插入左子树，具体算法就可以直接以左子树作为参数，递归调用新数据插入二叉排序树函数。如果新数据比根节点数据大，则表示它应该被插入到右子树中，此时可以通过同样的思路来设计算法。 要将二叉排序树节点数据有序输出，只需先有序输出左子树所有节点，再输出根节点，最后输出右子树所有节点。这样，如果左、右子树为空，无须做任何处理，否则都可以用左、右子树作为参数，递归调用二叉排序树节点数据有序输出函数。 递归算法应用 4.课堂小结 本节课我们学习了二叉排序树的基本概念和创建操作及其在排序中的应用，以及应用递归方法构建二叉排序树，进行中序遍历输出数据以实现排序的算法。 作业布置：请同学们认真完成教材中的拓展练习。 下节课见！ $$