我对以下树的术语感到困惑，我一直在研究树，但无法区分这些树：
a) 完全二叉树
b) 严格二叉树
c) 全二叉树
请帮助我区分这些树。在数据结构中何时何地使用这些树？
问问题
183771 次
12 回答
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
于 2012-09-10T21:35:27.770 回答
74
一棵完整的二叉树（有时是正确的二叉树或二叉树或严格的二叉树）是一棵树，其中除了叶子之外的每个节点都有两个孩子。
所以你没有只有 1 个孩子的节点。看起来和严格的二叉树一样。
这是来自谷歌的完整/严格二叉树的图像：
完全二叉树是一棵二叉树，其中除了可能的最后一层外，每一层都被完全填满，并且所有节点都尽可能靠左。
这似乎意味着一棵平衡的树。
这是一个完整的二叉树的图像，来自谷歌，图像的完整树部分是奖励。
于 2012-09-10T21:28:47.653 回答
53
严格的二叉树和完整的二叉树是有区别的。
1) 全二叉树：高度为 h 且恰好包含 (2^h)-1 个元素的二叉树称为全二叉树。（参考：第 427 页，C++ 中的数据结构、算法和应用[大学出版社]，Sartaj Sahni 第二版）。
或者换句话说
在完整的二叉树中，每个节点恰好有 0 或 2 个子节点，并且所有叶节点都在同一级别。
例如：以下是完整的二叉树：
18
/ \
15 30
/ \ / \
40 50 100 40
2) 严格二叉树：每个节点恰好有 0 或 2 个子节点。
例如：下面是一个严格的二叉树：
18
/ \
15 30
/ \
40 50
我认为完全二叉树的定义没有混淆，仍然为了帖子的完整性，我想告诉完全二叉树是什么。
3）完整的二叉树：如果所有级别都完全填充，除了可能的最后一层并且最后一层的所有键都尽可能离开，则二叉树是完整的二叉树。
例如：以下是完整的二叉树：
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
注意：下面也是一个完全二叉树：
18
/ \
15 30
/ \ / \
40 50 100 40
于 2015-08-18T05:21:50.270 回答
10
免责声明-一些定义的主要来源是维基百科，欢迎提出任何改进我的答案的建议。
尽管这篇文章有一个公认的答案并且是一个很好的答案，但我仍然感到困惑，并想对这些术语之间的区别进行更多澄清。
(1) FULL BINARY TREE - 完全二叉树是一种二叉树，其中除叶子之外的每个节点都有两个孩子。这也称为严格二叉树。
以上两个是完全或严格二叉树的例子。
(2)完全二叉树-现在，完全二叉树的定义非常模糊，它指出：- 完全二叉树是一棵二叉树，其中除了可能的最后一层之外，每一层都被完全填满，所有节点都为尽可能左。它可以有 1 到 2h 个节点，尽可能在最后一层 h
注意斜体字。
歧义在于斜体字，“除了可能最后一个”，这意味着最后一个级别也可能被完全填充，即不需要总是满足这个例外。如果异常不成立，那么它就像我发布的第二张图片一样，也可以称为完美二叉树。因此，一棵完美的二叉树也是完整且完整的，但反之则不然，我需要说明的另一个定义很清楚：
几乎完全二叉树 -当完全二叉树定义中的异常成立时，它被称为几乎完全二叉树或几乎完全二叉树。它本身只是一种完全二叉树，但需要单独定义以使其更加明确。
所以一个几乎完全的二叉树看起来像这样，你可以在图像中看到节点尽可能地靠左所以它更像是完全二叉树的一个子集，更严格地说每个几乎完全的二叉树都是一个完全二叉树树，但反之亦然。：
于 2014-09-28T19:36:11.367 回答
6
从以上答案得出结论，这是完整/严格，完整和完美二叉树之间的确切区别
完全/严格二叉树：- 除了叶节点之外的每个节点都有两个孩子
完全二叉树：- 除了最后一层之外的每一层都被完全填充，所有节点都是左对齐的。
完美二叉树：- 除了叶节点之外的每个节点都有两个子节点，并且每一层（最后一层）都被完全填满。
于 2015-01-31T13:59:56.127 回答
3
考虑一棵二叉树，其节点以树的方式绘制。现在开始从上到下和从左到右对节点进行编号。一棵完整的树具有以下属性：
如果 n 有子节点，则编号小于 n 的所有节点都有两个子节点。
如果 n 有一个孩子，它必须是左孩子，并且所有小于 n 的节点都有两个孩子。此外，编号大于 n 的节点都没有子节点。
如果 n 没有子节点，则编号大于 n 的节点都没有子节点。
一个完整的二叉树可以用来表示一个堆。它可以很容易地在连续的内存中表示，没有间隙（即所有数组元素都被使用，除了最后可能存在的任何空间）。
于 2012-09-10T21:33:19.193 回答
2
完全二叉树是一棵完全二叉树，但不可能反转，如果二叉树的深度为n，则否。完整二叉树中的节点数为 ( 2^n-1 )。在二叉树中它没有必要有两个孩子，但在完整的二叉树中，每个节点都没有或有两个孩子。
于 2012-10-16T19:13:54.000 回答
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 的子节点比 k 多，即最后一层 (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
好吧，很抱歉我不能发布图片，因为我没有 10 声望。希望这对您和其他人有所帮助！
于 2015-08-18T06:41:26.773 回答
2
根据我对二叉树的有限经验，我认为：
- 严格二叉树：除叶子节点外的每个节点都有两个孩子或只有一个根节点。
- 完全二叉树：严格（或完全）包含2^(H+1) -1 个节点的 H 的二叉树，很明显每个级别都有最多的节点。或者简而言之，所有叶节点都处于同一级别的严格二叉树。
- 完全二叉树：它是一棵二叉树，其中除了可能的最后一层之外，每一层都被完全填满，并且所有节点都尽可能地靠左。
于 2017-01-05T18:14:00.093 回答
1
让我们考虑一个高度为“h”的二叉树。如果所有叶子都出现在高度“h”或“h-1”且序列中没有任何缺失的数字，则二叉树称为完全二叉树。
1
/ \
2 3
/ \
4 5
它是一棵完全二叉树。
1
/ \
2 3
/ /
4 6
它不是完整的二叉树，因为序列中缺少数字 5 的节点
于 2018-11-27T08:53:46.150 回答
0
如果每个节点都有 0 或 2 个孩子，则满二叉树是满的。叶节点的完整二进制数是内部节点数加 1 L=l+1
于 2019-12-05T08:10:24.463 回答
0
完全二叉树：所有级别都完全填充，除了最低级别和一个主要的事情是所有叶子元素都必须有左子元素。严格二叉树：在这棵树中，每个非叶节点都没有子节点，即既没有左也没有右。完全二叉树：每个节点要么有零个孩子，要么有两个孩子（从不有单个孩子）。
于 2020-11-04T07:00:26.067 回答