满二叉树的定义

Question

我找到了两个资源，它们好像用两种方式给出了基本定义。 来源1（以及我的一位教授）说：

所有叶子节点都在同一级别，并且所有非叶节点都有两个子节点。 来源2（以及95%的互联网）说：

完全二叉树（有时称为规则二叉树或平衡二叉树）是指树中每个节点都有0或2个子节点的树。

现根据来源2， 成为了二叉树，但不符合来源1的定义，因为叶子节点不在同一级别。

所以通常他们认为像这样的树， 是一个 Full Binary Tree。

我可能听起来很愚蠢，但我很困惑应该相信什么。感谢您的帮助。

- lu5er

---

可能是[“完全二叉树”，“严格二叉树”，“满二叉树”之间的区别？]（https://dev59.com/6Wct5IYBdhLWcg3wFpm1）的重复问题。 - Ted Hopp

@TedHopp，如果您访问http://gateoverflow.in/122126/full-binary-tree-complete-almost-complete-binary-difference并查看`Fig 1`，那就是他们所声称的完全二叉树。我想我的问题不同。 - lu5er

你的教授所说的“满二叉树”，我会称之为“平衡二叉树”。 - Gordon Linoff

@IU5er . . . 不在同一层级，而是在同一层级或层级-1。平衡树是大多数数据库索引的实现方式，一致的高度对性能很重要。 - Gordon Linoff

@GordonLinoff，我明白你的意思。我只是想说第一个定义并不意味着它是一棵平衡树，而是一棵完美的树，正如答案所指出的那样。 - lu5er

Answer 1

有三个主要概念：(1) 满二叉树 (2) 完全二叉树 和 (3) 完美二叉树。正如你所说，满二叉树是一棵所有节点都有度数为2或0的树。然而，完全二叉树是指除了可能的最后一层以外，所有层都从左到右填充的树。最后，完美二叉树是一棵所有叶子节点深度相同的满二叉树。更多信息请参见维基百科页面 我对这里的术语完全的直觉是，给定一个固定数量的节点，完全二叉树是通过从左到右完成每个级别来创建的，可能的例外是最后一个级别，因为节点数可能不总是2^n - 1的形式。

- A. Mashreghi

---

这意味着他们正在混淆全和完美，对吗？ - lu5er

@lU5er 在你的情况下，是的。然而，有些人可能会使用“完整”一词来指代完美，并且使用“几乎完整”来指代我们在这里定义的完整。 - A. Mashreghi

好的，谢谢你的帮助。 :) - lu5er

Answer 2

我认为问题在于，定义的目的是什么？通常，在维基百科中定义“满二叉树”的原因是为了介绍和证明Full Binary Tree Theorem:

具有I个内部节点的满二叉树中节点的总数N为2I+1。

（有关内部节点数量、叶节点数量和总节点数量的等效表述有几种。）该定理的证明并不要求所有叶节点位于同一级别。

您的其中一位教授所描述的是我称之为“完美二叉树”或等效地称之为“满、完全二叉树”。

- Ted Hopp

---

谢谢你的帮助。 :) - lu5er