平衡二叉树和完全二叉树有什么区别？说每棵完全二叉树都是平衡树
是真的吗？
反过来呢？
问问题
23263 次
4 回答
33
平衡二叉树是每个节点的两个子树的深度相差不超过 1 的二叉树。
完全二叉树是除最后一层外的所有层都被完全填满并且最后一层的所有叶子都在左侧的二叉树。
下面是平衡二叉树，但不是完全二叉树。每个完整的二叉树都是平衡的，但不是相反。
1
1 1
1 1 1
1
正如暗示的那样，在一棵完整的树中，水平差总是不超过 1，所以它总是平衡的。
于 2013-02-07T17:00:21.470 回答
11
由于这发展成为关于完美、平衡、完整和完整的进一步问题 - 这里有一个答案也可以澄清这些问题。假设一棵二叉树，
平衡：每个节点的左右子树的高度相差不超过 1。
Full：除叶节点外的所有节点都有 2 个子节点
完成：
- 除了最后一层之前的所有节点都必须有 2 个子节点。
- 最后一层的所有节点都尽量靠左。
概括：
- 完整的树：必须平衡；可以满
- 满树：可以平衡；可以完整
- 平衡树：可以完整；可以满
例子：
完全和平衡- 所有节点都有 0 或 2 个子节点
level 3 - level 2 <= 1，, （不完整- 最后一级节点尽可能远离）1 --- LEVEL 0 / \ 1 1 --- LEVEL 1 /\ /\ 1 1 1 1 --- LEVEL 2 - /\ - - 1 1 --- LEVEL 3 x x - -完整、平衡和完整- 所有节点都有 0 或 2 个子
3 - 2 <= 1节点，最后一级节点尽可能靠左：1 --- LEVEL 0 / \ 1 1 --- LEVEL 1 /\ /\ 1 1 1 1 --- LEVEL 2 /\ - - - 1 1 --- LEVEL 3 - -完整- 所有节点都有 0 或 2 个子节点（不平衡-
3 - 1 > 1，不完整- 级别 1 有一个节点有 0 个子节点）：1 --- LEVEL 0 / \ 1 1 --- LEVEL 1 / \ - 1 1 --- LEVEL 2 / \ - x x 1 1 --- LEVEL 3 - -完整且平衡- 最后一级节点尽可能靠左，
3 - 3 <= 1（不完整- 有一个 2 级节点有 1 个子节点）：1 --- LEVEL 0 / \ 1 1 --- LEVEL 1 /\ /\ 1 1 1 1 --- LEVEL 2 /\ /\ /\ /x 1 1 1 11 1 1 --- LEVEL 3 - - - -- - -平衡-
3 - 3 <= 1，（未满- 有一个有 1 个子节点的 2 级节点，不完整- 最后一级节点不在最左边）1 --- LEVEL 0 / \ 1 1 --- LEVEL 1 /\ /\ 1 1 1 1 --- LEVEL 2 /\ /\ /x /\ 1 11 11 1 1 --- LEVEL 3 - -- -- x - -
- 完美：所有内部节点都有两个孩子，所有叶子都具有相同的深度。
以上例子都不是完美的
于 2021-02-03T03:30:28.497 回答
1
平衡树：平衡树是二叉树的形式，其中每个节点的左子树高度和右子树高度之差最多为k，其中 k 将是平衡因子。如果这个平衡因子为 0，那么该树将被称为完全平衡树。
示例：
8
6 1
3 9 1
这棵树是平衡因子为 1 的平衡树，因为每个节点的子树的高度差异为 0 或 1。
完全二叉树：如果除了叶子之外的每一层都被完全填满，则称一棵树是完整的。并且叶子节点上的任何新插入都将从左到右，这意味着左侧的叶子将首先被完全填充。
示例：8
6 1
3 5 4 1
现在这棵树是完整的二叉树，如果必须进行任何新的插入，那么它应该在左边的叶子下面，在这个例子中是 3。一旦 3 被左右孩子填充，那么 5 将成为新插入的下一个叶子。
于 2020-03-30T06:05:27.303 回答
0
当一棵高度为 h 的二叉树的所有叶子都在 h 层并且每个父节点正好有两个孩子时，就说树是满的
当除最后一层之外的所有层都包含尽可能多的节点时，树被认为是完整的，并且最后一层的节点从左到紧填充。（不完整，但完整）
当二叉树中的每个节点都有两个高度完全相同的子树时，这棵树被称为完全平衡的
完全平衡的树已满
如果节点的子树相差不超过一个，则树是高度平衡的或简单平衡的
于 2018-06-17T16:34:29.653 回答