二叉搜索树可以既是满的又是完全的吗？

Question

在准备数据结构期中考试时，教授给我们做了去年的测试，其中一个问题涉及将示例树重新排列成完整的二叉搜索树。我尝试了几种不同版本的写出树，但是 Wolfram Mathematica 的这个完整二叉树示例根本没有帮助，因为它也符合完整的定义。教科书将完整的二叉树定义为 n-1 级的树是完美的，在 n 级有一些额外的叶节点，全部左对齐。

节点为 AEILNOPRST U，n=11 个节点。这是我想出的最佳答案：

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

但这适合 WM 树的示例，但不适合书本示例。那么哪个是正确答案呢？

Answer 1

我不完全理解你的困惑在哪里，但我会尽力回答......

如果每个节点都有 0 或 2 个子节点，则二叉树被认为是完整的。

如果除最后一层之外的每一层都已满，并且所有节点都被推到尽可能远的左侧，则认为二叉树是完整的。

因此，如果它符合这两种描述（这是可能的），它就可以同时是完整的。

此外，如果二叉树已满并且所有叶子都位于同一级别，则该二叉树被认为是完美的。

因此，在您上面绘制的示例中，该树是完整的，但并不完美。

我希望这有帮助。

Answer 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

Answer 3

完整的树：
如果每个节点要么是叶子要么是二叉树 T 是满的
恰好拥有两个子节点。

      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

我希望这些有帮助！