"完全二叉树","严格二叉树","完整二叉树"之间的区别？

Question

我对以下树的术语感到困惑,我一直在研究树,我无法区分这些树:

a)完整的二叉树

b)严格的二叉树

c)完整的二叉树

请帮我区分这些树.在数据结构中何时何地使用这些树？

Answer 1

完美树:

       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 

Answer 2

维基百科屈服了

完整的二叉树(有时是适当的二叉树或2树或严格的二叉树)是一棵树,其中叶子以外的每个节点都有两个子节点.

所以你没有只有1个孩子的节点.看起来与严格的二叉树相同.

这是来自谷歌的完整/严格二叉树的图像:

完整的二叉树是一个二叉树,其中除了可能是最后一个级别之外的每个级别都被完全填充,并且所有节点都尽可能地离开.

它似乎意味着一棵平衡的树.

这是一个完整的二叉树的图像,从谷歌,完整的树部分图像是奖金.

Answer 3

STRICT和FULL BINARY TREE之间存在差异.

1)FULL BINARY TREE:高度为h的二叉树,包含精确的(2 ^ h)-1个元素,称为完整二叉树.(参考:Pg 427,C++中的数据结构,算法和应用 [大学出版社],Sartaj Sahni的第二版).

或换句话说

在FULL BINARY TREE中,每个节点都有正好0或2个子节点,并且所有叶节点都在同一级别上.

例如:以下是完整的二进制树:

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40 

2)严格二进制树:每个节点正好有0或2个孩子.

例如:以下是STRICT BINARY TREE:

         18
       /     \   
     15       30    
    /  \          
  40    50

我认为在完整二进制树的定义中没有混淆,仍然是为了完整的帖子我想告诉完整的二叉树是什么.

3)完成二进制树:二进制树是完整的二进制树,如果所有级别都被完全填充,除了可能的最后一级,最后一级有尽可能的所有键.

例如:以下是COMPLETE BINARY TREE:

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9 

注意:以下也是完整的二叉树:

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40 

Answer 4

免责声明 - 一些定义的主要来源是维基百科,欢迎提出改进我的答案的任何建议.

虽然这篇文章有一个公认的答案并且是一个很好的答案,但我仍然感到困惑,并希望对这些术语之间的差异进行更多澄清.

(1)完整二叉树 - 完整二叉树是一个二叉树,其中叶子以外的每个节点都有两个子节点.这也称为严格二叉树.

以上两个是完整或严格二叉树的示例.

(2)完全二叉树的树形现在,完全二叉树的定义是很模糊的,它规定: -一个完整的二叉树是二叉树中,每一个级别,除了可能的最后,完全填充,并且所有节点都为尽可能远的地方.它可以在最后一级h尽可能地保留1到2h节点

注意斜体的线条.

模糊性在于斜体线,"除了可能是最后一个",这意味着最后一个级别也可以完全填充,即不必总是满足该异常.如果异常不成立,那么它就像我发布的第二个图像一样,也可以称为完美的二叉树.因此,一个完美的二叉树也是完整和完整的,但反之亦然,我需要说明的另一个定义是明确的:

几乎完成二进制树 - 当完整二叉树的定义中的异常成立时,它被称为几乎完整的二叉树或几乎完整的二叉树.它只是一种完整的二叉树本身,但需要单独的定义才能使其更加明确.

所以一个几乎完整的二叉树看起来像这样,你可以在图像中看到节点尽可能地离开,所以它更像是完整二叉树的一个子集,更严格地说每个几乎完整的二叉树都是完整的二进制树树,但反之亦然.:

Answer 5

从上面的答案得出结论,这是完整/严格,完整和完美的二叉树之间的确切区别

1. 完整/严格二叉树: - 除叶节点外的每个节点都有两个子节点

2. 完整二叉树: - 除最后一级之外的每个级别都已完全填充,并且所有节点都是左对齐的.

3. 完美的二叉树: - 除叶子节点外的每个节点都有两个子节点,每个级别(最后一级)也完全填满.