资源简介

(共50张PPT)
课时2　二叉树的基本操作
第四章　树
1.掌握使用数组和链表等数据结构建立二叉树的方法。2.掌握二叉树遍历的基本操作方法。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.建立二叉树的方法
建立二叉树的操作方法为：按照二叉树层的顺序进行，先由第___层开始，依次到下一层，在每一层中按照从_________的顺序创建节点。
1
左到右
2.用数组实现二叉树的创建
(1)完全二叉树
①从二叉树的_________开始，按____________、自左向右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为_________。
②然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与_______________一一对应。
(2)非完全二叉树
①对于非完全二叉树，先将它补全为一棵______二叉树，补上的节点及分支用虚线表示。
②然后按照完全二叉树的方法，将节点存储在数组中。
根节点
从上到下
n－1　
数组的下标
完全
(3)使用数组(列表)建立二叉树
空树用None表示，非空二叉树用包含三个元素的列表[d，l，r]表示，分别存储着根节点的元素和左右子树，因此二叉树的list实现采用嵌套括号([])的形式。
用数组(列表)构建二叉树的代码如下：
def create_tree(tree，data)：
for i in range(len(data))：
depth＝0 #程序的第0层相当于树的第1层
if i＝＝0: #根节点
　　　　 tree[depth]＝data[i]
else：
　　　　 #while循环结束表示找到存放数据的节点(索引)位置
　　　while tree[depth] ！＝0：
　　　 　　　if data[i]>tree[depth]：　#往右寻找
　　　　　　　　depth＝depth*2＋2　#父节点的右孩子位置
　　　　　　else：　　　　#往左寻找
　　　　　　　　depth＝depth*2＋1　#父节点的左孩子位置
tree[depth]＝data[i]　#找到数据应存放的节点位置，并存储该节点
3.用链表实现二叉树的创建
二叉树用链表实现时，二叉树的节点至少需要三个域：一个_________和两个_________。如下图所示：
lchild data rchild
其中lchild和rchild是指针域，存放指向节点的左孩子节点和右孩子节点的指针，data是数据域。
使用链表建立搜索二叉树如下：
def insert(self，data)：
if self.data：　　　#如果根节点不存在
if data数据域
指针域
　　　if self.left：
　　　 　　　self.left.insert(data) #递归调用往下一层
　　　　else：
　　　　　 self.left＝Node(data) #建立新节点存放数据
else: #插入值大于当前节点值
　　if self.right：
　　　self.right.insert(data)
　　　else：
　　　　　self.right＝Node(data)
else: #如果根节点不存在
self.data＝data #建立根节点
4.二叉树的遍历
(1)二叉树的遍历是指按照一定的_______________访问二叉树中的所有节点，使得每个节点都被访问一次且__________________。
(2)根据访问根节点的先后顺序可以分为：前序遍历、____________和____________。
①前序遍历
前序遍历，也称为先序遍历，前序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问_________，再访问_________，最后访问_________。
规则和次序
仅被访问一次　
中序遍历
后序遍历
根节点
左子树
右子树
②中序遍历
中序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问_________，再访问根节点，最后访问_________。
③后序遍历
后序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问_________。
左子树
右子树
根节点
二叉树的三种遍历是根据访问根节点的先后次序来命名的，前序遍历的访问顺序为根左右(BLR)，中序遍历的访问顺序为左根右(LBR)，后序遍历的访问顺序为左右根(LRB)。
例题精析
2
例1 下列二叉树中，中序遍历结果为 BAEDFC的是(　　)
C
解析　本题考查二叉树遍历。中序遍历的方法：左子树－根－右子树，每棵子树，都遵循以上规定。A选项中序遍历为EDFBAC。B选项中序遍历为BEDFAC。D选项中序遍历为BACEDF。
解析　B选项的后序遍历为GFDBEHCA。
B
例2 某二叉树的树形结构如图所示，其前序遍历结果为BDEFCA，则中序遍历结果为(　　)
解析　本题考查二叉树的遍历。 前序遍历可知B为二叉树根节点，D和左子树根节点，E和F为左子树的左右孩子。C为F的左孩子，A为树的右子树。该树结构如图所示。因此中序遍历为EDCFBA。
A
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
变式训练　有一棵完全二叉树，已知其中序遍历结果是CADGBEIHJ，则其前序遍历结果应该为(　　)
解析　该完全二叉树有9个节点，因此共有4层，其中前3层是满二叉树(7个节点)，第4层有2个节点，画出二叉树的形态和中序遍历路径，可得前序遍历序列。
B
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
例3 某二叉树对应的一维数组表示如图所示：
解析　根据存储情况画出树如图所示。
D
下列关于该二叉树的说法正确的是(　　)
A.这是一棵完全二叉树
B.节点F是节点D的孩子节点
C.该二叉树有1个叶子结点
D.该二叉树中序遍历的结果是DBEACF
A选项最后一层节点没有从左向右依次排列。B选项节点F是节点C的孩子节点。C选项该二叉树有3个叶子结点。
变式训练　某二叉树用一维数组存储结构如下表所示：
解析　本题考查二叉树的相关知识。根据数组画出树如图所示，可以得到正确的前序遍历序列。
B
下列有关该二叉树的说法正确的是(　　)
A.该树度为 2 的节点有 4 个
B.该树的前序遍历为 A－B－D－E－G－H－C－F－I
C.该树是完全二叉树，其深度为 4
D.该树中共有 3 个叶子节点，分别是 G、H、I
例4 某二叉树的前序遍历结果为ABCDEF，后序遍历结果为CDBFEA，下列关于该二叉树的说法，正确的是(　　)
解析　A为树的根节点，在后序遍历中，B没有紧跟在A的前面，因此B是A的左孩子，CD是B的子树，FE是A的右子树。因此树的形态可能有如图所示的两种情况。
B
A.该二叉树的深度可能为4
B.该二叉树的中序遍历结果可能为CBDAEF
C.该二叉树可能的形态有3种
D.该二叉树度为2的节点可能有3个
A.该二叉树不是完全二叉树
B.该二叉树的深度为4
C.该二叉树的前序遍历结果为ACBDEGF
D.该二叉树所对应的一维数组表示为：
D
0 1 2 3 4 5 6 7 8 9 10 11
A C D B E F G
解析　本题考查二叉树的性质和遍历。后序遍历确定根节点，中序遍历由根节点位置划分左右子树。根节点A的左右子树分别为CB和EGDF，C为子树根，B为右节点。同理可以得到整棵树的结构 。该树深度为4但不是完
全二叉树，前序遍历结果为ACBDEGF，对应的一维数组为
0 1 2 3 4 5 6 7 8 9 10 11 12
A C D B E F G
随堂检测
3
C
解析　C选项中序遍历为ACBDEF。
2.有一棵二叉树如图所示，下列说法正确的是(　　)
B
解析　本题考查树的性质。A选项完全二叉树第n－1层为满二叉树，不符合。C选项叶子节点有2个。D选项可以用数组或链表实现。
A.该二叉树是一棵完全二叉树，树的高度为 3
B.该二叉树的前序遍历为 A，B，D，C，E
C.该二叉树的叶子节点有4个
D.该二叉树的建立只能使用数组来实现
3.下列二叉树中，前序和中序遍历结果一样的选项是(　　)
D
解析　前序遍历是根左右，中序遍历是左根右，当左子树不存在时，两者相同。
4.有二叉树形态如图所示，后序遍历结果为abcdefg，则树中与c同层的节点是(　　)
A
解析　本题考查树的遍历和性质。从后序遍历来看，g是根节点，左右子树分别有3个，左子树先于右子树，因此abc是左子树，def是右子树，c是g的左孩子，f是g的右孩子。
A.f B.e
C.d D.b
5.某二叉树从根节点开始，按从上到下、自左往右的顺序用 A－G 字母表示，若补全为完全二叉树后，用一维数组表示如图所示。
C
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G
下列关于该二叉树的说法，正确的是(　　)
A.该二叉树的深度为 3
B.节点 E 的父节点是 B
C.该二叉树的中序遍历结果为 BFDGACE
D.该二叉树的叶子节点为 D、E、F、G
解析　本题考查二叉树性质和遍历。根据题意画出二叉树如图所示：
该二叉树的深度为 4，E 的父节点是 C，中序遍历是 B－F－D－G－A－C－E，该二叉树的叶子节点是F，G，E。
6.用一维数组表示二叉树，如下表所示：
C
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是(　　)
A.该树中共有 4 个叶子节点
B.该树是完全二叉树，其深度为 4
C.该树的中序遍历为 B－F－D－G－A－C－E
D.该二叉树的结构图为(如图所示)
解析　本题考查二叉树的基本知识。第3层节点的索引号为3，4，5，可见B没有左子树，但有右子树，因此不可能是满二叉树，B也不是叶子节点。二叉树形态如图所示：
7.某二叉树的前序遍历结果为 GFDECAB，中序遍历结果为 DFGCAEB。关于该二叉树，以下说法，正确的是(　　)
B
解析　本题考查二叉树的性质和遍历。
根据前序遍历和中序遍历可画出二叉树。
A.该二叉树的后序遍历为 ADFCBEG
B.该二叉树的深度为 4，节点 C 在第 3 层
C.该二叉树的叶子节点数比非叶子节点数多一个
D.该二叉树可以通过添加 3 个节点后变为完全二叉树
8.某二叉树的中序遍历顺序为DHBEAFCG，后序遍历为HDEBFGCA，则节点E是(　　)
A.A节点的孩子节点 B.叶子节点
C.H节点的父亲节点 D.F节点的兄弟节点
B
解析　本题考查树的操作。由题意可知A为根节点，左子树的中序遍历为DHBE，观察其后序遍历，B为左子树的根节点，E为左子树的右子树，因此节点 E是叶子节点。
4
巩固与提升
基础巩固
能力提升
1.如图所示的二叉树，若要得到一个递增序列，可以采用的遍历方式是(　　)
B
解析　中序遍历的结果为3，5，7，8，10，12，17。
A.前序遍历 B.中序遍历
C.后序遍历 D.逐层遍历
2.某二叉树如图所示，下列说法正确的是(　　)
D
解析　A选项共有6个叶子节点。B选项该树倒数第2层不是满二叉树，因此不是完全二叉树。C选项中序遍历的结果为7*3＋1－4/2＋6，计算结果为26。
A.该二叉树共有5个叶子节点
B.该二叉树是一棵完全二叉树
C.对该二叉树进行中序遍历后的计算结果是32
D.该二叉树的后序遍历序列为731＋*426＋/－
A.该二叉树是一棵完全二叉树
B.该二叉树的叶子节点数是3个
C.该二叉树的中序遍历结果是DCBEAF
D.该二叉树的度为2
A
解析　本题考查二叉树的性质。该树不是完全二叉树。叶子节点有DEF，节点中最大的度为2。
4.数学表达式3/(5*2)可用二叉树表示，如图所示。
D
解析　本题考查二叉树的遍历。A选项完全二叉树是指一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同。3所在节点缺少叶子节点，故该二叉树不是完全二叉树。B选项3、5、2所在节点为叶子节点，数量为3。C选项前序遍历结果为/3*52。
下列关于该二叉树的说法，正确的是(　　)
A.是完全二叉树
B.叶子节点数为2
C.前序遍历结果为352*/
5.某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为(　　)
C
解析　根据树的形态，画出后序遍历的路径 ，
从而确定每个节点的值。
A.ABCDEF B.FEDCBA
C.DFACBE D.FDBCAE
6.已知某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，则下列说法正确的是 (　　)
A.其后序遍历结果为DCBFEA
B.该二叉树为完全二叉树
C.该二叉树深度为3，叶子节点数为3
D.该二叉树用一维数组实现需要6个节点的存储空间才能表示
C
解析　本题考查树的性质和遍历。根据前序遍历确定根节点，中序遍历区分左右子树，画出二叉树。其后序遍历结果为CDBFEA，该二叉树最后一层叶子节点不是从左向右分布。该二叉树深度为 3，叶子节点数为 3，该二叉树补全为完全二叉树，用一维数组实现需要 7 个节点的存储空间才能表示。
7.有一棵二叉树，如图所示，下列说法正确的是(　　)
C
解析　本题考查二叉树的相关知识。A选项节点 C 缺少左子树，不是完全二叉树。B选项该二叉树的深度是 4。D选项节点C前没有空节点。
A.此二叉树是完全二叉树
B.此二叉树的深度是 3
C.此二叉树的中序遍历为 H－D－B－E－A－C－F
D.此二叉树用一维数组表示为['A'，'B'，″，'C'，'D'，'E'，″，'F'，″，'H']
8.对于右图所示的二叉树，下列说法正确的是(　　)
D
解析　本题考查树与二叉树相关知识。A 选项树的高度是4，但不是完全二叉树。完全二叉树是除最后一层外节点都满节点，且最后一层节点都集中左边位置上，而该二叉树倒数第二层也没有满节点(c 没有子节点)。B选项度为2的节点有2个，而叶子节点有3个。实际上，任意二叉树的都满足叶子节点数比度为2的节点数多一个。C选项若有数组存储二叉树时，c节点虽然没有子节点，但是也要在数组中占据额外的两个空元素位置，因此总容量应该是8个存储空间。D选项后序遍历为fdebca。
A.树的高度是4，是一棵完全二叉树
B.度为2的节点数比叶子节点数多1
C.若采用数组存储法，需要6个存储空间
D.该二叉树的后序遍历序列是fdebca
9.用一维数组表示二叉树，如下表所示：
B
解析　本题考查树的性质。根据存储结构画出的二叉树如图所示 。A选项3个叶子节点。
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是(　　)
A.该树中共有4个叶子节点，度为2的节点有2个
B.该树的中序遍历为B－F－D－G－A－C－E
C.该树是完全二叉树，其深度为 4
D.该树有7条边
10.某二叉树用一维数组实现的示意图如下所示。
C
解析　本题考查二叉树的知识。根据题意画出二叉树如图所示：
0 1 2 3 4 5 6 7 8
A B C D E F
下列关于该二叉树的说法，正确的是(　　)
A.是完全二叉树 B.叶子节点数为3
C.前序遍历结果为ABDFCE D.深度为3
该树不是一颗完全二叉树，叶子节点个数2，深度为4。前序遍历时A－B－D－F－C－E。
11.二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为(　　)
A.abcde B.abdec C.debac D.adbce
A
解析　本题考查树的性质。从后序遍历来看，a是根节点，b是左子树，dce是右子树；c是右子树的根节点，d和e分别是左右子树。因此前序遍历为abcde。
12.有二叉树的前序遍历序列为A－B－C－E－F－G－D，中序遍历序列为A－E－C－F－G－B－D，则关于该二叉树的说法正确的是(　　)
A
解析　本题考查二叉树的性质和遍历。根据二叉树的前序遍历和中序遍历画出二叉树。该二叉树的根节点A的度为1，高度为5，节点G是节点F的右孩子。该二叉树的叶子节点是E、G、D。
A.该二叉树根节点的度为1 B.该二叉树的高度为4
C.该二叉树中节点G是节点C的左孩子 D.该二叉树中叶子节点的个数为4
C
13.某二叉树前序遍历为ABDCE，后序遍历为DBECA，则该二叉树可能情况数量是(　　)
A.1 B.2 C.4 D.6
解析　本题考查二叉树遍历的相关知识。左右子树的根节点都只有一个子节点，以下四种情况的前序和后序遍历都符合题目要求：
14.如图所示的二叉树，根节点为0，每个节点的左子节点为0，右子节点为1，每一条从根到叶子的路径都组成一个二进制数。例如：从根到叶子 a 的路径组成二进制数 011，转换为十进制数是 3。若某完全二叉树共有 13 个节点，则它能表示的最大十进制数是(　　)
C
A.3 B.4 C.5 D.6
解析　本题考查二叉树的性质。根据完全二叉树的性质可知，该二叉树共计13个节点。那么深度为4，前3层有7个节点，第4层有6个叶子节点，最大十进制数是0101B。
A.大好河山 B.河好山大 C.好山大河 D.山河好大
C
解析　本题考查树的遍历。前序遍历为根左右，A选项任一节点没有左节点，则前中序均为根右。B选项好是第1个左节点，则好是大的左节点，是河的根，山为河的兄弟。D选项任一节点没有右节点。C选项好是大的左节点，山是右节点，或山是大的左节点，是好的父节点，则前序遍历不对了。课时2　二叉树的基本操作
课时目标
1.掌握使用数组和链表等数据结构建立二叉树的方法。2.掌握二叉树遍历的基本操作方法。
1.建立二叉树的方法
建立二叉树的操作方法为：按照二叉树层的顺序进行，先由第________层开始，依次到下一层，在每一层中按照从__________的顺序创建节点。
2.用数组实现二叉树的创建
(1)完全二叉树
①从二叉树的__________开始，按__________、自左向右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为________。
②然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与__________一一对应。
(2)非完全二叉树
①对于非完全二叉树，先将它补全为一棵________二叉树，补上的节点及分支用虚线表示。
②然后按照完全二叉树的方法，将节点存储在数组中。
(3)使用数组(列表)建立二叉树
空树用None表示，非空二叉树用包含三个元素的列表[d，l，r]表示，分别存储着根节点的元素和左右子树，因此二叉树的list实现采用嵌套括号([])的形式。
用数组(列表)构建二叉树的代码如下：
def create_tree(tree，data)：
for i in range(len(data))：
depth＝0 #程序的第0层相当于树的第1层
if i＝＝0: #根节点
　　　　 tree[depth]＝data[i]
else：
　　　　 #while循环结束表示找到存放数据的节点(索引)位置
　　　while tree[depth] ！＝0：
　　　 　　　if data[i]>tree[depth]：　#往右寻找
　　　　　　　　depth＝depth*2＋2　#父节点的右孩子位置
　　　　　　else：　　　　#往左寻找
　　　　　　　　depth＝depth*2＋1　#父节点的左孩子位置
tree[depth]＝data[i]　#找到数据应存放的节点位置，并存储该节点
3.用链表实现二叉树的创建
二叉树用链表实现时，二叉树的节点至少需要三个域：一个__________和两个__________。如下图所示：
Lchild data rchild
其中lchild和rchild是指针域，存放指向节点的左孩子节点和右孩子节点的指针，data是数据域。
使用链表建立搜索二叉树如下：
def insert(self，data)：
if self.data：　　　#如果根节点不存在
if data　　　if self.left：
　　　 　　　self.left.insert(data) #递归调用往下一层
　　　　else：
　　　　　 self.left＝Node(data) #建立新节点存放数据
else: #插入值大于当前节点值
　　if self.right：
　　　self.right.insert(data)
　　　else：
　　　　　self.right＝Node(data)
else: #如果根节点不存在
self.data＝data #建立根节点
4.二叉树的遍历
(1)二叉树的遍历是指按照一定的____________访问二叉树中的所有节点，使得每个节点都被访问一次且________________。
(2)根据访问根节点的先后顺序可以分为：前序遍历、____________和____________。
①前序遍历
前序遍历，也称为先序遍历，前序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问________，再访问________，最后访问________。
②中序遍历
中序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问________，再访问根节点，最后访问________。
③后序遍历
后序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问________。
二叉树的三种遍历是根据访问根节点的先后次序来命名的，前序遍历的访问顺序为根左右(BLR)，中序遍历的访问顺序为左根右(LBR)，后序遍历的访问顺序为左右根(LRB)。
例1 下列二叉树中，中序遍历结果为 BAEDFC的是(　　)
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　某二叉树前序遍历为ABDFGCEH，后序遍历为FGDBHECA，则下列选项不可能是此二叉树的是(　　)
例2 某二叉树的树形结构如图所示，其前序遍历结果为BDEFCA，则中序遍历结果为(　　)
A.EDCFBA B.ECFDAB C.BFDEAC D.EDFCBA
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有一棵完全二叉树，已知其中序遍历结果是CADGBEIHJ，则其前序遍历结果应该为(　　)
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
例3 某二叉树对应的一维数组表示如图所示：
下列关于该二叉树的说法正确的是(　　)
A.这是一棵完全二叉树
B.节点F是节点D的孩子节点
C.该二叉树有1个叶子结点
D.该二叉树中序遍历的结果是DBEACF
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　某二叉树用一维数组存储结构如下表所示：
下列有关该二叉树的说法正确的是(　　)
A.该树度为 2 的节点有 4 个
B.该树的前序遍历为 A－B－D－E－G－H－C－F－I
C.该树是完全二叉树，其深度为 4
D.该树中共有 3 个叶子节点，分别是 G、H、I
例4 某二叉树的前序遍历结果为ABCDEF，后序遍历结果为CDBFEA，下列关于该二叉树的说法，正确的是(　　)
A.该二叉树的深度可能为4
B.该二叉树的中序遍历结果可能为CBDAEF
C.该二叉树可能的形态有3种
D.该二叉树度为2的节点可能有3个
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　已知某二叉树的后序遍历结果为BCGEFDA，中序遍历结果为CBAEGDF，下列说法不正确的是(　　)
A.该二叉树不是完全二叉树
B.该二叉树的深度为4
C.该二叉树的前序遍历结果为ACBDEGF
D.该二叉树所对应的一维数组表示为：
0 1 2 3 4 5 6 7 8 9 10 11
A C D B E F G
1.某二叉树中序遍历为ABCDEF，则下列不可能是此二叉树的是(　　)
2.有一棵二叉树如图所示，下列说法正确的是(　　)
A.该二叉树是一棵完全二叉树，树的高度为 3
B.该二叉树的前序遍历为 A，B，D，C，E
C.该二叉树的叶子节点有4个
D.该二叉树的建立只能使用数组来实现
3.下列二叉树中，前序和中序遍历结果一样的选项是(　　)
4.有二叉树形态如图所示，后序遍历结果为abcdefg，则树中与c同层的节点是(　　)
A.f B.e C.d D.b
5.某二叉树从根节点开始，按从上到下、自左往右的顺序用 A－G 字母表示，若补全为完全二叉树后，用一维数组表示如图所示。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G
下列关于该二叉树的说法，正确的是(　　)
A.该二叉树的深度为 3
B.节点 E 的父节点是 B
C.该二叉树的中序遍历结果为 BFDGACE
D.该二叉树的叶子节点为 D、E、F、G
6.用一维数组表示二叉树，如下表所示：
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是(　　)
A.该树中共有 4 个叶子节点
B.该树是完全二叉树，其深度为 4
C.该树的中序遍历为 B－F－D－G－A－C－E
D.该二叉树的结构图为(如图所示)
7.某二叉树的前序遍历结果为 GFDECAB，中序遍历结果为 DFGCAEB。关于该二叉树，以下说法，正确的是(　　)
A.该二叉树的后序遍历为 ADFCBEG
B.该二叉树的深度为 4，节点 C 在第 3 层
C.该二叉树的叶子节点数比非叶子节点数多一个
D.该二叉树可以通过添加 3 个节点后变为完全二叉树
8.某二叉树的中序遍历顺序为DHBEAFCG，后序遍历为HDEBFGCA，则节点E是(　　)
A.A节点的孩子节点 　B.叶子节点
C.H节点的父亲节点 　 D.F节点的兄弟节点
课时2　二叉树的基本操作
知识梳理
1.1　左到右
2.(1)①根节点　从上到下　n－1　②数组的下标　(2)①完全
3.数据域　指针域
4.(1)规则和次序　仅被访问一次　(2)中序遍历　后序遍历
①根节点　左子树　右子树　②左子树　右子树　③根节点
例题精析
例1　C　[本题考查二叉树遍历。中序遍历的方法：左子树－根－右子树，每棵子树，都遵循以上规定。A选项中序遍历为EDFBAC。B选项中序遍历为BEDFAC。D选项中序遍历为BACEDF。]
变式训练　B　[B选项的后序遍历为GFDBEHCA。]
例2　A　[本题考查二叉树的遍历。 前序遍历可知B为二叉树根节点，D和左子树根节点，E和F为左子树的左右孩子。C为F的左孩子，A为树的右子树。该树结构如图所示。因此中序遍历为EDCFBA。]
变式训练　B　[该完全二叉树有9个节点，因此共有4层，其中前3层是满二叉树(7个节点)，第4层有2个节点，画出二叉树的形态和中序遍历路径，可得前序遍历序列。]
例3　D　[根据存储情况画出树如图所示。
A选项最后一层节点没有从左向右依次排列。B选项节点F是节点C的孩子节点。C选项该二叉树有3个叶子结点。]
变式训练　B　[本题考查二叉树的相关知识。根据数组画出树如图所示，可以得到正确的前序遍历序列。]
例4　B　[A为树的根节点，在后序遍历中，B没有紧跟在A的前面，因此B是A的左孩子，CD是B的子树，FE是A的右子树。因此树的形态可能有如图所示的两种情况。]
变式训练　D　[本题考查二叉树的性质和遍历。后序遍历确定根节点，中序遍历由根节点位置划分左右子树。根节点A的左右子树分别为CB和EGDF，C为子树根，B为右节点。同理可以得到整棵树的结构。该树深度为4但不是完全二叉树，前序遍历结果为ACBDEGF，对应的一维数组为]
0 1 2 3 4 5 6 7 8 9 10 11 12
A C D B E F G
随堂检测
1.C　[C选项中序遍历为ACBDEF。]
2.B　[本题考查树的性质。A选项完全二叉树第n－1层为满二叉树，不符合。C选项叶子节点有2个。D选项可以用数组或链表实现。]
3.D　[前序遍历是根左右，中序遍历是左根右，当左子树不存在时，两者相同。]
4.A　[本题考查树的遍历和性质。从后序遍历来看，g是根节点，左右子树分别有3个，左子树先于右子树，因此abc是左子树，def是右子树，c是g的左孩子，f是g的右孩子。]
5.C　[本题考查二叉树性质和遍历。根据题意画出二叉树如图所示：
该二叉树的深度为 4，E 的父节点是 C，中序遍历是 B－F－D－G－A－C－E，该二叉树的叶子节点是F，G，E。]
6.C　[本题考查二叉树的基本知识。第3层节点的索引号为3，4，5，可见B没有左子树，但有右子树，因此不可能是满二叉树，B也不是叶子节点。二叉树形态如图所示：]
7.B　[本题考查二叉树的性质和遍历。
根据前序遍历和中序遍历可画出二叉树。]
8.B　[本题考查树的操作。由题意可知A为根节点，左子树的中序遍历为DHBE，观察其后序遍历，B为左子树的根节点，E为左子树的右子树，因此节点 E是叶子节点。]

展开更多......

收起↑