关于完全二叉树

Question

完全二叉树中是否可能存在只有一个子节点的节点呢？

这是否可以算作完全二叉树呢？

        23
       /  \
      12  15
     /  \   
    9   11 
   / \    \
  10  5    13  

- user355002

---

不，这不是一棵完全二叉树。节点必须从左到右对齐。如果13号节点是左子节点而不是右子节点，那么你的二叉树将是完全的。 - Petar Minchev

没问题，这没关系。 - Petar Minchev

@ Petar：但是其他答案中写道，所有级别都应该是满的，这意味着除了你提到的原因之外，第三级也不是满的。 - user355002

@matin1234 你说得对。我现在有些心不在焉，刚才没看到第三层还没有满。对此我感到很抱歉。 - Petar Minchev

http://en.wikipedia.org/wiki/Binary_search_tree - Petar Minchev

Answer 1

首先要区分完全二叉树和满二叉树之间的区别。在一个满二叉树中，每个节点都有两个孩子（如果不是叶子节点）或没有孩子（如果是叶子节点）。因此，一个有N层的满二叉树共有2^(N + 1) - 1个节点。但是，如果我们谈论的是完全二叉树，则表示除了最后一层外，每一层都是满的，而最后一层可能不是满的。此外，在完全二叉树中，最后一层的节点必须从左到右填充。

因此，如果你说的是满二叉树，那么只有一个孩子是不可能的。但是，如果你指的是完全二叉树，那么只有一个孩子是可能的。

- Petar Minchev

Answer 2

我认为这是可能的：

     *
    / \
   /   \
  *     x
 / \   / 
*   * *

这是一棵二叉树，除了最后一层可能不完全填充外，每一层都完全填充，且所有节点尽可能地靠左。此外，节点 x 只有一个子节点。

- phimuemue

---

根据定义而定，我希望你能提供一个来源，但是是的，这是一个合理的定义，允许这样做。+1 - Konrad Rudolph

我从vlood的回答中获取了定义。 - phimuemue

Answer 3

引用维基百科：

完全二叉树是一种二叉树，除了最后一层可能不完全填充外，每个层都是完全填充的，并且所有节点尽可能靠左。

这意味着“不”。

- vlood

---

“除了……”后面跟着“没有”是一种无关联的推论，即逻辑谬误。 - Konrad Rudolph

那不应该是“这意味着是吗？”吗？ - Tom Hubbard

这意味着“不” => 提供的示例不是完全二叉树。 - vlood

Answer 4

从其他答案中可以得出以下结论：

完全二叉树是一种二叉树，其中除了可能是最后一层外，每一层都是完全填满的，并且所有节点尽可能靠左。

        23
       /  \
      12  15
     /  \   
    9   11     <- not the last level, but not completely filled!
   / \    \
  10  5    13  <- last level: not completely filled, but that's okay

因此，根据这个定义，这个示例树不完整。

- Thomas