一个完整的二叉树和一棵满二叉树有什么不同？

Question

据我理解，完全二叉树中最后一层可以有不完整的节点。那么什么是满二叉树？它们有何区别？

- praxmon

---

一个完全二叉树指的是，在除了最后一层外，其它所有层的节点都有两个子节点；在最后一层上，如果存在节点，那么这些节点都在最左边。而一个满二叉树则是每个节点都有两个子节点，除了叶节点。更多详情可以在谷歌和其他网站上查看相关图片。 - Sandeep Singh

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

Answer 1

完全二叉树（有时称为真二叉树或2-树）是一棵树，其中除了叶子节点以外的每个节点都有两个子节点。

完整二叉树是一棵二叉树，在该树中，除了可能是最后一层之外的每一层都是完全填充的，并且所有节点都尽可能靠左。

这些描述的来源和参考图片如下： http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

- Raevik

---

请注意，实际的“来源”是维基百科，如页面左上角所示。 - chb

Answer 2

完美二叉树： 1. 所有内部节点必须有两个子节点。 2. 所有叶子节点在同一层级上。

Example :

         A1
     B1       B2
  C1    C2  C3  C4

完全二叉树： 除了最后一层，所有层都是完全填充的

示例：

         A1
     B1       B2
  C1    C2  C3  C4
D1  D2 D3 

满二叉树： 每个节点都有0或2个子节点。

例子：

         A1
     B1       B2
  C1    C2  C3  C4
D1  D2 

请更新答案如果同意。

- Tamil.S

---

关于完全二叉树；当你说“除了最后一层可能不完全填充之外完全填充”是指所有节点（包括可能是叶子节点的父节点）都有两个孩子吗？ - ElleryL

Answer 3

一个完全二叉树是任何节点数量下最平衡的树。如果你有恰好(2^n)-1个节点，那么一棵满二叉树就是最平衡的树。 此外，按照惯例，在完全二叉树中，空白的位置保留在树的右侧。 编辑：所谓最平衡，是指给定节点数量时深度最小的树。

- as g