二叉树例题详解

tiger · 发表于 2023-3-12 16:02:00

本帖最后由 tiger 于 2023-3-12 16:15 编辑

1.一个完全二叉树的节点总数是18，叶节点数量为（）

A.7个 B.8个 C.9个 D.10个

完全二叉树：所有叶节点都在左边

18-1=17去掉根

17-2-4-8最多有4层

=15-12

= 3

剩三个叶节点在左边

8-2+3=9最上面一层的左边两个分出左边三个节点，那两个不是叶节点

9个叶节点

选C

答案：C

2.二叉树的第十层的节点数的最大数目为（）

A.10 B.100 C.512 D.1024

问最大数目

那个理想二叉树，一定是满二叉树

十层，1，2，4，8，16，32，64，128，256，512

2^(10-1)

512

答案：C

3.一颗深度为K的满二叉树有（）个节点

A.2^K-1 B.2^K C.2*K D.2K-1

满二叉树每一层都比上一层多2倍个节点

符合^的意义

但还得减那个根

答案：A

tiger · 发表于 2023-3-12 16:04:18

tiger · 发表于 2023-3-12 16:16:23

不知道对不对

tiger · 发表于 2023-3-12 16:16:57

https://bbs.singera.cn/forum.php ... &fromuid=100250

tiger · 发表于 2023-3-12 16:18:43

二叉树例题详解
https://bbs.singera.cn/forum.php ... &fromuid=100250
(出处: 信息学基地社区)

tiger · 发表于 2023-3-19 09:07:04

1.一个完全二叉树的节点总数是18，叶节点数量为（）
A.7个 B.8个 C.9个 D.10个
完全二叉树：
            叶节点
所有叶节点都在左边
18-1=17 去掉根
17-2-4-8 最多有4层
  = 15-12
  = 3
剩三个叶节点在左边
8-2+3=9 最上面一层的左边两个分出左边三个节点，那两个不是叶节点
9个叶节点
选C
答案：C
2.二叉树的第十层的节点数的最大数目为（）
A.10 B.100 C.512 D.1024
问最大数目
那个理想二叉树，一定是满二叉树
十层，1，2，4，8，16，32，64，128，256，512
2^(10-1)
512
答案：C
3.一颗深度为K的满二叉树有（）个节点
A.2^K-1 B.2^K C.2*K D.2K-1
满二叉树每一层都比上一层多2倍个节点
符合^的意义
但还得减那个根
答案：A
4.一个n个结点的完全二叉树，则该二叉树的高度为（）
A.n/2 B.log(n) C.log(n)/2 D.floor(log(2n))+1
我们可以用举例子的方法验证：
就举上图的例子
10个节点
10*2=20
Log20=1.3010299956639811952137389
            2+1=3层答案：D
5. 一个完全二叉树的节点总数是1001，叶节点数量为（）
A.250个 B.500个 C.254个 D.501个
1001-1=1000
2，4，8，16，32，64，128，256
1000-510=490
256-ceil（490/2）+490
=256-245+490
=11+490
=501
答案：D
6.在一棵具有k层的满三叉树中，节点总数为（）个
A.（3k-1）/2 B.3k-1 C .(3k-1)/3
D.3k
满二叉树的节点数是2k-1，-1是因为去掉根，2k是满二叉树的总结点数
以此为例：满三叉树就有3k-1个节点
答案：B

二叉树例题详解

本帖子中包含更多资源