第14课 二叉树的基本操作与抽象数据类型-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第14课　二叉树的基本操作与抽象数据类型(见学生用书P105) ——4.2　二叉树的基本操作　4.3　抽象数据类型，教材P106～118 1.掌握使用数组和链表等数据结构建立二叉树的方法。　2.掌握二叉树遍历的基本操作方法。　3.了解抽象数据类型的概念。 1． 二叉树的遍历 建立二叉树的操作，可以按照　层　的顺序进行，先由第　1　层开始，依次到下一层，在每一层中按照　从左到右　的顺序创建节点。 (1)数组实现 ①完全二叉树：用数组表示完全二叉树，从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为　0　，最后一个节点的编号为　n－1　。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 ②非完全二叉树：用数组表示非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示，数据存储时对应位置空缺，其他节点在数组中的位置参照完全二叉树。 ③对于一般的二叉树来说，一个深度为k且只有k个节点的树需要2k－1个节点的存储空间才能表示出来，容易造成存储空间的浪费。 (2)链表实现 用链表实现二叉树，每个节点至少需要　3　个域，一个　数据域　和两个　指针域　。数据域用于存放本节点的　数据信息　，左右两个指针域分别指向节点的　左孩子和右孩子　。 (3)list构造二叉树法 ①空树用None表示。 ②非空二叉树用包含三个元素的列表[d，l，r]表示，其中：d表示根节点的元素，l和r是两棵子树，采用与整个二叉树同样结构的list表示。例如： 2． 二叉树的遍历 (1)二叉树的遍历，是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被　访问一次且仅被访问一次　。二叉树的遍历方式有很多，主要有　前序遍历　、　中序遍历　、　后序遍历　等。 ①前序遍历：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。简单描述：　根左右　；把每层的子树看成一个单独的树，依然按照前序遍历进行。 ②中序遍历：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。简单描述：　左根右　；把每层的子树看成一个单独的树，依然按照中序遍历进行。 ③后序遍历：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。简单描述：　左右根　；把每层的子树看成一个单独的树，依然按照后序遍历进行。 (2)表达式树： 将数学表达式中的运算数和运算符视为二叉树的每个节点，那么可以构造出各种表达式树，如图所示是一棵表达式树。 二叉树实行中序遍历，将得到遍历序列：8－(3＋2*6)/5＋4， 即人们平时习惯书写的数学表达式， 也称为中缀表达式。 二叉树实行后序遍历，那么得到遍历序列：8326*＋5/－4＋，称为后缀表达式(也称逆波兰表达式)。 书写后缀表达式时， 因为采用了运算符紧跟在两个操作数之后的方法，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右依序完成计算，并方便求得结果。 3．抽象数据类型 (1)数据类型与抽象数据类型 ①数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 ②抽象数据类型是指一个数学模型及定义在该模型上的一组操作，即一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。 (2)抽象数据类型(ADT)的描述 ①定义一个抽象数据类型，需要清晰地表述出各方面的形式要求(如操作的名字、参数的个数和类型等)和功能要求(希望这个操作完成什么样的计算或产生什么效果等)。 ②抽象数据类型的标准格式： ADT 抽象数据类型名： Data 数据元素之间逻辑关系的定义 Operation 操作1 初始条件 操作结果描述 操作2 …… 操作n …… end ADT 1． 通过“前序遍历序列＋中序遍历序列”或“中序遍历序列＋后序遍历序列”可以确定唯一的一棵二叉树；但通过“前序遍历序列＋后序遍历序列”无法确定唯一的一棵二叉树。 例如，一棵二叉树的中序遍历序列为“DBGEHAFIC”，后序遍历序列为“DGHEBIFCA”，请画出这棵二叉树。 分析：首先在后序遍历中找到根节点“A”， 再由中序遍历得到左子树和右子树， 然后再在子树中继续重复这一过程。 2． 用数组构建二叉树的Python代码： create_tree(tree，data)： for i in range(len(data))： depth＝0　#程序的第0层相当于树的第1层 if i＝＝0：　 #根节点 　　tree[depth]＝data[i] else： while tree[depth]！＝0： if data[i]>tree[depth]： depth＝depth*2＋2　 #父节点的右孩子位置 else： depth＝depth*2＋1　 #父节点的左孩子位置 tree[depth]＝data[i] #找到数据应存放的节点位置，并存储该节点 3．二叉搜索树(二叉排序树)： (1)一棵空树或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势，所以应用十分广泛。例如，在文件系统和数据库系统中，一般会采用这种数据结构进行高效率的排序与检索操作。 4．利用类创建域遍历二叉树(了解) #二叉树节点类 class TreeNode： def 　init　(self，x)： self.val＝x self.left＝None self.right＝None #列表创建二叉树 def listCreatTree(root，llist，i)： if i <len(llist)： if llist[i]＝＝'#'： return None　#这里的return很重要 else： root＝TreeNode(llist[i]) #往左递推 root.left＝listCreatTree(root.left，llist，2*i＋1)　#从根开始一直到最左，直至为空 #往右回溯 root.right＝listCreatTree(root.right，llist，2*i＋2)　#再返回上一个根，回溯右 #再返回根 return root　#这里的return很重要 return root #先序遍历二叉树 def preOrderBT(root)： if not root： return None print(root.val， end＝'\t') preOrderBT(root.left) preOrderBT(root.right) #中序遍历二叉树 def midOrdBT(root)： if not root： return ”#” midOrdBT(root.left) print(root.val，end＝”\t”) midOrdBT(root.right) 　　#后序遍历二叉树 def afterOrdBT(root)： if not root： return ”#” afterOrdBT(root.left) afterOrdBT(root.right) print(root.val，end＝”\t”) if 　name　＝＝'　main　'： 　list＝['1'， '2'， '3'， '#'， '4'， '5'， '6'] root＝listCreatTree(None， llist， 0) #p＝root print(”．............................”) preOrderBT(root) print() midOrdBT(root) print() afterOrdBT(root) 　　一棵二叉树的形态如下图所示，其对应的数组表示为(　A　) 　　　　　　　　　　　　　 0 1 2 3 4 5 6 7 8 A B C D E F G 　　　　　A．　　　　　 0 1 2 3 4 5 6 A B C D E F G 　　　　B． 0 1 2 3 4 5 6 7 8 A B C D E F G 　　　　　C． 0 1 2 3 4 5 6 7 8 A B C D E F G 　　　　D． 【解析】 用数组表示非完全二叉树，需先将它补全为一棵完全二叉树，然后从根节点开始，从上而下、自左往右的顺序进行编号，节点编号与数组的下标一一对应，选项A正确。 变式1用一维数组表示二叉树，如下表所示。下列关于该二叉树的说法中，正确的是(　A　) 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 　　A．该二叉树中共有3个叶子节点　　　　　　　B．该二叉树是满二叉树，其深度为4 C．该二叉树是完全二叉树，其根节点是A D．该二叉树的中序遍历结果为FDGBAEC 【解析】 二叉树的形态如下图所示： 该二叉树不是满二叉树，故选项B错误；该二叉树不是完全二叉树，故选项C错误；该二叉树中有3 个叶子节点，分别为F，G，E，故选项A正确；该二叉树的中序遍历结果为BFDGACE，故选项D错误。 　　二叉树可以用数组和链表存储，如图所示为用链表存储的二叉树，其对应的数组表示为(　C　) 　　 0 1 2 3 4 5 6 7 8 A B C D E F G 　　　　　　 0 1 2 3 4 5 6 A B C D E F G 　　 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 0 1 2 3 4 5 6 7 8 A B C D E F G 【解析】 用链表实现二叉树，左右两个指针分别指向节点的左孩子和右孩子，补全为一棵完全二叉树，然后从根节点开始，从上而下、自左往右的顺序从0开始编号，并将其放入数组对应的位置，选项C正确。 　　某二叉树如图所示，用list表示该二叉树为(　D　) A．[5，2，1，3，4] B．[5，[2，[1，None，None]，None]，[3，[4]]] C．[5，[2，[1]]，[3，[4，None，None]]] D．[5，[2，[1，None，None]]，[3，[4，None，None]，None]，None] 【解析】 用list实现二叉树，空树用None表示，非空二叉树用三个元素的列表[根节点，左子树节点，右子树节点]表示，左右子树也采用相同的方式处理，因此该二叉树的表示为选项D。 　　2023·浙江1月选考下列二叉树中，中序遍历结果为BAEDFC 的是(　C　) 　　　　A．　　　　　　　　　B．　　　　　　　　C．　　　　　　　　D． 【解析】 本题考查二叉树遍历的基本操作。中序遍历的特点：左子树→根→右子树，每个子树，都遵循以上规定基础解法。4 个二叉树遍历结果分别为：选项A，EDFBAC；选项B，BEDFAC；选项C，BAEDFC；选项D，BACEDF，选项C正确。快速解法：4 个选项的根节点都是A，根据遍历结果，左子树只有节点B，排除选项A、B。选项C、D 中，右子树的根节点都是C，中序遍历节点C 在最后，说明节点C 没有右子树(右子树为空)，排除选项D，选项C正确。 变式1有一棵二叉树如图所示，该二叉树的后序遍历结果正确的是(　D　) 　　　　　　　　　　 A．XBCDAYEF B．FEYADCBX C．DBEAFXCY D．DEFABYCX 【解析】 后序遍历的规则是先访问左子树，再访问右子树，最后访问根节点，选项D正确。 变式22023·鄞州中学检测已知二叉树T2 的后序遍历序列为GDHEBIFCA，中序遍历序列为DGBEHACIF，则二叉树T2 的前序遍历序列为(　B　) A．ABDGEHCIF B．ABDGEHCFI C．ABDGEHFCI D．该二叉树的形态不唯一，无法确定 【解析】 通过其后序遍历(左右根)序列和中序遍历(左根右)序列确定其二叉树的形态：①通过后序遍历序列确定其根为A，再通过中序遍历序列确定左子树为DGBEH，右子树为CIF。 ②研究其左子树：通过后序遍历序列GDHEB 和中序遍历序列DGBEH，可以确定根为B，左子树为DG，右子树为EH，左子树的后序遍历序列GD 和中序遍历序列DG 可以确定其形态。右子树的后序遍历序列HE 和中序遍历序列EH可以确定其形态。 ③研究其右子树： 通过后序遍历序列IFC 和中序遍历序列CIF，可以确定根为C，左子树为空，右子树为FI，右子树的后序遍历序列IF 和中序遍历序列IF 可以确定其形态如下图所示。故其前序遍历序列为ABDGEHCFI，选项B正确。 变式3有二叉树用数组表示为：[“A”，“B”，“C”，None，“D”，“E”，“F”，None，None，None，“G”]，则下列关于该二叉树的说法中，正确的是(　A　) A．该二叉树中度为1 的节点有2 个 B．该二叉树一共有3 层 C．该二叉树的叶子节点有4 个 D．该二叉树的中序遍历序列是BGDAECF 【解析】 根据题干中的提示可以画出二叉树的示意图如下，由此我们可以分析出该二叉树度为1 的节点有2 个，故选项A正确；该二叉树一共有4 层，该二叉树中的叶子节点有3 个，该二叉树的中序遍历序列是BDGAECF，故选项B、C、D 不正确。 变式4某二叉树前序遍历的结果为“大好河山”，则中序遍历的结果不可能是(　C　) A．大好河山　　　　　B．河山好大　　　　　C．好山大河　　　　　D．山河好大 【解析】 选项A的树如图1所示；选项B的树如图2所示；选项D的树如图3所示。 　　表达式树是包含表达式的数据结构，表达式树对于一些高性能的场景下有较大实用性。如图1所示，一个数学表达式可以用一棵表达式树来表示。下列关于该表达式树的说法中，不正确的是(　A　) A．表达式树的根节点左右子树的深度不会超过1 B．对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理 C．该表达式树对应的表达式为(6－3)/2＋5*(7＋2)/8 D．该表达式树中的内部节点比分支节点少1个 　　　　　　　　　　　　　　　图1　　　　　　　　　　　　　　　　图2 【解析】 选项B，就是后序表达式的相关概念，选项正确；选项C，根据图，可以到对应的表达式，选项正确；选项D，内部节点，就是不包括根节点的所有分支节点，所以少一个，选项正确。 变式1对于数学运算来说，其本质是一个分层的递归结构。每一步计算都是一个操作符作用于相应的操作对象，其操作对象又可以是一个操作数或任意复杂的表达式，而树的递归结构正好可以用来表示这种表达式，以数学表达式 (3＋2)*6为例，将其转换为表达式树如图2所示。现有数学表达式“3*(4＋5)＋2”，其对应的表达式树是(　B　) 　　　　 A．　　　　　　　　B．　　　　　　　 C．　　　　　　 　D． 【解析】 根据表达式中计算的优先次序，从底层开始逐层画出对应的表达式树，选项B正确。 　　2023·学军中学检测创建一个简单的ADT，如下所示： class odd()： def __init__(self，data)： #初始化属性data self.data＝data def pd(self)： if self.data%2＝＝0： print(self.data，”是偶数”) else： print(self.data，”是奇数”) #创建实例： my_pro＝odd(12) my_pro.pd() 下列关于该抽象数据类型(ADT)实例的说法中，不正确的是(　B　) A．创建的类名称为odd B．def pd(self)的功能是定义pd()函数 C．程序代码执行后的结果为“12是偶数” D．my_pro为odd类的一个对象 【解析】 def pd(self)的功能是定义pd操作，选项B错误。 　　小明在学习了二叉树的相关知识后，认为可以通过二叉树实现数组的排序。如有数组a＝[8，9，15，2，12，4，10]，先将a[0]作为根节点建立二叉树，对于数组a 中的其他元素，遵循“比根节点小的数放左边、比根节点大的数放右边”的原则，依次将a[i]放入二叉树中。最后将这棵树进行中序遍历就可以得到从小到大的排序结果。Python代码如下： a＝[8，9，15，2，12，4，10] tr＝[[a[0]，－1，－1]] for i in range(1，len(a))： q＝p＝0 k＝1 while p！＝－1： if tr[p][0]>a[i]： k＝1 q＝p p＝tr[p][1] else： k＝2 q＝p p＝tr[p][2] tr[q][k]＝①　　　　　　 tr.append([a[i]，－1，－1]) mt＝[] def midtravel(tr，p)： if tr[p][1]！＝－1： midtravel(tr，tr[p][1]) mt.append(tr[p][0]) if tr[p][2]！＝－1： midtravel(tr，tr[p][2]) ②　　　　　　 print(mt) 则①、②处填入的代码分别为(　D　) A．①len(tr)－1　②midtravel(tr，1) B．①len(tr)　②midtravel(tr，1) C．①len(tr)－1　②midtravel(tr，0) D．①len(tr)　②midtravel(tr，0) 【解析】 for循环构建二叉排序树，a[0]作为根节点建立二叉树，对于数组a 中的其他元素，遵循“比根节点小的数放左边、比根节点大的数放右边”的原则；①处将父节点的指向准备新的节点，由于还未添加新节点，指向len(tr)，排除选项A和选项C；②调用函数进行遍历输出二叉排序树，从根节点开始遍历，选项D正确。 |随|堂|检|测| 1．一棵二叉树的形态如图所示，用数组来表示为(　B　) 0 1 2 3 4 5 6 7 A B C D E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 10 11 12 A B C D E F 【解析】 用数组表示非完全二叉树，需先将它补全为一棵完全二叉树，然后从根节点开始，从上而下、自左往右的顺序进行编号，节点编号与数组的下标一一对应，选项B正确。 2．有如图所示的二叉树，下列关于该二叉树的说法中，正确的是(　A　) A．该二叉树的前序遍历序列为ABDGJCEFHI B．该树中共有3个叶子节点 C．若有前序遍历序列和后序遍历序列可以推导出唯一的二叉树 D．该树的深度是4 【解析】 没有孩子的节点称为叶子节点，故叶子节点为J、E、H、I，共4 个，选项B错误；前序遍历规则为根左右，后序遍历为左右根，故除了可以确定根节点外并不能确定左节点和右节点，选项C错误；该树有5 层，深度为5，选项D错误。 3．如果将数学表达式中的运算数和运算符视同为二叉树的每个节点，那么我们可以构造出各种表达式二叉树，如图所示的是一棵表达式二叉树。如果对该二叉树进行中序遍历，并加上括号后，就可以得到中缀表达式：(9－4/2)*5＋3。如果对该二叉树实行前序遍历，则可以得到的表达式为(　A　) A．＋*－9/4253 B．＋*－/42953 C．942/－*53＋ D．942/－5*3＋ 【解析】 前序遍历是中左右进行遍历，相当于前缀表达式，选项A正确。 4．2023·宁波中学检测某二叉树从根节点开始，按从上到下、自左往右的顺序用A～G 字母表示，若补全为完全二叉树后，用一维数组表示(如下图)。则该二叉树的中序遍历结果为(　A　) A．DBAGECF B．BDAFECG C．ABDCEFG D．DBGEFCA 【解析】 根据题干中数组表示二叉树的结果可得该二叉树如图所示。由此可得该二叉树的中、前、后序遍历结果。非空二叉树中序遍历的规则为先访问左子树，再访问根节点，最后访问右子树，由此得到遍历结果为DBAGECF。 5．2023·温州中学检测数学表达式(7－5)*(1＋2)可用二叉树表示，如图所示。则下列说法不正确的是(　C　) A．该二叉树是满二叉树 B．该二叉树的高度为3 C．通过后序遍历可求出该表达式的逆波兰表达式为7 5 1 2 － ＋ * D．用列表方式存储该二叉树的具体结构为：['*'，['－'，[7，None，None]，[5，None，None]]，['＋'，[1，None，None]，[2，None，None]]] 【解析】 该表达式的逆波兰表达式为75－12＋*，选项C错误。 学科网（北京）股份有限公司 $$