二元搜索树可以是完整的吗?

我不完全理解你的困惑,但我会尽力回答…

如果每个节点正好有0或2个子节点,则认为二进制树已满。

如果每个级别都已满(最后一个除外),并且所有节点都尽可能左推,则认为二进制树是完整的。

因此,如果它符合这两种描述,这是可能的,它可以同时是完整的和完整的。

另外,如果一棵二叉树是满的,并且所有的叶子都在同一水平上,那么它被认为是完美的。

所以在上面的例子中,这棵树是完整的,但并不完美。

我希望这有帮助。

更多的例子可能会有所帮助:

完整,不完整:

        R
      /    \
     L      T
    / \    / \
  I    N   S   U
 / \  /
A  E O   

完整,不完整:

        R
      /    \
     L      T
    / \    / \
  I    N   S   U
      / \
     O   P


        R
      /    \
     L      T
    / \    
  I    N   
 / \  / \
A  E O   P

全树: 如果每个节点都是叶或 只拥有两个子节点。

      O
     / \
    O   O
   / \ / \
  O  O O  O
    / \
   O   O

整棵树但不完整

完整树: 具有n个级别的二叉树t如果全部 除了最后一层可能已经满了, 最后一层的所有节点都在左侧。

       O
      / \
     O   O
    /
   O

完整的树,但不完整

同样,另一个例子

      O
     / \
    O   O
   / \ / \
  O  O O  O
 /\ /
O O O

希望这些有用!