检查Scala中是否平衡了二叉树

Question

我在Scala中使用case类和trait定义了一个二叉树结构.我这样做了:

sealed trait Tree[+T]

case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
case class Leaf[A](v: A) extends Tree[A]
case object Empty extends Tree[Nothing]

如果给定一个Tree实例,我想检查实例是否平衡,其中balance的定义是右边元素的数量等于左边元素的数量.

我尝试了以下方法(使用累加器模式)来获得我想要的东西:

sealed trait Tree[+T]

case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
case class Leaf[A](v: A) extends Tree[A]
case object Empty extends Tree[Nothing]

def isBalanced[A](tree: Tree[A]) = {
  def inner(tree: Tree[A], acc: (Int, Int)): Boolean = tree match {
    case n: Node[A] => inner(n.l, (acc._1 + 1, acc._2)) && inner(n.r, (acc._1, acc._2 + 1))
    case l: Leaf[A] => inner(tree, acc)
    case Empty      => acc._1 == acc._2 
  }

  inner(tree, (0, 0)) 
}

val node: Node[Int] = Node(1, Node(2, Leaf(3), Leaf(4)), Node(5, Leaf(6), Leaf(7)))
isBalanced[Int](node)

这会进入一个无限循环,我很确定我的逻辑犯了一些愚蠢的错误.我对自己犯错误的地方并不自信.

Answer 1

你的错误在于case Leaf:它应该是在调用inner(Empty, acc).你拥有它的方式,它只是不断调用自己 - 因此无限循环.

这将修复无限循环,但实现仍然是错误的:基本上,你继续下降左分支,递增左边acc,直到你击中叶子.然后你比较左右(仍然是零),并返回.除了树之外,此实现将始终返回false,这只是一个叶子节点.

此外,您对平衡树的定义是错误的.例如,像这样:

                     A
                    / \
                   B   E
                  /   / \
                 C   F  G
                /
               D

匹配定义(左侧和右侧有三个元素),但不是真正平衡.
另一方面,这样的事情:

                    A
                   / 
                  B  

与定义不符,但实际上是平衡的.

平衡树的正确定义是一个,其中左右子树都是平衡的,并且它们的高度最多相差一个.

考虑到这一点,我们可以像这样编写一个正确的实现(如果它是平衡的,它返回树的高度,否则返回-1):

   def balanced(root: Tree[_]): Int = root match {
      case Empty => 0
      case Leaf(_) => 1
      case Node(_, left, right) => 
        val l = balanced(left)
        val r = balanced(right)
        if (l < 0 || r < 0 || abs(l - r) > 1) -1 else (l max r) + 1
    }