binary-search-tree - 二叉搜索树可以既完整又完整吗？

Question

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

节点是 A E I L N O P R S T U , n=11 个节点。这是我想出的最佳答案:

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

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

Answer 1

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

如果每个节点恰好有 0 或 2 个子节点，则认为二叉树是满的。

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

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

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

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

我希望这有帮助。