【数据结构与算法】数据结构初阶：详解二叉树（六）——二叉树应用：二叉树选择题

艾莉丝努力练剑

发布于 2025-11-12 19:05:04

2290

文章被收录于专栏：C / C++C / C++

重要提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。因此，不同的场景我们选择不同的数据结构。

前言：本篇文章，我们继续来看二叉树，来刷一刷选择题，其实也是对前面学过的知识的一个回顾与练习，毕竟笔试面试已经越来越看重程序员的算法能力，把选择题作为一个对已学知识的一个快速回顾——比如说加深对数据结构某个重要性质的记忆、降低记忆成本——还是很值得去做的。我们做这些选择题正有此意：一来加深了对二叉树性质的理解；二来通过做几道代表性的选择题我们将知识点迅速运用了起来，让知识顺利扎根在大脑；三来也是对自己学习二叉树学习情况的一个小测验。

回顾：

正文

一、二叉树性质相关选择题

（一）性质

证明：

假设一个二叉树有 a 个度为2的节点，b 个度为1的节点，c 个叶节点，则这个二叉树的边数是 2a+b，另一方面，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1。

2a + b = a + b + c - 1 ，即： a = c-1。

（二）题目

1、题目1

1、某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（） A 不存在这样的二叉树 B 200 C 198 D 199

解析：

2、题目2

2、在具有 2n 个结点的完全二叉树中，叶子结点个数为（） A n B n+1 C n-1 D n / 2

解析：

在完全二叉树，有多少度为1的节点个数

3、题目3

3、一棵完全二叉树的结点数位为531个，那么这棵树的高度为（） A 11 B 10 C 8 D 12

解析：

4、题目4

4、一个具有767个结点的完全二叉树，其叶子结点个数为（） A 383 B 384 C 385 D 386

解析：

二叉树性质相关选择题答案： 1、B 2、A 3、B 4、B

二、链式二叉树遍历相关选择题

1、题目1

1、某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（） A. ABDHECFG B. ABCDEFGH C. HDBEAFCG D. HDEBFGCA

解析：

2、题目2

2、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。则二叉树根结点为（） A E B F C G D H

解析：先序遍历打印的一个是就是根节点，知道了先序遍历，根节点就找到了。

3、题目3

3、设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。 A adbce B decab C debac D abcde

解析：

方法： 确定一个删掉一个，也就是说：已知任意两个求第三个。

根据后序遍历找到根节点，中序遍历看左右孩子。如下图：

1、根据后序遍历我们确定根节点就是a：

2、确定了，我们就把它删掉，以免对我们产生干扰：

3、确定了a是根节点，我们看一下中序遍历，a的左子树是b，确定的就删掉：

4、我们看：a的右子树，中序遍历的结果是dce，后序遍历的结果是dec，ab我们都删掉了，没有干扰项。dec，根节点是c，既然根节点是c，我们再回到中序遍历，c的左子树是d，c的右子树是e。后面大家做这种题目就可以采用这种方法。

4、题目4

4、某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出（同一层从左到右）的序列为（） A FEDCBA B CBAFED C DEFCBA D ABCDEF

解析：

只有左子树，没有右子树。

5、加餐1：题目5

5、已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（） A.ABDGHJKCEFILM B.ABDGJHKCEILMF C.ABDHKGJCEILMF D.ABDGJHKCEIMLF

解析：

由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间。

详解： 我们根据后序遍历可知，A是根节点—— A的左子树：JGDHKB，A的右子树：ELIMCF； A的左子树的根：B，A的右子树的根：C； B的左子树：JGDHK，B的右子树：空，C的左子树：ELIM，C的右子树：F； B的左子树的根：D，C的左子树根：E； D的左子树的根：G，D的右子树的根：H，E的右子树的根：I。

6、加餐2：题目6

6、已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（） A.4 2 5 7 6 9 1 B.4 2 7 5 6 9 1 C.4 7 6 1 2 9 5 D.4 7 2 9 5 6 1

解析：

首先根据前序和中序遍历确定二叉树结构：前序遍历是根左右，可知前序遍历第一个数5是根节点。在中序遍历中找到5，左边4 7是左子树，右边6 9 1 2是右子树。前序中5后面是7，7是左子树的根，中序中7左边是4，所以7的左子节点是4 。前序接着是4、9，9是右子树的一部分，中序中5右边6在9前，所以9是6的父节点，我们逐步构建出二叉树。已知后序遍历顺序是左右根。正确构建二叉树后，后序遍历应为4 7 6 1 2 9 5。

链式二叉树遍历相关选择题答案： 1、A 2、A 3、D 4、A 5、B 6、C

三、二叉树树度相关选择题

1、题目1

1、一颗拥有1000个结点的树度为4，则它的最小深度是（） A.5 B.6 C.7 D.8

解析·：

要使树深度最小，应让树尽可能“满”，即除最后一层，每层结点数达该度下最大值（度为4，则每层最多4^(i - 1)个结点，i 为层数）。设深度为h，前h - 1层是满的，结点数和为(4^(h - 1) - 1) / (4 - 1) 。当h = 5，前4层和为(4^4 - 1) / 3 = 85；当h = 6，前5层和为(4^5 - 1) / 3 = 341；当h = 7，前6层和为(4^6 - 1) / 3 = 1365 > 1000 。且前5层和341 < 1000，前6层和1365 > 1000，所以最小深度是6 。