资源简介

(共50张PPT)
课时27 二叉树的基本操作
一、二叉树的数组实现
1. 用　　　　来表示二叉树时，需要将二叉树分为完全二叉树和非完全二叉树两种情况。
数组　
2. 完全二叉树。
（1）从二叉树的　　　　节点开始，按从上而下、自左往右的顺序对 n 个节点逐个进行编号。以图中的二叉树为例，从第一层的根节点开始，根节点 A 的编号为 0；第二层从左至右，节点 B 的编号为 1，节点 C 的编号为 2；第三层从左至右，节点 D 的编号为 3，节点 E 的编号为 4，F 为 5，G 为 6；第四层从左至右，节点 H 的编号为 7，I为 8，J 为 9，K 为 10。
（2）节点编号与数组的　　　　一一对应，将节点数据存储到数组中。
根
下标
3.非完全二叉树。
（1）对于非完全二叉树的数组存储，需要先将它补全为　　　　，补上的节点和边用虚线表示，如图所示。
（2）将一个非完全二叉树补全为完全二叉树之后，根据完全二叉树的方法将各节点进行编号（包括用虚线表示的节点），然后根据编号将节点数据存储到数组对应的位置，如图所示。
（3）采用一维数组表示非完全二叉树时，虽然结构简单，但是容易造成存储空间的浪费。
完全二叉树
1. 用　　　　表示二叉树，用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。
2. 存储二叉树的链表节点至少需要 3 个域：一个　　　　和两个　　　　，指针域分别指向该节点的左孩子和右孩子，分别称其为左指针和右指针，这样得到的链表称为　　　　。
链表
数据域
二、二叉树的链表实现
指针域
二叉链表
1.用列表 list构造二叉树的方法。
（1）空树用　　　　表示。
（2）非空二叉树用包含三个元素的列表　　　　表示，d 表示根节点的元素，l 表示左子树，r 表示右子树。
2.列表构造二叉树实例。
（1）先用列表表示出每个节点。
三、Python 列表表示二叉树
None
[d,l,r]
（2）之后从　　　　节点开始，逐个将节点嵌套到其父节点的列表中，一直到根节点结束。
（3）如图所示是二叉树中左子树的 list 结构示意，从最下层节点开始，将节点逐个嵌套到其 list 结构的父节点中，最终得到左子树的 list 表示为 ['B', ['D', ['G', None,None], None],['E',None,None]]，一样的方法可以得到右子树的 list 表示为['C',['F',['H',None,None],['I',None,None]],None]，再将左右子树的 list 表示嵌套到根节点的 list 表示中，得到的二叉树 list表示是['A',['B',['D',['G',None, None],None], ['E', None, None]], ['C', ['F', ['H', None,None],['I',None, None]],None]]。
叶子
1.前序遍历。
（1）前序遍历的规则是：先访问　　　　，再访问　　　　，最后访问　　　　；若二叉树为空，则空操作返回。
（2）如图所示的二叉树，其前序遍历的顺序即是节点旁边序号的顺序，即该二叉树的前序遍历结果是：ABDEGCFH。
四、二叉树的遍历
根节点
左子树
右子树
2.中序遍历。
（1）中序遍历的规则是：先访问　　　　，再访问　　　　，最后访问　　　　；若二叉树为空，则空操作返回。
（2）如图所示的二叉树，其中序遍历的顺序即是节点旁边序号的顺序，即该二叉树的中序遍历结果是：DBGEACFH。
左子树
根节点
右子树
3.后序遍历。
（1）后序遍历的规则是：先访问　　　　，再访问　　　　，最后访问　　　　；若二叉树为空，则空操作返回。
（2）如图所示的二叉树，其后序遍历的顺序即是节点旁边序号的顺序，即该二叉树的后序遍历结果是：DGEBHFCA。
4.通过遍历序列推导二叉树。
一般来说通过二叉树的前、中、后序遍历中的两种即可得到第三种遍历结果。但是如果只知道　　　　遍历结果和　　　　遍历结果，则无法确定唯一的一棵二叉树。
左子树
右子树
根节点
前序
后序
1. 数据类型是指一组性质相同的值的　　　　及定义在此集合上的一些　　　　的总称。使用计算机程序处理的数据，通常属于不同的类型，如整数型、浮点数型或逻辑型等。每种程序设计语言都提供了一些内置数据类型，并为每个内置类型提供了一批操作。
2.例如，有下列 Python 程序语句：
s1="Hello"
s2="World!"
s=s1+s2
　　在这段语句中，给变量 s1、s2 和 s 均赋予了字符串类型的数据，字符串是 Python 内置的数据类型，而运算符“+”是定义在该内置类型中的一种操作，其作用是将前后字符串进行连接。这样的内置数据类型和操作在 Python 语言中还有很多。
五、数据类型与抽象数据类型
集合
操作
3. 抽象是指抽取出事物具有的　　　　本质，是对具体事物的一个概括。抽象隐藏了繁杂的细节，只保留实现目标所必需的信息。实现　　　　后有利于对事物的抽象，便于实现功能、提高模块独立性。
4.抽象数据类型。
（1）对已有数据类型进行抽象，就有了抽象数据类型（Abstract Data Type，简称 ADT），它是指一个数学模型及定义在该模型上的一组　　　　。
（2）ADT 的基本思想是　　　　，它的定义仅取决于它的一组逻辑特性，把数据结构及其操作作为一个整体来研究，而与其在计算机内部如何表示和实现无关。
（3）程序设计语言的一个内置类型可以看作是一个抽象数据类型，例如，Python 的字符串型（str）就是一个抽象数据类型，在字符串对象的内部提供了一组操作可供编程者使用，每个操作都有明确的抽象意义，编程者不必受制于操作内部的具体实现技术，在程序设计时可以直接使用。
普遍性
抽象化
操作
抽象
（4）抽象数据类型除了已经定义并实现的数据类型，还可以是编程者在程序设计时使用的　　　　或者单独定义的数据类型等。如使用 Python 的内建函数时，使用者只需考虑它的功能是否满足实际需要，再确保调用时是否符合调用规则，而不需要知道功能实现的任何具体细节。
（5）抽象数据类型还包括定义在该模型上的一组操作，即一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。
函数
1.定义一个抽象数据类型，需要表述以下方面。
（1）为该抽象数据类型确定一个　　　　。
（2）各方面的　　　　要求（操作的名字、参数的个数和类型等）。
（3）　　　　要求（希望这个操作完成什么样的计算或产生什么效果等）。
2.描述抽象数据类型的标准格式。
ADT 抽象数据类型名:
Data
数据元素之间逻辑关系的定义
Operation
操作 1
初始条件
操作结果描述
操作 2
……
操作 n
……
endADT
六、抽象数据类型的描述
类型名
形式
功能
1.抽象数据类型的功能。
抽象数据类型主要体现了程序设计中问题　　　　、抽象和信息隐藏的特征。它把实际生活中的问题分解成多个规模较小且容易处理的问题，然后建立一个计算机能处理的数据模型，把每个功能模块作为一个独立单元，　　　　具体的实现过程，通过一次或多
次的模块调用来实现整个问题的解决。
2.抽象数据类型的好处。
（1）使用抽象数据类型编写出来的程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析。
（2）因为其　　　　的特点，在程序设计中容易纠正，具有很好的可维护性。
（3）由于抽象数据类型的表示和实现都可以封装起来，便于移植和　　　　。
（4）因为算法设计与数据结构设计的隔开，降低了算法和程序设计的复杂度，有助于在开发过程中少出差错，保证编写的程序有较高的可靠性。
（5）允许数据结构的自由选择，给了算法的优化空间，提高了程序运行的效率。
七、抽象数据类型的作用
分解
隐藏
模块化
重用
典例 1 将如图所示的二叉树用数组方式存储，表示正确的是 （　　）
A.["A","B","C","D","E","F","G","H"]
B.["A","B","E","C","","F","H","","D","","","G"]
C.["A","B","E","C","F","H","D","","G"]
D.["A","B","E","C","","D","F","G","","H"]
B
√
题型导向一　二叉树的表示
胜券点拨1
明考向 本题主要考查二叉树的数组表示
审关键 非完全二叉树的数组表示
考场思 维快闪 首先要将非完全二叉树补全为如图所示的完全二叉树，然后从左到右，逐层对节点进行编号，有数据内容的节点存放到与编号相应的数组下标的位置，没有数据内容的虚线节点则不在相应位置存放元素，该位置为空
典例 2 将如图所示的二叉树用链表表示，则其中两个指针域都不为空的链表节点数量是 （　　）
A.5
B.4
C.3
D.2
C
√
胜券点拨2
明考向 本题主要考查二叉树的链表表示
审关键 链表指针与二叉树节点的关系
考场思 维快闪 链表表示的二叉树中，存储二叉树的链表节点需要两个指针域，即左指针和右指针，一个指向该节点的左孩子，另一个指向该节点的右孩子。在该二叉树中，两个指针域都不为空的链表节点即二叉树中度为2的节点，即节点A、C、F
典例 3 ［2025 天域协作体］某完全二叉树用数组存储，根节点的编号为 0，若编号为 8 的节点有兄弟节点和两个孩子节点，则它的兄弟节点和右孩子节点的编号分别是 （　　）
A.7 和 17
B.9 和 17
C.7 和 18
D.9 和 18
C
√
胜券点拨3
明考向 本题主要考查完全二叉树的数组表示
审关键 完全二叉树父节点和孩子节点的关系
考场思 维快闪 在完全二叉树中，若根节点的编号为0，则对于任意节点i，其左孩子节点的编号为2×i+1，其右孩子节点的编号为2×i+2。若i为偶数，则其兄弟节点的编号为i-1；若i为奇数，则其兄弟节点的编号为i+1。若编号为8的节点有兄弟节点和两个孩子节点，则它的兄弟节点的编号为8-1=7，右孩子节点的编号为2×8+2=18
典例 4 ［2023.1 浙江选考］下列二叉树中，中序遍历结果为 BAEDFC 的是 （　　）
C
√
题型导向二　二叉树的遍历
胜券点拨4
明考向 本题主要考查二叉树的中序遍历
审关键 中序遍历的过程是先遍历左子树，再遍历根节点，最后遍历右子树
考场思维快闪 A 首先遍历左子树（节点EDFB）；接着遍历根节点A，最后遍历右子树（节点C），得到中序遍历结果为EDFBAC
B 首先遍历左子树（节点BEDF）；接着遍历根节点A；最后遍历右子树（节点C），得到中序遍历结果为BEDFAC
C 首先遍历左子树（节点B）；接着遍历根节点A；然后遍历右子树（节点EDFC），得到中序遍历结果是BAEDFC
D 首先遍历左子树（节点B），然后遍历根节点A，最后遍历右子树（节点CEDF），得到中序遍历结果为BACEDF
典例 5 ［2023.6浙江选考］某二叉树的树形结构如图所示，其前序遍历结果为 BDEFCA，则中序遍历结果为 （　　）
A.EDCFBA
B.ECFDAB
C.BFDEAC
D.EDFCBA
A
√
胜券点拨5
明考向 本题主要考查二叉树的遍历
审关键 前序遍历、中序遍历
考场思 维快闪 根据前序遍历“根-左-右”的特点，可画出二叉树如图所示，再根据中序遍历“左-根-右”的特点，可得知二叉树中序遍历结果为EDCFBA
典例 6 ［2024.6 浙江选考］某完全二叉树包含 5 个节点，其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为 x、y，则 x-y 的值为 （　　）
A.0
B.1
C.2
D.3
B
√
胜券点拨6
明考向 本题主要考查二叉树的遍历
审关键 二叉树的遍历推理
考场思 维快闪 含5个节点的完全二叉树如图所示。该二叉树的后序遍历序列为3-4-1-2-0，其中根节点排在最后一位。该二叉树的中序遍历序列为3-1-4-0-2，其中根节点排在倒数第二位，故x-y的值为1
典例 7 ［2025.1 浙江选考］某二叉树如图所示，若其中的一个叶子节点增加右子树（仅包含节点 N），则新二叉树的中序遍历结果不可能是 （　　）
A.CNBDAE
B.CBDNAE
C.CBDAEN
D.NCBDAE
D
√
胜券点拨7
明考向 本题主要考查二叉树的遍历
审关键 二叉树的中序遍历
考场思 维快闪 在该二叉树的叶子节点增加右子树N，可能的二叉树如图所示，对应的中序遍历结果是CNBDAE、CBDNAE、CBDAEN
典例8　［2025.6浙江选考］某二叉树如图所示，E节点在前序遍历序列中的位置记号为x。下列二叉树中，E节点在中序遍历序列中的位置序号也为x的是 （　　）
A
√
胜券点拨8
明考向 本题主要考查二叉树的遍历
审关键 前序遍历、中序遍历
考场思维快闪 前序遍历的访问顺序是“根→左→右”。图示的E节点在前序遍历序列中的位置序号为4。中序遍历的访问顺序是“左→根→右”。选项A、B、C、D的E节点在中序遍历序列中的位置序号分别为4、3、5、3
典例 9 描述一个抽象数据类型的语句如下：
ADT Queue: #创建队列抽象数据类型
Queue(self) #创建空队列对象
#判断队列是否为空，空返回 True，非空返回False
is_empty(self)
enqueue(self,elem) #将元素 elem 入队
dequeue(self) #将队首元素出队
peek(self) #返回队首元素的值，不出队
（1）设队列对象为 q，若要判断该队列对象是否为空，则调用相关方法的语句是　　　　　　。
（2）设队列对象 q 中的元素从队首开始依次是 3，7，9，6，2，执行语句 q.peek()，则返回的内容是　　　　　　　，此时队列中元素的个数是　　　　　　　。
（3）设队列对象 q 中原有元素从队首开始依次为 7，9，2，3，4，5，若干次操作之后，队列对象 q 中的元素变为 4，5，7，9，则 q.dequeue()执行的次数最少是　　　　　　　。
q.is_empty()
3
5
4
题型导向三　抽象数据类型的描述
胜券点拨9
明考向 本题主要考查抽象数据类型的描述和应用
审关键 不同抽象数据类型的作用和运用
考场思维快闪 （1） 该抽象数据类型中，判断队列是否为空的方法是is_empty(self)，对象为q，语句为q.is_empty()
（2） peek()方法返回队首元素的值但不对队列进行操作，此时队首元素是3，返回值为3，队列中元素的个数依然是5
（3） 新队列中元素4，5的排列不变，所以至少将元素7，9，2，3进行了出队操作，q.dequeue()的执行次数为4
1.完全二叉树的两个特点。
（1）最多只有最下面两层的节点度数小于 2。这表示完全二叉树的叶子节点只在最后两层有。
（2）最下面一层的叶子节点都依次排列在该层的最左边位置（倒数第二层中最多只能有一个节点的度为 1，节点的度数从左到右不变或递减）。
2.将非完全二叉树补全为完全二叉树的过程。
（1）将除了最后一层以外的节点的度数都补全为 2，补充的节点用虚线表示。
（2）若倒数第二层最右边的节点度数为 0，则不用补充。
通法一　非完全二叉树补全为完全二叉树
1.通过前（后）序遍历结果和中序遍历结果得到后（前）序遍历结果。
（1）在前（后）序遍历结果中得到根节点。
（2）在中序遍历结果中通过根节点区分哪些节点属于左子树，哪些节点属于右子树。
（3）分别得到左、右子树的前（后）序遍历结果和中序遍历结果。
（4）将左、右子树作为单独的二叉树重复以上步骤。
2.不能通过前序遍历结果和后序遍历结果得到唯一的中序遍历结果。
通法二　二叉树的遍历
1. 如果将数学表达式中的运算数和运算符视为二叉树的每个节点，那么
可以构造出各种表达式树。如图所示是一棵表达式树。
2. 如果对如图所示的表达式树进行中序遍历，将得到遍历序列：8-(3+
2*6)/5+4，即人们平时习惯书写的数学表达式，也称为中缀表达式。由
于中缀表达式要将运算符放在两个操作数中间，并且在许多情况下为了
确定运算顺序，括号是必不可少的。
3. 如果对如图所示的表达式树进行后序遍历，将得到遍历序列：8 3 2
6 * + 5 / - 4 +，称为后缀表达式（也称逆波兰表达式）。因为后缀
表达式采用了运算符紧跟在两个操作数之后的方法，从而实现了无括号
处理和优先级处理，使计算机的处理规则简化为：从左到右依序完成计
算，并方便求得结果。
通法三　表达式树
ADT List:
List(self) #创建一个新表
is_empty(self) #判断 self是否为一个空表
len(self) #返回表的长度
prepend(self,elem) #在表头插入元素 elem
append(self,elem) #在表尾插入元素 elem
insert(self,elem,i) #在表的第 i个位置插入元素 elem
del_first(self) #删除第一个元素
del_last(self) #删除最后一个元素
del(self,i) #删除第 i个元素
search(self,elem) #查找元素 elem 在表中第一次出现的位置
forall(self,op) #对表中的每个元素执行 op 操作
通法四　线性表抽象数据类型
1.下列二叉树中，用数组表示为["F","K","L","N",None,"C","A",None,"G",None,None,None,"E"]的是 （　　）
根据数组的下标，在一个完全二叉树中对应的位置填入数组元素的值，就能得到相应的二叉树。如图所示的完全二叉树中，节点中的数字表示对应数组的下标，将对应下标的数组元素的值填入节点，之后擦除值为None的节点即可得到相应的二叉树。
一、二叉树的表示
B
√
2.将如图所示的二叉树用列表list方式存储，下列表示正确的是 （　　）
A.["A",["B",["D","E"]],["C","F","G"]]
B.["A",["B",None,["D",None,"E"]],["C","F","G"]]
C.["A",["B",None,["D",None,["E",None,None]]],
["C",["F",None,None],["G",None,None]]]
D.["A",["B",[None,None,None],["D",None,["E",None,None]]],["C",["F",None,None],["G",None,None]]]
用列表list表示的树中，每个节点都用一个单独的列表[d,l,r]表示，空节点用None表示。其中叶子节点表示为[d,None,None]，注意节点之间的嵌套关系。
C
√
3.有如图所示的二叉树，该二叉树的一种遍历结果是13、15、17、20、22、23、24、33、45、48、50，则该结果是该二叉树的（　　）
A.前序遍历结果
B.后序遍历结果
C.中序遍历结果
D.层序遍历结果
C
√
第一个遍历的节点不是根节点，故不是前序遍历和层序遍历，再根据中序遍历“左-根-右”和后序遍历“左-右-根”的特点可知，是中序遍历结果。
二、二叉树的遍历
4.若某二叉树的中序遍历结果是BDAFEGC，前序遍历结果是ABDCEFG，则该二叉树的后序遍历结果是 （　　）
A.DBFGECA
B.BDGFECA
C.GFECDBA
D.DBAFGEC
A
√
根据二叉树的前序和中序遍历结果可确定该二叉树结构如图所示，故该二叉树的后序遍历结果是DBFGECA。
5.［2025县域联盟］某二叉树中有4个节点，其前序遍历结果与后序遍历结果互逆，如abcd与dcba，则该二叉树的中序遍历结果有 （　　）
A.2种
B.4种
C.8种
D.16种
已知前序遍历结果与后序遍历结果互逆，则说明二叉树中所有节点的度均为1，可能的结果如图所示，该二叉树的中序遍历结果有8种。
C
√
6.定义一个简单的ADT，具体描述如下：
ADT Bag:　#创建一个背包类
Bag(self)　#创建空背包
is_empty(self)　#判断背包是否为空
add_weight(self,wei)　#加入重量wei
take_weight(self,wei)　#取走重量wei
all_weight(self)　#输出背包的总重量
为该抽象数据类型创建一个背包实例bag1并执行如下语句：
bag1.add_weight(8)
bag1.add_weight(2)
bag1.all_weight()
执行该程序段后，输出的结果是 （　　）
根据代码可知，只有语句bag1.all_weight()有输出功能，输出的内容为背包bag1的总重量，在输出之前已向背包bag1中添加了重量8和2，故输出的总重量为10。
C
三、抽象数据类型的描述
A.8 2 10 B.0
C.10 D.6
√
7.［2025浙南名校联盟］某二叉树有6个节点，其部分结构如图所示，若该二叉树有2个度为2的节点，中序遍历结果为cbaedf，则该二叉树的前序遍历结果是(　　)
A.abcdef
B.abcedf
C.acbdef
D.bcefda
A
度为2的节点有2个，已知a的度为2，说明右子树中也有1个度为2的节点，右子树的中序遍历结果为edf，故右子树的根是d，d的左子树是e，d的右子树是f。则该二叉树的完整结构如图所示，其前序遍历结果是abcdef。
√
8.下列二叉树中，中序遍历结果为BFDACE的是 （　　）
B
根据中序遍历“左-根-右”的特点，选项A中序遍历结果为FDBAEC。选项C中序遍历结果为BDAFCE。选项D中序遍历结果为DBFAEC。
√
9.［2026七彩阳光联盟］某二叉树的前序遍历结果为ABCDEF，其中A是C的父节点，E和F是兄弟节点。该二叉树的后序遍历结果是 (　　)
A.BACEDF
B.BEFDCA
C.BCDEFA
D.BCEFDA
B
√
前序遍历的规则是“根-左-右”，故A是根节点。A是C的父节点，故B是A的左子树，CDEF是A的右子树，右子树的根节点是C。E和F是兄弟节点，故E是D的左孩子，F是D的右孩子。该二叉树的可能形态如图所示，它们的后序遍历结果都是BEFDCA。
10.［2026.1浙江选考］某二叉树有a、b、c、d四个节点，若中序遍历序列为abcd，后序遍历序列为dcba，则该二叉树的树形结构为 （　　）
C
根据中序遍历“左-根-右”和后序遍历“左-右-根”的特点，可知当中序遍历序列与后序遍历序列逆序时，该二叉树的所有节点均无左子树。
√
11.［2025杭州模拟］某二叉树共有5个节点，其中有3个叶子节点。若中序遍历结果为“仁义礼智信”，则下列说法正确的是 （　　）
A.“仁”的父节点一定是“信”
B.根节点一定是“智”
C.叶子节点一定是“仁”“礼”“信”
D.“义”的孩子节点一定是“礼”
C
√
根据中序遍历结果，可画出该二叉树的2种可能形态，如图所示。“仁”的父节点一定是“义”。根节点可能是“智”或“义”。“义”的孩子节点是“仁”“礼”或“仁”“智”。
12.某二叉树的中序遍历结果是DGBAECF，后序遍历结果是GDBEFCA，下列关于该二叉树的说法，不正确的是 （　　）
A.该二叉树的前序遍历结果是ABDGCEF
B.该二叉树是满二叉树
C.该二叉树有3个叶子节点
D.节点D是节点G的父节点
B
√
根据该二叉树的中序遍历结果和后序遍历结果，可画出如图所示的二叉树，故该二叉树不是满二叉树。
13.已知某二叉树的前序遍历结果为ABCD，下列说法正确的是 （　　）
A.该二叉树的中序遍历结果可能是BDCA
B.度为2的节点数可能与叶子节点数相同
C.若该树的深度为4，则形态只有3种
D.若该树为完全二叉树，则D是分支节点
A
√
在任意一棵二叉树中，若度为2的节点数量为n2，叶子节点数为n0，则有n0=n2+1。若该树的深度为4，则每一层只有1个节点，可以是其父节点的左孩子或右孩子，故形态共有2×2×2=8种。若该树为完全二叉树，则D是叶子节点。
14.某二叉树的中序遍历结果为ABCDE，其任意非叶子节点的度为2，则下列关于该二叉树的说法，正确的是 （　　）
A.该二叉树有4层
B.该二叉树可能有3种形态
C.节点A不可能是叶子节点
D.该二叉树有3个叶子节点
D
√
该二叉树共有5个节点，其任意非叶子节点的度为2，则该二叉树的结构是：第1层有1个节点；第2层有2个节点，其中1个节点有2个孩子节点，故该二叉树有3层。该二叉树可能有2种形态。节点A可能是叶子节点。
15.某完全二叉树总节点数为10，用数字1~10逐层依次标记各个节点。下列关于该树的说法，不正确的是 （　　）
A.叶子节点数比度为2的节点数多1个
B.中序遍历的顺序为8-9-4-10-5-2-1-6-3-7
C.若某节点无左孩子节点，则此节点也无右孩子节点
D.用一维数组存储该树时，所有节点对应的数组元素一定是连续的
B
√
该完全二叉树如图所示，其中序遍历的顺序为8-4-9-2-10-5-1-6-3-7。
16.某二叉树用一维数组存储，结构如图所示。
下列关于该二叉树的说法，正确的是 （　　）
A.该二叉树是完全二叉树
B.该二叉树中度为2的节点有3个
C.该二叉树的前序遍历结果是ABDFGCHE
D.节点C是节点E的父节点
D
√
根据一维数组画出如图所示的二叉树。该二叉树不是完全二叉树。该二叉树中度为2的节点有2个。该二叉树的前序遍历结果为ABDFGCEH。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H
17.用如图所示的数组表示一棵二叉树。
下列说法正确的是 （　　）
A.这是一棵完全二叉树
B.这棵树的叶子节点比度为1的节点多1个
C.节点g和h是兄弟节点
D.使用前序遍历和中序遍历方式查找节点e，访问节点个数相同
D
√
根据数组表示的二叉树，可画出二叉树的结构如图所示。该二叉树不是完全二叉树。该树的叶子节点个数为3，度为1的节点个数为4。节点g和h不是兄弟节点。使用前序遍历和中序遍历方式查找节点e，访问节点个数都为5。
0 1 2 3 4 5 6 7 8 9 10 11
a b c d e f g h i
18.有如下Python程序段：
from random import randint
n=12;a=[""]*n
for i in range(n//2):
x=chr(65+randint(0,i))
while x in a:
x=chr(65+randint(0,i))
a[randint(0,i)*2]=x
使用得到的数组a，构建的二叉树可能是 （　　）
D
x为随机生成的字母"A"~"F"（选项C不可能），while循环保证生成x的值不重复（选项A不可能），然后将x赋值给a的偶数索引位置。因此数组a对应的二叉树中没有左子树（选项B不可能）。
√
19.某二叉树采用链表存储：链表节点由三部分构成，分别是左子树指针、数据区域和右子树指针，-1表示空指针。其处理程序如下：
def traversal(h,t):
if h==-1:
return
else:
traversal(t[h][0],t)
print(t[h][1],end=" ")
traversal(t[h][2],t)
#主程序
a=[[6,26,1],[2,35,4],[-1,29,-1],[-1,25,-1],[-1,40,-1],[-1,15,0],[-1,20,3]]
root=5
traversal(root,a)
若根节点是[-1,15,0]，则下列关于该二叉树和程序的说法，不正确的是 （　　）
A.该二叉树中度为1的节点有2个
B.该二叉树的叶子节点数比度为2的节点数多1个
C.该程序输出的结果是15 20 25 26 29 35 40
D.该二叉树的前序遍历结果是15 25 20 26 35 29 40
D
√
由根节点和各节点的左、右子树指针可画出如图所示的二叉树。其中度为1的节点有2个。叶子节点数是3个，度为2的节点数是2个。主程序从根节点开始调用traversal函数，递归函数traversal(h,t)当h值是-1时结束递归，否则递归调用t[h][0]，即t节点的左子树指针，然后输出t[h][1]，即t节点的数据区域，最后又递归调用t[h][2]，即t节点的右子树指针。因此traversal函数是二叉树的中序
20.有二叉树如图所示。
（1）请写出该二叉树的数组表示。
（2）请写出该二叉树的链表表示。
下标 0 1 2 3 4 5 6 7 8 9 10 11 12
数据
下标 0 1 2 3 4 5 6 7 8 9 10 11 12
数据 C B A D E G F N
（1）将二叉树补全为如图所示的完全二叉树，从第一层根节点开始编号为0，第二层从左往右依次为1、2，逐层编号之后根据编号将数据元素存储到数组对应的下标位置，若节点为空则数组该位置元素值为空。　（2）根据二叉树形态，为节点设定两个指针域，左指针指向左孩子，右指针指向右孩子，若无左孩子或无右孩子则相应的指针域为空。

展开更多......

收起↑