6.1《树结构及其实现》

6.1树结构及其实现 高中信息技术/教科版/选择性必修1 目录 1.情景导入， 引入新课 2.了解树的 基本概念 3.认识表达式树 4.二叉树的顺序存储实现 5.二叉树的链式存储实现 6.课堂小结 1.情景导入，引入新课 大树的结构由树根、树于、树枝构成，这样的结构跟生物分类体系以及行政区划的层级有什么相同之处？ 本节围绕“无处不在的树”项目展开学习，通过项目活动来学习什么是树结构，如何用顺序存储和链式存储方式实现树结构。本节主要包含“生活中的树”和“算术表达式树的实现”两个任务。 2.了解树的基本概念 任务一生活中的树 活动1表示生物的分类 这样的生物分类体系是不是正像一棵有主干、分枝和树叶的大树?只不过方向是倒立的，根和主干在上，分枝和树叶朝下。 图6.1.1 生物分类体系(部分 ) 任务一生活中的树 活动1表示生物的分类 请根据图 6.1.1填写表6.1.1，并在图6.1.1中将每种生物所属的各层次类别用线圈起来。 任务一生活中的树 活动1表示生物的分类 根据你的观察和理解，回答以下问题。 4.同一个生物会属于不同种类吗? 1.具体的生物会出现在分类体系的哪个位置? 中间还是末端? 具体的生物会出现在分类体系的末端，即最下端。 2.上层的大类和下层的小类之间是什么关系? 一对多的一般——特殊关系，一个大类会包含多个小类，这些小类都是大类增加了一些独特特征而得来的。 3.同一大类下面的几个小类之间是什么关系? 同一个大类下的小类之间都会有一些共同的特征，这些小类距离大类越远，差异就会越大。 不会属于不同的种类，只会属于一个种类。 树结构的基本概念 树结构是对自然界中树的一种抽象和结构仿生。树结构中的分叉部分称为“节点(Node)”，节点之间的连线称为“边(Edge)”。 在对树结构进行图示的时候，其方向正好与自然界中的树相反，对应树根的“根节点(Root Node)”画在上方，对应枝干和树叶的“内部节点(Internal Node)”和“叶节点 (Leaf Node)”画在中间和下方，再用代表边的线连接起来，如图所示。 任务一生活中的树 活动1表示生物的分类 在上图中，(A)节点就是根节点，(B)(C)(D)(E)(J) 节点是内部节点，(F)(G)(H)(I)(K)(L节点是叶节点。 我们将根节点或者内部节点连接的下方节点称为这个节点的“子节点(Child Node)”，相应地，其本身被称作“父节点( ParentNode)”，具有同一个父节点的子节点之间互称“兄弟节点 (SiblingNode)”。例如: (A)节点是(B) (C)(D)节点的父节点; (E)(F) 节点是(B)的子节点; (H (I) (J)节点是弟节点，有共同的父节点(D)。 任务一生活中的树 活动1表示生物的分类 子节点通常也是一棵树的树根，我们把以子节点为树根的这棵树称为“子树(Subtree)”。例如:以(B)为根节点的(B) (E)(F) (K)，就是节点(A)的一子树。节点(A)一共有3个子节点，相应地，它也有3棵子树。 在树结构中，每个节点到根节点之间都有唯一的一条路径(Path)，如(E)节点到根的路径为(E-B-A); (L)节点到根的路径为(L一J-D-A） 按照树结构中每个节点到根节点的路径长度，我们将树结构分为若干层 (Level)。例如: (D)节点位于第2层，(L) 节点位于第4层。一棵树的最大层数称为树的深度 (Depth)。图 6.1.2所的的深度为4。整棵树只有一个根节点的话，树的深度为1。 任务一生活中的树 活动1表示生物的分类 任务一生活中的树 活动2表示行政区划 请根据上图填写表6.1.2，并在图6.1.3 中将每个行政区的直接组成部分用线圈起来。 任务一生活中的树 活动2表示行政区划 根据你的观察和理解，思考并回答以下问题。 1.上层行政区和下层行政区之间是什么关系? 2.同一个行政区下的几个行政区之间是什么关系? 3.一个行政区会隶属于不同的上层行政区吗? 任务一生活中的树 活动2表示行政区划 在树结构中，除根节点外，其余节点有且仅有一个父节点，而可以有多个子节点。我们可以用树结构来表示两种常见的数据关系:“般一特殊”关系和“整体一部分”关系。在“一般一特殊”关系中，父节点表示具有一般性的大类，而大类下的特殊细分小类则是多个子节点，每个小类只属于一个大类。在“整体一部分”关系中，父节点表示事物的整体，而整体的每个部分则是多个子节点，每个部分只归属于一个整体。 树结构及其数据关系 3.认识表达式树 任务二算术表达式树的实现 活动1认识算术表达式树 按照图 6.1.5 所示补全以下创建树的步骤: (1)创建一棵树T，树根是 ; (2)为T插入左子节点，内容是 ; (3)为T插入右子节点，内容是 ,,右子节点记为R; (4)为R插入 ,内容是 ; (5)为R插入 ,内容是 ; T 5 - 左子节点 3 右子节点 1 由于运算符要连接两个运算数，而运算数之间不会直接连接，所以我们用内部节点来表示运算符，叶节点表示运算数。 任务二算术表达式树的实现 活动1认识算术表达式树 用来表示表达式的树结构称为“表达式树”，由于每个节点只有左、右两个子节点，所以也称作“二叉树”。请注意运算的次序，画出下列表达式的树结构，并写出这些表达式树的创建步骤: ( 1)(3+4)*(9-6) (2) 1+3*4-9/3 任务二算术表达式树的实现 活动1认识算术表达式树 我们为二叉树抽象数据类型(ADT BinaryTree)定义了如下接口。 ADT BinaryTree: BinaryTree(val):创建一棵二叉树，树根内容为val。 getLeftChild0:返回左子节点为根的左子树。 getRightChild0:返回右子节点为根的右子树 setRootValue(val):将二叉树树根的内容设置为val。 getRootValue0:返回二树树根的内容。 ·insertLeft(val):给二叉树插入左子树，其树根内容为val，并返回左子树。 ·insertRight(val):给二叉树插入右子树，其树根内容为val，并返回右子树。 任务二算术表达式树的实现 活动2 用抽象数据类型创建表达式树 有了二叉树抽象数据类型，我们就可以把前面的表达式树的创建过程写成程序了。例如，“3-1”对应的程序如下。 01.T=BinaryTree("-"） 02.T.insertLeft(3) 03.T.insertRight(1) 请自行写出创建下列3 个表达式树的程序: 5+(3-1); (3+4)*(9-6); 1+3*4-(9/3) 4.二叉树的顺序存储实现 任务二算术表达式树的实现 活动2 用抽象数据类型创建表达式树 可以利用 Python的内置数据类型列表实现二叉树抽象数据类型。我们约定，表示二叉树的列表恰好包含3个元素，第1项元素是树根内容，第2、第3项元素分别是左子树和右子树，如果没有左、右子树，则设置为空列表。实际上，左、右子树也是二叉树，所以这个列表将会是一个嵌套列表。如图所示是一棵二叉树及其对应的顺序存储实现。 这样，对于一棵顺序存储实现的二叉树T而言，T[O]就是树根，而 T[1]和 T[2]则分别是左、右子树。如果 T的左、右子树不为空的话，还可以继续引用它们的子树。例如，T[1][O]是B，T[1][1]则是 B 的左子树。 任务二算术表达式树的实现 活动3表达式树的顺序存储实现 如果二叉树抽象数据类型用顺序存储来实现，表达式树看起来会是什么样的?例如，表达式“3-1”表示为一个3元素嵌套列表后如图所示。 请继续写出下列3个表达式的表达式树及其列表实现: 5+(3-1); (3+4)*(9-6) 1+3*4-(9/3) 任务二算术表达式树的实现 活动3表达式树的顺序存储实现 我们把二叉树的顺序存储表示用Python 的类来编程实现。首先是用类的构造函数_init()来实现ADT BinaryTree 中的创建二叉树接 BinaryTree(val) 01. class BinaryTree: 02.def __init__(self, val_or_list):02. 03.if type(val_or_list) is list: 04.self.items=val or_list 05.else: 06.self.items=[val_or_list,[],[]] 任务二算术表达式树的实现 活动3表达式树的顺序存储实现 insertLeft的接口实现如下: 07.def insertLeft(self， val): 08.oldLeft=self.items.pop(1) #取到现有的左子树#如果09.现有左子树不为空,把它作为新左子节点的左子树 10.if len(oldLeft)>1: 11.self.items.insert(1，[val， oldLeft，[]]) 12.#如果现有左子树为空,则插入新的左子节点作为左子树 13.else: 14.self.items.insert(1，[val，[]，[]])return 15.BinaryTree(self.items[1])#返回刚插入的左子树 任务二算术表达式树的实现 活动3表达式树的顺序存储实现 getLeftChild是获取二叉树的左子树，其代码实现非常简单，只要返回第 2个元素即可。 16.def getLeftChild(self): 17.BinaryTree(return self.items[1]) getRightChild的接口实现也只需要返回第3个元素即可，在此不再赘述。getRootValue和setRootValue这一对接口涉及树根的操作，与列表的第1个元素相关，其实现代码如下: 18.def getRootValue(self): 19.return self.items[0] 20.def setRootValue(self， val): 21.self.items[0]=val 5.二叉树的链式存储实现 实现二叉树的另一种更为通用的方式是基于节点引用的链式存储方式，许多其他编程语言如 C语言可以通过指针等方式来实现链式存储，所以可以采用同样的方法来实现二叉树。在链式存储实现中，每个二叉树节点对应一个节点对象，每个节点对象具有两个属性分别引用本节点的左、右子树，如果没有左、右子树，则引用设置为None。 二叉树的链式存储实现 任务二算术表达式树的实现 活动3表达式树的顺序存储实现 如果二叉树抽象数据类型用链式存储来实现，表达式树看起来会是什么样的?例如，表达式“3-1”表示为一个链式存储结构后如图所示。 任务二算术表达式树的实现 活动4表达式树的顺序存储实现 请继续画出下列3个表达式的表达式树及其链式存储实现: 5+(3-1) (3+4)*(9-6) 1+3*4-(9/3) 我们把二叉树的链式存储也用 Python 的类来编程实现。首先是用类的构造函数init0来实现ADT BinaryTree中的创建二叉树接 BinaryTree(val) 01.class BinaryTree(): 02.def__init__(self, val): 03.self.value=val 04.self.leftChild=self.rightChild=None 任务二算术表达式树的实现 活动4表达式树的顺序存储实现 05.def insertLeft(self， val): 06.#如果现有左子树不为空,把它作为新左子节点的左子树 07.if self.leftChild is not None: 08.newLeft=BinaryTree(val) 09.newLeft.leftChild=self.leftChild #注意赋值顺序10.self.leftChild=newLeft 11.#如果现有左子树为空,则插人新的左子节点作为左子树 12.else: 13.self.leftChild=BinaryTree(val) 14.return self.leftChild #返回刚插入的左子树 任务二算术表达式树的实现 活动4表达式树的顺序存储实现 15.def getLeftChild(self): 16.return self.leftChild 17.def getRootValue(self): 18.return self.value 19.def setRootValue(self， val): 20.self.value=val 任务二算术表达式树的实现 活动4表达式树的顺序存储实现 6.课堂小结 本节课我们学习了树结构的基本概念和相关术语，以及二又树的抽象效据类型接口、算术表达式树实例、嵌套列表与节点链接两种二叉树实现方法。 作业布置：请同学们认真完成教材中的拓展练习。 下节课见！ $$