我要招人

去企业版

首页 > 试题广场 >

含有n个叶子结点的最优二叉树中共有()个分支结点。

[单选题]

```
n一2
```
```
n-1
```
```
2n-1
```
```
2n+1
```

推荐

白驹之过隙

选B。

最优二叉树就是从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树，使树的权值最小，最优二叉树是带权路径长度最短的二叉树，或哈夫曼树。

如下图所示：a、b、c、d四个叶子节点构成的最优二叉树，除了叶子节点，其他3个均为分支节点。根据题目已知n=4代入，得出B选项正确。

编辑于 2019-05-30 14:52:06 回复(1)

牛客992211932号

答案是B：n-1。

分析如下：

二叉树具有以下性质：度为2的节点(双分支节点)数比度为0(叶子节点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知，最优二叉树中只有度为2和0的结点，因此，其节点总数为2n-1。

而其中叶子节点是n，则非叶子节点是2n-1-n=n-1。

发表于 2019-05-29 14:57:53 回复(0)

我是土豆土豆

这里的最优二叉树指的是赫夫曼二叉树，由赫夫曼二叉树的构造可以知道：n个叶子结点的赫夫曼树总共有2n-1个结点，那么分支结点的个数=总结点数 - 叶子结点数 = 2n-1-n = n-1 。至于为什么 “ n个叶子结点的赫夫曼树总共有2n-1个结点 ” 可以去看一下赫夫曼树的构造过程。

发表于 2021-01-27 17:26:41 回复(0)

__sgf__

二叉树具有以下性质：度为2的节点(双分支节点)数比度为0(叶子节点)数正好少1。最优二叉树也就是哈夫曼树。根据最优二叉树(哈夫曼树)的构造过程可知，最优二叉树中只有度为2和0的结点，因此，其节点总数为2n-1。而其中叶子节点是n，则非叶子节点是2n-1-n=n-1。

发表于 2022-02-15 08:13:05 回复(1)

ML_ZDD

我去，看成了结点个数，反手一个C

发表于 2020-02-03 09:51:13 回复(0)

lulutoy

分支节点:非中端节点，即度不为0的节点。叶子节点:终端节点，度为0的节点。除了根节点之外的分支节点，也叫内部节点。

发表于 2022-02-09 15:34:40 回复(0)

YkekeY

最优二叉树也就是哈夫曼树

发表于 2021-04-23 18:06:22 回复(0)

辉小歌

分支结点，即有孩子的结点

发表于 2022-09-12 13:47:31 回复(0)

陳丶奕丶迅

最优二叉树就是哈夫曼树，哈夫曼树中没有度为1的节点

发表于 2022-08-08 11:46:11 回复(0)

hptc

带权二叉树中，带权路径长度最小的二叉树称为哈夫曼树，又称最优二叉树

发表于 2019-09-27 15:34:25 回复(0)

拼命也要幸福

最优二叉树中只有n0和n2而二叉树的性质是n2=n0-1,所以n-1

发表于 2019-09-03 08:03:26 回复(0)

提交观点

问题信息

树

上传者：zsw3

难度：

11条回答 207收藏 3947浏览

含有n个叶子结点的最优二叉树中共有()个分支结点。

问题信息

热门推荐

相关试题