🏷️ 知识点：Ds.05.04.02

共 8 道相关题目

课后题年第 76 题数据结构选择题

下列关于树的说法中，正确的是（　　）。Ⅰ．对于有n个结点的二叉树，其高度为log₂n Ⅱ．完全二叉树中，若一个结点没有左孩子，则它必是叶结点 Ⅲ．高度为h(h>0)的完全二叉树对应的森林所含的树的个数一定是h Ⅳ．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

A. Ⅰ和Ⅲ B. IV C. Ⅰ和Ⅱ D. Ⅱ

[tag_link]

正确答案：D

结论

选项 D 符合本题的树/森林规则。

推导

Ⅰ错误：一般二叉树高度不由log₂n唯一确定；Ⅱ正确：完全二叉树无左孩子即无右孩子；Ⅲ错误：森林棵数不必等于h；Ⅳ错误：同父叶子转换后会合并兄弟关系。

易错点

本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。

课后题年第 77 题数据结构选择题

利用二叉链表存储森林时，根结点的右指针是（　　）。

A. 指向最左兄弟 B. 指向最右兄弟 C. 一定为空 D. 不一定为空

[tag_link]

正确答案：D

结论

选项 D 符合本题的树/森林规则。

推导

单棵树时根无兄弟，right为空；多棵树时根的right指向下一棵树根，故不一定为空。

易错点

本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。

课后题年第 78 题数据结构选择题

设森林F中有3棵树，第1、2、3棵树的结点数分别为M₁、M₂和M₃，与森林F对应的二叉树根结点的右子树上的结点数是（　　）。

A. M B. M₁+M₂ C. M₃ D. M₂+M₃

[tag_link]

正确答案：D

结论

选项 D 符合本题的树/森林规则。

推导

森林根依次成为右兄弟，根的右子树包含第2、3棵树，结点数为M₂+M₃。

易错点

本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。

课后题年第 81 题数据结构选择题

设森林F对应的二叉树是一棵具有16个结点的完全二叉树，则森林F中树的数目和结点最多的树的结点数分别是（　　）。

A. 2和8 B. 2和9 C. 4和8 D. 4和9

[tag_link]

正确答案：D

结论

选项 D 符合本题的树/森林规则。

推导

16结点完全二叉树根右链为1→3→7→15，得到4棵树；根及左子树共9结点。

易错点

本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。

课后题年第 87 题数据结构选择题

设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲结点的右孩子，下列结论中正确的是（）。

A. 在树T中，X是其双亲结点的第一个孩子 B. 在树T中，X一定无右边兄弟 C. 在树T中，X一定是叶结点 D. 在树T中，X一定有左边兄弟

[tag_link]

正确答案：D

推导

二叉树的right child对应原树中的右兄弟；X成为双亲的右孩子，说明X在原树中不是第一个孩子，必有左兄弟。

易错点

区分二叉树right child与原树右孩子：前者表示右兄弟，不推出叶结点或无右兄弟。

课后题年第 89 题数据结构选择题

在森林的二叉树表示中，结点M和结点N是同一父结点的左孩子和右孩子，则在该森林中（）。

A. M和N有同一双亲 B. M和N可能无公共祖先 C. M是N的孩子 D. M是N的左兄弟

[tag_link]

正确答案：B

推导

二叉树中的同一父结点左右孩子在森林转换后分别表示一个结点及其第一个孩子/后续兄弟关系，M、N可能跨越不同原树而无公共祖先，故B。

易错点

不要把二叉树父子关系直接当成森林父子关系；转换后left/right含义不同。

课后题年第 90 题数据结构综合题

给定一棵树的先根遍历序列和后根遍历序列，能否唯一确定一棵树？若能，请举例说明；若不能，请给出反例。

[tag_link]

参考答案

有序树且结点标识互异时，孩子兄弟二叉树的先序等于原树先根，中序等于原树后根；先序与中序可唯一重建二叉树，故能唯一确定。若是一般二叉树只给先序与后序，或允许重复标识，则不成立：例如只有 A、B 两个结点时，B 作 A 的左孩子或右孩子，先序均为 AB、后序均为 BA。

推导过程

孩子兄弟转换把第一个孩子连为 left、下一个兄弟连为 right；递归展开可得先序访问根及孩子链、后序访问孩子后根与兄弟链，恰对应原树先根/后根。互异标识保证中序根划分唯一。

复杂度与边界

时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。

易错点

不要把一般二叉树的先序+后序误当作总能唯一重建；本题能唯一确定依赖转换后得到的是先序+中序且结点标识互异。

评分要点

写出核心结构对应关系或伪代码
给出正确性理由
给出复杂度与边界

课后题年第 92 题数据结构综合题

给定二叉树先序序列 ABDEHCFIMGJKL、中序序列 DBHEAIMFCGKLJ，完整重建二叉树并转换为森林，写出二叉树边、森林父子边以及先根和后根序列。

[tag_link]

参考答案

二叉树边为 A-L-B、A-R-C、B-L-D、B-R-E、E-L-H、C-L-F、C-R-G、F-L-I、I-R-M、G-R-J、J-L-K、K-R-L。转换森林的根链为 A→C→G→J，父子边为 A-B、A-E、B-D、E-H、C-F、F-I、F-M、J-K、J-L；森林先根为 ABDEHCFIMGJKL，后根为 DBHEAIMFCGKLJ。

推导过程

先序首项 A 为根；在中序 DBHE|A|IMFCGKLJ 中划分左右子树，递归得到 B/E/H 与 C/F/G/J，再按孩子兄弟规则将右链解释为兄弟链。

复杂度与边界

时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。

易错点

右指针在孩子兄弟表示中是兄弟而非右孩子；森林根链也不能误报成同一棵树的父子链。

评分要点

写出核心结构对应关系或伪代码
给出正确性理由
给出复杂度与边界

← 返回真题分析