🏷️ 知识点：Ds.05.02.01

下列关于二叉树的说法中，正确的是（ ）。

A. 度为2的有序树就是二叉树 B. 含有n个结点的二叉树的高度为⌊log₂n⌋+1 C. 在完全二叉树中，若一个结点没有左孩子，则它必是叶结点 D. 含有n个结点的完全二叉树的高度为⌊log₂n⌋

[tag_link]

correct answer: C

结论

完全二叉树中没有左孩子的结点只能是叶结点；一般二叉树高度并非固定公式。

推导

完全二叉树中没有左孩子的结点只能是叶结点；一般二叉树高度并非固定公式。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

“二叉树为空”意味着二叉树（ ）。

A. 根结点没有子树 B. 不存在 C. 没有结点 D. 由一些没有赋值的空结点构成

[tag_link]

correct answer: C

结论

空二叉树定义为结点数为0，并不表示二叉树不存在。

推导

空二叉树定义为结点数为0，并不表示二叉树不存在。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

下列关于完全二叉树的说法中，正确的是（ ）。

A. 在完全二叉树中，叶结点的双亲的左兄弟（若存在）一定不是叶结点 B. 任何一棵二叉树中，叶结点数为度为2的结点数减1 C. 完全二叉树不适合顺序存储结构，只有满二叉树适合 D. 结点按完全二叉树层序编号时，第i个结点的左孩子编号为2i

[tag_link]

correct answer: A

结论

完全二叉树按层从左到右填充，叶结点双亲的左兄弟若存在必有孩子。

推导

完全二叉树按层从左到右填充，叶结点双亲的左兄弟若存在必有孩子。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

具有10个叶结点的二叉树中有（ ）个度为2的结点。

A. 8 B. 9 C. 10 D. 11

[tag_link]

correct answer: B

结论

二叉树有 n₀=n₂+1；10个叶结点对应9个度为2结点。

推导

二叉树有 n₀=n₂+1；10个叶结点对应9个度为2结点。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。

A. h B. 2h−1 C. 2h+1 D. h+1

[tag_link]

correct answer: B

结论

只有度0、度2时，为达到高度h，除根外每层至少延伸一条二分支，最少2h−1个结点。

推导

只有度0、度2时，为达到高度h，除根外每层至少延伸一条二分支，最少2h−1个结点。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

具有n个结点且高度为n的二叉树的数目为（ ）。

A. log₂n B. n/2 C. n D. 2ⁿ⁻¹

[tag_link]

correct answer: D

结论

高度等于结点数时每个非根结点都可独立选左或右孩子，共2ⁿ⁻¹种。

推导

高度等于结点数时每个非根结点都可独立选左或右孩子，共2ⁿ⁻¹种。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

假设一棵二叉树的结点数为50，则它的最小高度是（ ）。

A. 4 B. 5 C. 6 D. 7

[tag_link]

correct answer: C

结论

最小高度为⌈log₂(50+1)⌉=6。

推导

最小高度为⌈log₂(50+1)⌉=6。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

设二叉树有2n个结点，且m<n，则不可能存在（ ）的结点。

A. n个度为0 B. 2m个度为0 C. 2m个度为1 D. 2m个度为2

[tag_link]

correct answer: C

结论

由n₀=n₂+1及总数2n可得 n₁=2n−2n₂−1，因此度为1结点数必为奇数，2m个度为1不可能。

推导

由n₀=n₂+1及总数2n可得 n₁=2n−2n₂−1，因此度为1结点数必为奇数，2m个度为1不可能。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

一个具有1025个结点的二叉树的高度h为（ ）。

A. 11 B. 10 C. 11～1025 D. 10～1024

[tag_link]

correct answer: C

结论

二叉树高度范围为⌈log₂(1025+1)⌉=11至1025。

推导

二叉树高度范围为⌈log₂(1025+1)⌉=11至1025。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

设二叉树只有度为0和2的结点，其结点数为15，则该二叉树的最大深度为（ ）。

A. 4 B. 5 C. 8 D. 9

[tag_link]

correct answer: C

结论

仅有度0、2且15个结点时，交替单支可得最大深度8。

推导

仅有度0、2且15个结点时，交替单支可得最大深度8。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

高度为h的完全二叉树最少有（ ）个结点。

A. 2ʰ B. 2ʰ⁺¹ C. 2ʰ−1 D. 2ʰ⁻¹

[tag_link]

correct answer: C

结论

完全二叉树高度h至少包含前h−1层满二叉树及最后层1个结点，即2ʰ⁻¹。

推导

完全二叉树高度h至少包含前h−1层满二叉树及最后层1个结点，即2ʰ⁻¹。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点数最少是（ ）。

A. 39 B. 52 C. 111 D. 119

[tag_link]

correct answer: A

结论

前5层至少31个结点，再加第6层8个叶结点，最少39个。

推导

前5层至少31个结点，再加第6层8个叶结点，最少39个。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。

若一棵深度为6的完全二叉树的第6层有3个叶结点，则该二叉树共有（ ）个叶结点。

A. 17 B. 18 C. 19 D. 20

[tag_link]

correct answer: A

结论

第5层有16个结点，其中最左2个是第6层3个叶结点的双亲，其余14个为叶，加第6层3个叶得17。

推导

第5层有16个结点，其中最左2个是第6层3个叶结点的双亲，其余14个为叶，加第6层3个叶得17。

易错点

完全树第6层只能从左连续填充，不能把第5层16个结点都当叶。

一棵完全二叉树上有1001个结点，其中叶结点的个数是（ ）。

A. 250 B. 500 C. 254 D. 501

[tag_link]

correct answer: D

结论

最后一个分支结点下标为⌊1001/2⌋=500，所以叶结点为1001−500=501。

推导

最后一个分支结点下标为⌊1001/2⌋=500，所以叶结点为1001−500=501。

易错点

完全二叉树的叶区间从⌊n/2⌋+1到n。

若一棵二叉树有126个结点，在第7层（根结点在第1层）至多有（ ）个结点。

A. 32 B. 64 C. 63 D. 不存在第7层

[tag_link]

correct answer: C

结论

7层满二叉树有127个结点，126个结点时只能缺第7层最右1个，故最多63个。

推导

7层满二叉树有127个结点，126个结点时只能缺第7层最右1个，故最多63个。

易错点

层号从根为第1层计数，不能把64当作第7层上限。

一棵有124个叶结点的完全二叉树，最多有（ ）个结点。

A. 247 B. 248 C. 249 D. 250

[tag_link]

correct answer: B

结论

二叉树n₀=n₂+1，n₂=123；n=124+123+n₁=247+n₁，完全树n₁可为1，最大248。

推导

二叉树n₀=n₂+1，n₂=123；n=124+123+n₁=247+n₁，完全树n₁可为1，最大248。

易错点

叶数不能单独确定n₁，完全树奇偶性决定最大值。

某完全二叉树T中，结点数最大的层有8个结点，则T中至多有（ ）个结点。

A. 8 B. 15 C. 23 D. 31

[tag_link]

correct answer: C

结论

最大层为第4层8个；再有第5层8个时总数15+8=23。

推导

最大层为第4层8个；再有第5层8个时总数15+8=23。

易错点

结点数最大的层不必是最后一层，但完全树各层容量受限。

在一棵完全二叉树中，其根的序号为1，（ ）可判定序号p和q的两个结点是否在同一层。

A. ⌊log₂p⌋=⌊log₂q⌋ B. log₂p=log₂q C. ⌊log₂p⌋+1=⌊log₂q⌋ D. ⌊log₂p⌋=⌊log₂q⌋+1

[tag_link]

correct answer: A

结论

完全树结点所在层为⌊log₂i⌋+1，故同层当且仅当⌊log₂p⌋=⌊log₂q⌋。

推导

完全树结点所在层为⌊log₂i⌋+1，故同层当且仅当⌊log₂p⌋=⌊log₂q⌋。

易错点

不要比较log值本身，层号取整后才相同。

假定一棵三叉树的结点数为50，则它的最小高度为（ ）。

A. 3 B. 4 C. 5 D. 6

[tag_link]

correct answer: C

结论

高度h的三叉树最多(3^h−1)/2个结点，(3^4−1)/2=40<50≤121，故最小高度5。

推导

高度h的三叉树最多(3^h−1)/2个结点，(3^4−1)/2=40<50≤121，故最小高度5。

易错点

高度按根为第1层，使用向上取整边界。

对于一棵满二叉树，共有n个结点和m个叶结点，高度为h，则（ ）。

A. n=h+m B. n+m=2h C. m=h−1 D. n=2^h−1

[tag_link]

correct answer: D

结论

满二叉树按层求和n=1+2+…+2^(h−1)=2^h−1，故D。

推导

满二叉树按层求和n=1+2+…+2^(h−1)=2^h−1，故D。

易错点

指数是h，不是乘法2h。

在一棵完全二叉树中，含有 n0 个叶结点，当度为1的结点数为1时，该树的高度是多少？当度为1的结点数为0时，该树的高度是多少？

[tag_link]

参考答案

当n1=1时，n=2n0，h=floor(log2 n0)+2；当n1=0时，n=2n0−1，h=ceil(log2 n0)+1。

推导过程

由n2=n0−1及n=2n0+n1−1，分别代入完全二叉树的层容量边界得到两种高度。

评分要点

写出n2=n0−1；分别代入n1=1/0；说明取整与层次从1开始。

易错点

把树高、深度和边数口径混用。

一棵有 n 个结点的满二叉树有多少个分支结点和多少个叶结点？该满二叉树的高度是多少？

[tag_link]

参考答案

分支结点数为(n−1)/2，叶结点数为(n+1)/2，高度为log2(n+1)。

推导过程

满二叉树n1=0且n0=n2+1；因此n=2n0−1，n2=(n−1)/2，n0=(n+1)/2，且n=2^h−1。

评分要点

使用n0=n2+1；给出两个数量公式；由2^h−1反解高度。

易错点

把满二叉树误写成完全二叉树的范围。

已知完全二叉树的第9层有240个结点，则整个完全二叉树有多少个结点？有多少个叶结点？

[tag_link]

参考答案

总结点数495，叶结点数248。

推导过程

第9层最多256个，现有240个故为最后一层；前8层满，有2^8−1=255个结点，总数495。第9层240个均为叶，第8层120个双亲，余8个叶，故叶数240+8=248。

评分要点

判断第9层为末层；计算255+240；计算第8层8个叶并求总叶数。

易错点

只把第9层240当作全部叶，漏掉第8层叶结点。

一棵高度为h的满m叉树有如下性质：根结点所在层次为第1层，第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。若按层次自顶向下、同一层自左向右，从1开始对全部结点编号，求各层结点数、编号i结点的双亲编号、第k个孩子编号，以及有右兄弟的条件和右兄弟编号。

[tag_link]

参考答案

第r层有m^(r−1)个结点；parent(i)=floor((i−2)/m)+1(i>1)；child_k(i)=(i−1)m+k+1；有右兄弟当该结点不是双亲的第m个孩子且右兄弟存在，此时编号为i+1。

推导过程

按层序编号时第r层容量为m^(r−1)。第i结点的孩子编号连续为(i−1)m+2至(i−1)m+m+1，反解得到双亲公式；非第m孩子即(i−1)%m≠0。

评分要点

写出层容量；推导父/子下标；说明边界、右兄弟存在性。

易错点

忽略编号从1开始或把不存在的孩子当成右兄弟。