haskell - 检查二叉树是否完整 - haskell

Question

我有一个二叉树：

data Btree a = Leaf a | Unary (Btree a) a | Binary (Btree a) a (Btree a) deriving Show

以及一些可以使用的示例：

ex1 = Binary (Binary (Leaf 0) 1 (Leaf 2)) 3 (Unary (Leaf 4) 5)
ex2 = Binary (Unary (Leaf 1) 2) 3 (Binary (Leaf 4) 5 (Leaf 10))
ex3 = Binary (Binary (Leaf (0,"a"))(1,"z")(Leaf (2,"x")))(3,"y")(Binary (Leaf (4,"b"))(5,"c")(Leaf (6,"d")))

我需要找出这棵树是否完整，如果根与任何叶子之间的距离始终相同，直到 1，那么一棵树是完整的，所有最深的叶子都位于其他叶子的左侧，并且有最多是一个内部节点，其中一元节点应位于倒数第二级。

这就是我到目前为止所拥有的

complete :: Btree a -> Bool
complete x = fst $ go x where
  go (Leaf _) = (True, 0)
  go (Unary left _) = (leftTrue, 1 + leftCount) where 
    (leftTrue, leftCount) = go left
  go (Binary left _ right) = (leftTrue && rightTrue &&
                            leftCount == rightCount,
                            1 + leftCount + rightCount) where
    (leftTrue, leftCount) = go left
    (rightTrue, rightCount) = go right

ex1 & ex3 应该返回 true，但只有 ex3 是。我相信一元部分是问题所在。

标签： haskellbinary-tree

Answer 1

这个答案依赖于以下Unary部分的代码更改：(leftTrue, 1 + leftCount)-> (False, 1 + leftCount)。

您的解决方案的主体是go功能。如果左右子树完全平衡以及子树有多少节点，则该函数返回子树。所有深度都相同，就像在 ex3 中一样。但是如果你没有 2^n-1 个节点和 2^(n-1) 个叶子，就不可能构建那棵树。在您的问题的描述中，允许表示任何节点数的不平衡很少。Ex1 满足 ex2 不满足的规则。根据您的定义，Ex3 也是完整的。

在代码下，我对示例进行了 ASCII 艺术。

我的解决方案不计算子树的数量节点。它计算最大和最小深度，因为它允许我揭示树的任何级别的非法不平衡。布尔值表示子树是否满足完整树的条件。它检查：

1. 差异最多相同
2. 左子树的最小深度大于或等于右树的最大深度。

上面的检查还包含关于倒数第二级的一个一元节点的条件。

你能猜出这个地方属于什么......吗？

data Btree a = Leaf a | Unary (Btree a) a | Binary (Btree a) a (Btree a) deriving Show

ex1 = Binary (Binary (Leaf 0) 1 (Leaf 2)) 3 (Unary (Leaf 4) 5)
ex2 = Binary (Unary (Leaf 1) 2) 3 (Binary (Leaf 4) 5 (Leaf 10))
ex3 = Binary (Binary (Leaf (0,"a"))(1,"z")(Leaf (2,"x")))(3,"y")(Binary (Leaf (4,"b"))(5,"c")(Leaf (6,"d")))

complete :: Btree a -> Bool
complete x = fst $ go x

go :: Btree a -> (Bool,(Int,Int))
go (Leaf _) = (True, (0, 0))
go (Unary left _) = (leftMaxDepth == 0, (1 + leftMaxDepth, 0)) where 
  (leftIs, (leftMaxDepth, leftMinDepth)) = go left
go (Binary left _ right) =
  ( leftIs && rightIs
    ...
    , (1+newMaxDepth
    , 1+newMinDepth )) where
      newMaxDepth = max leftMaxDepth rightMaxDepth
      newMinDepth = min leftMinDepth rightMinDepth
      (leftIs, (leftMaxDepth, leftMinDepth)) = go left
      (rightIs, (rightMaxDepth, rightMinDepth)) = go right

&& leftMinDepth >= rightMaxDepth && newMaxDepth - newMinDepth <= 1

例 1：真

      3
     / \
    /   \
   1     5
  / \   /
 0   2 4

深度：[3,3,3,2]

例 2：错误

      3
     / \
    /   \
   2     5
  /     / \
 1     4   10

深度：[3,2,3,3]

例 3：是的

             (3,"y")
             /     \
           /         \
    (1,"z")          (5,"c")
    /    \            /    \ 
(0,"a")  (2,"x")  (4,"b")  (6,"d")

深度：[3,3,3,3]