3

为了准备数据结构的期中考试，教授给了我们去年的测试，其中一个问题涉及将示例树重新排列成完整的二叉搜索树。我尝试了几种不同版本的写出树的方法，但是 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 的树示例，但不适合书籍示例。那么哪个是正确答案呢？

4

3 回答 3

11

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

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

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

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

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

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

我希望这有帮助。

于 2010-10-19T14:06:02.307 回答
4

更多示例希望对您有所帮助：

完整的，不完整的：

        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
于 2010-10-21T02:38:34.600 回答
1

满树：如果每个节点是叶子或恰好拥有两个子节点，则二叉树 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

我希望这些是有帮助的！

于 2014-04-21T21:30:55.920 回答