如何使用6个节点制作完整二叉树?

问题描述 投票:2回答:3

我非常了解完整二叉树和完整二叉树。但是无法制作只有6个节点的完整二叉树。

algorithm binary-tree
3个回答
1
投票

答案是No。您不能只使用6个节点创建完整的二叉树。正如Wikipedia中的定义所说:

完整二叉树(有时称为适当或平面二叉树)是一个树,其中每个节点具有0或2个子节点。定义完整二叉树的另一种方法是递归定义。完整的二叉树是:

单个顶点。

一个树,其根节点有两个子树,这两个子树都是完整的二叉树。

我注意到的另一个有趣的属性是,制作完整二叉树所需的节点数总是奇数。


1
投票

在讨论@ vivek_23的答案时,遗憾的是,这是不可能的。有一个美丽的定理说明如下:

定理:任何完整的二叉树都有2L - 1个节点,其中L是树中叶子节点的数量。

这个定理背后的直觉实际上非常简单。想象一下,您将获取一个完整的二叉树并从中删除所有内部节点。您现在拥有一个L单节点完整二叉树的林,每个叶子一个。现在,一次添加一个内部节点。每次你这样做,你将在森林中采取两棵不同的树木,并将它们组合成一棵树,这将树林中的树木数量减少一棵树。这意味着你必须拥有完全L-1个内部节点,因为如果你有更少的东西,你将无法将森林中的所有树木连接在一起,如果你还有更多,你就会用尽树木来结合。

在完整二叉树中存在2L-1个总节点的事实意味着完整二叉树中的节点数总是奇数,因此您无法创建具有6个节点的完整二叉树。但是,您可以使用任意数量的奇数节点创建完整的二叉树 - 您能想出如何证明这一点吗?

希望这可以帮助!


1
投票

另一种看到完整二叉树具有奇数节点的方法:

从完整二叉树(Wikipedia)的定义开始:

每个节点都有0或2个子节点的树。

这意味着子节点的总数是偶数(0 + 2 + 2 + 0 + ... + 2总是偶数)。只有一个节点不是另一个节点的子节点,它是根节点。因此,考虑到该节点,总数变为奇数。

结果,没有具有6个节点的完整二叉树。

© www.soinside.com 2019 - 2024. All rights reserved.