我对以下树的术语感到困惑，我一直在研究树，但是我无法区分这些树：
a) 完全二叉树
b) 严格二叉树
c) 满二叉树
请帮助我区分这些树。 这些树在数据结构中何时以及何地使用？
---我对下列树的术语感到困惑，我一直学习树，但我无法区分以下树：
a) 完全二叉树
b) 严格二叉树
c) 满二叉树
请帮我区分这些树。这些树在数据结构中何时和哪里使用？
"完全二叉树"、"严格二叉树"和"满二叉树"之间的区别是什么？（注：这是一个提问标题，不需要回答）
87
我对下列树的术语感到困惑，我一直学习树，但我无法区分以下树：
a) 完全二叉树
b) 严格二叉树
c) 满二叉树
请帮我区分这些树。这些树在数据结构中何时和哪里使用？
- kTiwari
4
2http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees 这个链接没有回答你的问题吗？ - rodion
8不是的，这些中有很多混淆。 - kTiwari
1严格二叉树：每个节点最多只能有两个子节点或者没有子节点。 - vikkyhacks
这是关于完全二叉树和满二叉树的一个很好的例子：https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html - theshubhagrwl
13个回答
91
完美二叉树：
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ / \ / \ / \
x x x x x x x x
完全二叉树：
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ /
x x x
严格/完整树：
x
/ \
/ \
x x
/ \
x x
/ \
x x
- japreiss
2
4您的意思是“完美二叉树”指的是原帖中提到的满二叉树吗？ - RBT
4完美二叉树既是严格/满二叉树，也是完全二叉树，但反之则不一定成立。 - neo
74
满二叉树（有时也称作 proper 二叉树、2-树或严格二叉树）是一种每个非叶子节点都有两个孩子的二叉树。
因此，没有只有 1 个孩子的节点。看起来与严格二叉树相同。
下面是一个来自谷歌的满/严格二叉树示例图：
完全二叉树是一棵二叉树，其中除了可能是最后一层外，每个层上的节点数都达到了最大值，并且所有节点都尽可能靠左。
它似乎意味着一棵平衡树。
下面是一个来自谷歌的完全二叉树示例图，其中满树部分是额外的：
- Sam I am says Reinstate Monica
7
35你的完整树示例也满足完全二叉树的标准，因此差异显然模糊了，在我看来，你可能想举一个既是完整树但不是完全二叉树的例子，反之亦然，这将使答案更加完整 :) - 0decimal0
2此外，虽然所有完全树都是平衡树，但并非所有平衡树都是完全树。 - sfarbota
1每个级别完全填充是什么意思？ - lolololol ol
2@lololololol 的意思是该层可能存在的所有节点都已经出现。 - Sam I am says Reinstate Monica
1在完全二叉树上，“所有节点尽可能靠左”这个概念有点令人困惑。我认为这意味着在最后一行，如果你从左到右进行层次遍历，就不会有空隙。一旦你到达倒数第二层的一个没有左右子节点的节点，你就知道那是最后一个节点了。 - Joel Cunningham
显示剩余2条评论
53
在STRICT BINARY TREE和FULL BINARY TREE之间存在差异。
1) FULL BINARY TREE: 高度为h的二叉树，恰好包含(2^h)-1个元素，称为完全二叉树。 (参考: Sartaj Sahni所著《数据结构、算法与C++应用》第二版，第427页)。
或者说
在完全二叉树中，每个节点恰好有0或2个孩子，并且所有叶子节点都在同一层上。
以下是完全二叉树的示例：
a.
18
/ \
15 30
/ \ / \
40 50 100 40
b.
18
/ \
15 30
2) 严格二叉树：每个节点恰好有0或2个子节点。
以下是严格二叉树的示例：
a.
18
/ \
15 30
/ \
40 50
18
/ \
15 30
/ \
40 50
/ \
20 45
我认为完全二叉树的定义没有什么混淆，但为了让文章更加完整，我想解释一下什么是完全二叉树。
3) 完全二叉树：如果所有层级都被填满，除了最后一层，且最后一层的所有键都尽可能地靠左，则称这棵二叉树为完全二叉树。
例如：以下是一棵完全二叉树：
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
注意：以下是完全二叉树，也是按定义来说的满二叉树：
18
/ \
15 30
/ \ / \
40 50 100 40
结论 因此，一个完全二叉树也是一棵满二叉树。但反过来则不成立。
- Saurabh Bhatia
4
你能提供完整二叉树定义的来源吗？这与维基百科上引用NIST的定义[https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees]相矛盾。 - Calvin Li
@CalvinLi 在“完全二叉树”的定义中提到了源。这是一个 PDF 文件的链接（PDF 的第 447 页）- https://o6ucs.files.wordpress.com/2012/10/data-structures-algorithms-and-applications-in-c-by-sartraj-sahani.pdf。 - Saurabh Bhatia
@SaurabhBhatia，最后一种表示方法也适用于完全二叉树。如果我错了，请纠正我。如何让一个表示方法适用于不同的变体？ - Rose
@Rose 是的，最后一种表示方法也适用于满二叉树。因此，我们也可以说满二叉树也是完全二叉树。但反过来则不成立。希望这样清楚了。 - Saurabh Bhatia
10
免责声明- 一些定义的主要来源是维基百科，欢迎提出改进建议。
虽然这篇文章有一个被接受的答案，而且很好，但我仍然感到困惑，想要添加更多的澄清，关于这些术语之间的区别。
(1)完全二叉树- 完全二叉树是一种二叉树，其中除了叶节点外的每个节点都有两个子节点。这也称为严格二叉树。
上面两个是完全或严格二叉树的例子。
(2) 完美二叉树- 现在，完美二叉树的定义相当模糊，它陈述：- 完美二叉树是一棵二叉树，在每个级别上，除了最后一个级别可能不完全填充外，所有节点尽可能靠左对齐。 它可以在最后一个级别 h 上最左边拥有1和2h个节点
注意斜体行中的行。
模糊之处在于斜体行中的“除了最后一个”，这意味着最后一级也可能完全填充，即这个例外并不总是成立。如果该例外不成立，则与我发布的第二个图像完全相同，也可以称为完美二叉树。因此，完美二叉树也是完全和严格的，但反之不然，这将通过我需要陈述的另一个定义变得更清楚：
几乎完全二叉树- 当完全二叉树的定义中的例外情况成立时，它被称为几乎完全二叉树或近似完全二叉树。它只是完全二叉树的一种类型，但需要一个单独的定义来使其更加明确。
因此，一个几乎完全的二叉树看起来像这样。你可以在图片中看到节点尽可能靠左，所以它更像是完全二叉树的子集，更加严谨地说，每个几乎完全的二叉树都是一个完全二叉树，但反之则不成立。
- 0decimal0
6
从以上答案中可以得出，完全二叉树、严格二叉树和满二叉树之间的确切区别如下：
1. 严格二叉树：除了叶节点，每个节点都有两个子节点。 2. 完全二叉树：除了最后一层，每一层都被完全填充，并且所有节点都靠左对齐。 3. 满二叉树：除了叶节点，每个节点都有两个子节点，并且每一层（包括最后一层）都被完全填充。
1. 严格二叉树：除了叶节点，每个节点都有两个子节点。 2. 完全二叉树：除了最后一层，每一层都被完全填充，并且所有节点都靠左对齐。 3. 满二叉树：除了叶节点，每个节点都有两个子节点，并且每一层（包括最后一层）都被完全填充。
- pantech
3
考虑一个二叉树，其节点以树的形式绘制。现在从上到下，从左到右开始对节点进行编号。完全树具有以下特性：
如果一个节点n有孩子，则比n编号小的所有节点都有两个孩子。
如果n有一个孩子，则它必须是左孩子，而且比n编号小的所有节点都有两个孩子。此外，没有编号大于n的节点具有孩子。
如果n没有孩子，则没有编号大于n的节点具有孩子。
完全二叉树可用于表示堆。它可以轻松地在连续的内存中表示，没有间隙（即所有数组元素都被使用，除了可能存在的任何空间）。
如果一个节点n有孩子，则比n编号小的所有节点都有两个孩子。
如果n有一个孩子，则它必须是左孩子，而且比n编号小的所有节点都有两个孩子。此外，没有编号大于n的节点具有孩子。
如果n没有孩子，则没有编号大于n的节点具有孩子。
完全二叉树可用于表示堆。它可以轻松地在连续的内存中表示，没有间隙（即所有数组元素都被使用，除了可能存在的任何空间）。
- Craig Wright
2
根据我的有限经验，我认为二叉树有以下几种类型：
- 严格二叉树：除了叶子节点外，每个节点都有两个孩子或只有一个根节点。
- 满二叉树：高度为H的二叉树恰好包含2^(H+1)-1个节点，每一层的节点数最多。简而言之，所有叶子节点都在同一层的严格二叉树。
- 完全二叉树：它是一棵二叉树，在除了可能是最后一层之外的每一层上都是完全填充的，并且所有节点尽可能地向左对齐。
- BertKing
3
2你对完全二叉树的定义是错误的，那是完美二叉树的定义。满二叉树与严格二叉树是同义词。
（来源：参见严格二叉树：http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html）
（来源：参见完美二叉树：https://www.slideshare.net/ajaykumarc137151/difference-between-complete-binary-tree） - Keego
1哦，我的天啊，刚才我有点困惑，但我会确保这一点。非常感谢。 - BertKing
1没问题 :) 请参考下面@Lotus的答案(https://dev59.com/6Wct5IYBdhLWcg3wFpm1#28252424)，他解决了这个问题。我只是建议修改你的答案以反映这一点。 - Keego
2
完全二叉树是一种特殊的二叉树，而反过来则不一定成立。如果一个二叉树的深度为n，则完全二叉树的节点数为（2^n-1）。二叉树不一定每个节点都有两个子节点，但在完全二叉树中，每个节点要么没有子节点，要么有两个子节点。
- Raghvendra Singh Thakur
2
1你不能严格地说“反转不可能”，事实上，在被接受的答案中完全树的例子就违反了你的这个假设...你应该更准确地说可能或不可能。 - 0decimal0
1如果二叉树的深度为n，则完全二叉树中节点的数量为(2^n-1)。但是，完全二叉树的定义是每个节点要么是叶子节点，要么有两个子节点。因此，最大可能的子节点数为(2^n-1)，但实际上可能会少于这个数。 - mrida
2
首先，了解二叉树本身非常重要，才能理解不同类型的二叉树。
如果以下条件均满足，则该树是二叉树：
- 它有一个根节点，可能没有任何子节点（0个子节点，NULL树）
- 根节点可以有1或2个子节点。每个这样的节点本身都形成了一个二叉树
- 子节点数可以是0、1、2......但不超过2个
- 从根到每个其他节点都存在唯一的路径
例如：
X
/ \
X X
/ \
X X
关于您所询问的术语：
如果且仅如果一个二叉树是完全二叉树（对于高度为h的二叉树，我们将根节点视为0），则满足以下条件：
从第0层到第h-1层代表高度为h-1的完全二叉树
-第h-1层中的一个或多个节点可能具有0个或1个子节点
如果j、k是第h-1层的节点，则当且仅当j在k的左侧时，j具有更多的子节点，即最后一层（h）可以缺少叶节点，但存在的节点必须向左移动
例如：
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
如果且仅如果一个二叉树满足以下条件，则该二叉树是严格的二叉树：
每个节点恰好有两个子节点或没有子节点。
例如：
X
/ \
X X
/ \
X X
/ \ / \
X X X X
如果且仅如果二叉树满足以下条件，则为完全二叉树：
每个非叶子节点恰好有两个子节点
所有叶子节点都在同一层级上
示例：
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
你还应该知道什么是完美二叉树？
当且仅当以下条件成立时，二叉树才是完美二叉树：
- 是一棵满二叉树
- 所有叶节点都在同一层级上
例如：
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
很抱歉，我因为声望不足无法发布图片。 希望这个回答对你和其他人有所帮助！
- user2376267
1
让我们考虑一棵高度为'h'的二叉树。如果所有叶子节点都出现在高度为'h'或'h-1'的位置上，并且序列中没有任何缺失数字，则称该二叉树为完全二叉树。
1
/ \
2 3
/ \
4 5
它是一棵完全二叉树。
1
/ \
2 3
/ /
4 6
由于序列中缺少数字为5的节点，它不是一棵完全二叉树。
- Ravi varma Indukuri
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接