问“完全二叉树”、“严格二叉树”、“完全二叉树”的区别？

EN

Wikipedia yielded

完全二叉树(有时是真正的二叉树、2-树或严格的二叉树)是这样一种树，其中除叶子之外的每个节点都有两个子节点。

所以你没有只有一个子节点的节点。看起来和严格的二叉树是一样的。

以下是来自google的完整/严格二叉树的图像：

​

​

一个完整的二叉树是一个二叉树，其中的每一层，除了可能的最后一层，都是完全填充的，并且所有的节点都尽可能地向左。

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

这是一个完整的二叉树图像，来自google，图像的完整树部分是奖励。

​

​

完美树：

       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 

严格的二叉树和完全的二叉树是有区别的。

1)完全二叉树：高度为h的二叉树恰好包含-1\f25 (2^h)-1 \f25-1\f6元素，称为-1\f25 FULL binary tree -1\f6。(参考: Pg 427，C++大学出版社第二版中的Data Structures，Algorithms and Applications，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