资源简介

专题15　树
知识点一　树的性质
1.假设完全二叉树的树根为第1层，树中第10层有5个叶子结点，则完全二叉树最多有个结点(　　)
A.511 B.516
C.2037 D.2047
2.下列Python表达式用于表示“一棵n个节点的二叉树的叶子节点最大可能数量”，正确的是(　　)
A.n－1 B.n//2
C.n//2＋1 D.n/2
3.某二叉树的结构如图所示，下列说法不正确的是(　　)
A.该二叉树是一棵完全二叉树
B.该二叉树的叶子节点数是3个
C.该二叉树的中序遍历结果是DCBEAF
D.该二叉树的度为2
4.某树的结构如右，下列说法正确的是(　　)
A.该树的度为4 B.该树的高度为4
C.该树的叶子节点为3个 D.节点F和G是兄弟节点
5.一棵有n(n>0)个节点的二叉树，其节点为0度或2度，则此树的最大高度是(　　)
A.(n＋1)//2 B.n//2
C.(n－1)//2 D.int(log2n＋1)
6.若一棵二叉树具有10个度为2的节点，5个度为1的节点，则该树形结构的总边数是(　　)
A.14 B.25
C.23 D.不能确定
7.将一棵有1000个节点的完全二叉树按照从上到下、从左到右的顺序依次进行编号，根节点的编号为1，则编号为35的节点的右孩子编号为(　　)
A.36 B.70
C.72 D.71
8.下列有关二叉树的论述中，正确的是(　　)
A.只有一个节点的二叉树的度为0
B.二叉树的度为2
C.二叉树的左右子树可任意交换
D.完全二叉树的所有节点的度均为2
9.若一棵二叉树具有10个叶子节点，则树形结构度为2的节点数为(　　)
A.8 B.9
C.10 D.11
10.若一棵二叉树共有10个节点，其中4个是叶子节点，则度为1的节点数量为(　　)
A.3 B.4
C.5 D.6
知识点二　树的遍历
1.如图所示的二叉树，若要得到一个递增序列，可以用下列遍历方式是(　　)
A.前序遍历 B.中序遍历
C.后序遍历 D.逐层遍历
2.有一棵二叉树如图所示：关于该树，以下说法正确的是(　　)
A.该二叉树是一棵完全二叉树，树的高度为4
B.该二叉树的前序遍历为25、15、46、6、18、28、58、12、22、35、60
C.该二叉树的叶子节点有8个
D.若用数组(第一个元素下标为0)来表示该树，则节点“46”在数组中下标为2
3.某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为(　　)
A.ABCDEF B.FEDCBA
C.DFACBE D.FDBCAE
4.某二叉树的前序遍历结果为ABCDEF，后序遍历结果为CDBFEA，下列关于该二叉树的说法，正确的是(　　)
A.该二叉树的深度可能为4
B.该二叉树的中序遍历结果可能为CBDAEF
C.该二叉树可能的形态有3种
D.该二叉树度为2的节点可能有3个
5.已知一棵二叉树如图所示，下列说法正确的是(　　)
A.树的高度是4，节点F是唯一的叶子节点
B.中序、后序的遍历方式，节点F先于节点D、E访问
C.前序遍历的结果为A－B－C－D－E－F
D.使用数组可以表示为[‘A’，‘B’，‘C’，‘D’，‘E’，‘F’]
6.用一维数组来表示某二叉树如表所示，则下列说法不正确的是(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H
A.该二叉树的深度为4
B.节点B有两个孩子节点，分别为E和F
C.该二叉树的中序遍历结果为DBGEAFHC
D.叶子节点的数量比度为2的节点数量多1
7.如图所示，将二叉树A的根节点与二叉树B的根节点连接，使得二叉树A成为二叉树B的左子树，合并为一棵新的二叉树C。下列说法中正确的是(　　)
A.二叉树C的高度为3
B.二叉树C的叶子节点数量为3
C.二叉树C是一棵完全二叉树
D.二叉树C中序遍历的结果是一个有序序列
8.已知一棵二叉树的前序遍历序列为ABCDEFG，则该二叉树中序遍历序列可能为(　　)
A.CABDEFG B.ABCDEFG
C.DACEFBG D.ADBCFEG
9.某二叉树从根节点开始，按从上到下、自左往右的顺序用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
10.二叉树的中序遍历为BAEDFC，后序遍历为BEFDCA，其前序遍历为(　　)
A.ABDEFC B.ABDCEF
C.ABCDEF D.ABCDFE
11.已知某二叉树的后序遍历结果为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
12.如图所示二叉树的前序遍历序列是(　　)
A.A－B－C－D－E－G－H－F－I
B.A－B－D－E－G－H－C－F－I
C.D－B－E－G－H－A－C－F－I
D.B－D－G－H－E－A－F－I－C
13.某二叉树用数组表示，如图所示，下列说法正确的是(　　)
A.该二叉树是完全二叉树
B.该二叉树的深度是3
C.该二叉树的叶子节点有2个
D.该二叉树的中序遍历为A－D－E－F－G－C－B
14.有一棵二叉树，如图所示，下列说法正确的是(　　)
A.此二叉树是完全二叉树
B.此二叉树的深度是3
C.此二叉树的中序遍历为H－D－B－E－A－C－F
D.此二叉树用一维数组表示为['A'，'B'，''，'C'，'D'，'E'，''，'F'，''，'H']
15.某表达式树如图所示，则该树的后序遍历结果是(　　)
A.3＋7*5－8/2 B.8/2*5＋37－
C.37＋5*82/－ D.82/5－3＋7*
16.用数组表示二叉树的示意图如下所示，则该二叉树的中序遍历序列为(　　)
A.BEDFAC B.ABDEFC
C.DBEAFC D.BDAECF
17.已知二叉树T节点的前序遍历序列为A－B－D－E－F－G－C，中序遍历序列是D－B－F－E－G－A－C，则其后序遍历序列是(　　)
A.F－D－G－E－B－C－A B.D－F－G－E－B－C－A
C.B－F－D－G－B－C－A D.C－G－F－E－D－B－A
18.某二叉树前序遍历的结果为“大好河山”，则中序遍历的结果不可能是(　　)
A.大好河山 B.河山好大
C.好山大河 D.山河好大
19.已知二叉树的后序遍历序列是DCBAE，中序遍历序列是BDCEA，它的前序遍历序列是(　　)
A.EBDCA B.ACDBE
C.ECDBA D.EBCDA
20.某二叉树的前序遍历为A－B－D－E－C－F－G，中序遍历为B－D－E－A－F－C－G，则下列说法正确的是(　　)
A.该二叉树的叶子节点有4个
B.该二叉树的后序遍历为E－D－B－F－G－C－A
C.该二叉树的高度为4，是一棵完全二叉树
D.用数组来表示该树，若A的下标为0，则E的下标为5
21.某二叉树的前序遍历和后序遍历正好相反，则该二叉树一定是(　　)
A.空或只有一个节点 B.高度等于其节点数
C.任一节点无左孩子 D.任一节点无右孩子
22.某二叉树前序遍历为ABDCE，后序遍历为DBECA，则该二叉树可能情况数量是(　　)
A.1 B.2
C.4 D.6
23.有二叉树的前序遍历序列为A－B－C－E－F－G－D，中序遍历序列为A－E－C－F－G－B－D，则关于该二叉树的说法正确的是(　　)
A.该二叉树根节点的度为1
B.该二叉树的高度为4
C.该二叉树中节点G是节点C的左孩子
D.该二叉树中叶子节点的个数为4
专题15　树
知识点一
1.C　[本题考查树的性质。在完全二叉树中，叶子节点出现在最后一层或倒数第二层中。当树有11层时，达到最多有211个结点。完全二叉树倒数第二层是满二叉树，最后一层从左向右分布节点，因此最后一层缺少10个叶子节点。211－1－10＝2037。]
2.C　[本题考查二叉树的性质。由n0＝n2＋1和n0＋n1＋n2＝n可得到n0＋n1＋n0－1＝n，二叉树度为1的节点个数n1为0时，叶子节点个数n0达到最多，得到n0＝(n＋1)/2。总节点个数是奇数个，(n＋1)/2等价于n//2＋1。]
3.A　[本题考查二叉树的性质。该树不是完全二叉树。叶子节点有DEF，节点中最大的度为2。]
4.B　[本题考查树的性质。A选项数的度取决于节点的最大度数，因此该树的度为3。]
5.A　[本题考查二叉树基本性质。该二叉树的节点的度都为0或2，即除根节点外，其余每个节点都有一个兄弟节点。题目要求树的最大高度，每层就只有2个节点(除了根节点)，若总节点数加上1，相当于令第1层也变成两个节点，那么总层数就是(n＋1)//2。]
6.B　[根据题目已知度为2的节点为10个，则叶子节点为11个，所以总的节点数为10＋5＋11＝26，在二叉树的所有节点中，除了根节点没有前驱外，每个节点均有且只有一个前驱节点，因此26个节点的二叉树的总边数为25条。]
7.D　[在一棵完全二叉树中，若父节点的编号为n，则它的左孩子编号为2*n，右孩子的编号为2*n＋1，则编号为35的节点的右孩子编号为71。]
8.A　[节点所拥有的子树个数称为该节点的度，只有一个节点的二叉树的度为0，二叉树的度小于等于2，完全二叉树最下面两层的节点度数小于2，二叉树的左右子树交换会改变数据的层次关系。]
9.B　[根据二叉树的性质，任意一棵二叉树中，若度为2节点数量为n2，叶子节点数为n0，则n0＝n2＋1，故题目中度为2的节点数是9个。]
10.A　[二叉树的所有节点的度都小于或者等于2，题目中已知叶子节点数为4，则度为2的节点数是4－1＝3，因此度为1的节点数是10－4－3＝3。]
知识点二
1.B　[最小的数是3，是最下层的左子树，因此是中序遍历。]
2.D　[D选项25的索引是0，第二层中索引分别是1和2。]
3.C　[根据树的形态，画出后序遍历的路径，从而确定每个节点的值。]
4.B　[A为树的根节点，在后序遍历中，B没有紧跟在A的前面，因此B是A的左孩子，CD是B的子树，FE是A的右子树。因此树的形态可能有如图所示的两种情况。]
5.B　[A选项B和E也是叶子节点。B选项F是D的左子树，在中序、后序遍历中，F先于D，D和E分别是C的左右子树，D肯定先于E。]
6.B　[构建的二叉树如图。深度为4，B的两个孩子节点为D和E。]
7.C　[本题考查二叉树的性质和遍历。新二叉树高度为4；叶子节点数量为4，是一棵完全二叉树；中序遍历的结果为84251637，不是一个有序序列。]
8.B　[本题考查二叉树的相关知识。前序遍历找出根A，中序遍历根据根的位置，区别左右子树。A选项左子树为C，但C在前序遍历中后于B访问，不正确。C选项同A选项。D选项该树没有左子树，在右子树中，B为根，D为B的左孩子，但在前序中D后于C访问，不正确。B选项前序遍历为根左右，中序遍历为左根右，当树缺失左孩子时，前中序遍历是一样的。]
9.C　[本题考查二叉树性质和遍历。根据题意画出二叉树如图所示：该二叉树的深度为4，E的父节点是C，中序遍历是B－F－D－G－A－C－E，该二叉树的叶子节点是F，G，E。]
10.C　[本题考查二叉树的相关知识。后序遍历确定根节点，中序遍历区分左右子树。根据二叉树的中序遍历和后序遍历可知，该二叉树的形状如图所示，前序遍历为：ABCDEF。]
11.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
12.B　[本题考查二叉树的遍历。前序遍历的顺序为根－左－右，第一个遍历的节点一定是A，接下来遍历A的左子树，最后遍历A的右子树，遍历结果应为A－B－D－E－G－H－C－F－I。]
13.D　[根据存储结构画出二叉树如图所示。A选项该二叉树不是完全二叉树。B选项该树深度为4。C选项叶子节点有3个。]
14.C　[本题考查二叉树的相关知识。A选项节点C缺少左子树，不是完全二叉树。B选项该二叉树的深度是4。D选项节点C前没有空节点。]
15.C　[本题考查树的遍历。访问顺序左、右、根，从最左最高层子树开始遍历。最后访问根结点。]
16.A　[本题考查树的存储和遍历。D是B的右孩子，C节点没有孩子，D的左右孩子为E和F。中序遍历是左根右，B的左孩子缺失，因此先访问B再访问B的右子树EDF，接着访问根节点A，再访问右孩子C。]
17.B　[本题考查二叉树的遍历。根据前序可以确定根节点为A，把中序分为(DBFEG)A(C)，B为子树DBFEG根节点，E为子树FEG的根节点，画出二叉树，并确定后序遍历。]
18.C　[本题考查树的遍历。前序遍历为根左右，A选项任一节点没有左节点，则前中序均为根右。B选项河是第1个左节点，则好是大的左节点，是河的根，山为河的兄弟。D选项任一节点没有右节点。C选项好是大的左节点，山是右节点，或山是大的左节点，是好的父节点，则前序遍历不对了。]
19.D　[本题考查二叉树的遍历。从后序遍历来看，E为根节点，因此把中序遍历分成(BDC)E(A)三部分，在子树BDC中，B为根节点，DC为右子树，在子树DC中，C为根节点。]
20.B　[本题考查二叉树的性质、存储和遍历。根据前序遍历，可知A为根节点，中序序列可以划分为(BDE)A(FCG)，则左子树BDE中，B为根节点，DE为右子树，DE子树中，E为D的右节点。右子树FCG中，C为根节点，F和G分别为左右子树。根据上述描述，画出树，可知叶子节点有EFG3个，后序遍历为EDBFGCA，树的高度为4，但不是完全二叉树。]
21.B　[本题考查二叉树的遍历。二叉树的前序遍历是：根－左－右，后序遍历是：左－根－右，当前序遍历和后序遍历恰好相反的时候，可以是没有左子树，也可以是没有右子树，因此二叉树的高度等于节点数。]
22.C　[本题考查二叉树遍历的相关知识。左右子树的根节点都只有一个子节点，以下四种情况的前序和后序遍历都符合题目要求：]
23.A　[本题考查二叉树的性质和遍历。根据二叉树的前序遍历和中序遍历画出二叉树。该二叉树的根节点A的度为1，高度为5，节点G是节点F的右孩子。该二叉树的叶子节点是E、G、D。]

展开更多......

收起↑