java - 如何确定平衡或完美平衡的二叉搜索树(仅来自图片)

Question

我不确定如何确定一棵树是平衡的、完美平衡的，还是两者都不是，如果我把它作为图片而不是代码

例如如果我有这棵树我如何检查它是平衡的、完全平衡的还是不平衡的？谁能给我一个完美平衡树的例子？

    [o]
   /   \
 [b]   [p]
   \    / \
  [d]  [m] [r]

很明显，如果树是这样的，我可以看出它是不平衡的:

      [b]
        \
        [d]
         \
          [r]
           \
           [c]

但是，如果它与上面的非常相似，我不知道如何得到它

这是一棵完美平衡且平衡的树:

        [k]
       /   \
      [A]   [p]
            /  \
           [N]  [R]

谁能给我解释一下吗？

Answer 1

一棵完美平衡的树应该是这样的:

       [ R ]
      /     \
    [a]      [b]
   /   \     /  \
 [c]   [d] [e]  [f]

平衡:你可以说它是平衡的，因为每个节点的左右子树的高度相差1或更小(在这种情况下为0)，

完美:您可以说它是完美的，因为节点数等于 2^(n+1)-1，其中 n 是树的高度，在这种情况下 (2^ 3) - 1 = 7

在您的示例中，第一棵树是平衡的，但并不完美，第二棵树既不平衡也不完美。第三个是平衡的，因为每个节点上的左右子树的深度相差1或更少，但它并不完美，因为根据完美树方程，节点数应该是7个，而节点数是5个。

编辑:

关于你最后的评论，你在考试中得到它并不意味着答案在任何意义上都是正确的。完美树的概念与完整性的概念有关，一棵完整的树有时被称为“完美”树，这意味着除了叶子之外每个节点的 child 数是 2 我给你的是一个计算它的方程式.第三棵树是平衡的，因为重要的是每个节点的左右子树的深度，而不是左右子树中子树的数量。在这种情况下，从节点 A 开始，左子树的深度为 0，右子树的深度为 0 -> 0 - 0 = 0，从 P 开始，两个深度均为 1 -> 1 - 1 = 0，从根节点开始，深度为左子树为 1，右子树为 2 -> 2 - 1 = 1 <- 它是平衡的，因为差值应为 1 或更小。

希望对您有所帮助!