algorithm - 在 Scala 中合并二叉树

Question

它说 here :

The easiest way to merge two binary trees is to take iterate down the left child of one tree until reaching a node without a left child. Then add the other tree's root as the left child.

简单。在“普通代码”中，我会这样写:

if(!left.isEmpty)
  thisFuncAgain()
else left = otherSet; return this

但是，我无法想象这在 Scala 中会是什么样子。这是我的一些想法。此函数将放在 BinaryTree 类中:

def merg(that: BinaryTree): BinaryTree = {
  if(leftNode.isEmpty) leftNode += that; leftNode
  else merg(leftNode)
}

但是，重新分配给 val 是不可能的。我可以为左节点递归此函数，但当它返回时，将不会考虑最后一个节点之前的元素。

关于我如何想到这个的任何提示？ 我是 Scala 的初学者，我真的被困在这上面。

Answer 1

这取决于 BinaryTree 类的外观，您不会透露太多。完全可以有一个可变的 BinaryTree，您可以在其中修改节点。但这里是您的算法的一个实现，带有典型的不可变 BinaryTree

sealed trait BinaryTree[A] {
  def merge(that: BinaryTree[A]): BinaryTree[A]
}
case object Empty extends BinaryTree[Nothing] {
  def merge(that: BinaryTree[A]: BinaryTree[A] = that
}
case class Node(left: BinaryTree[A], value: A, right: BinaryTree[A]) 
extends BinaryTree[A] {
  def merge(that: BinaryTree[A]): BinaryTree[A] =
   Node(left.merge(that), value, right)
}

它不修改 this，它返回 BinaryTree 的新实例，并保持 this 不变。它的成本并不高，因为 that 的所有节点和 this 的大部分节点将在两棵树之间共享。唯一需要重新创建的节点位于此节点的根节点和最左边的节点之间。您获得不变性的好处，最重要的是它可以自由共享，您永远不需要制作防御性副本。

另一方面，很有可能使左右子节点 var 而不是 val 并合并改变原始树。

---

您在评论中声明它只返回要合并的树。它不是。我刚刚修复了 Node.merge 中的一个拼写错误，也许这就是让您感到困惑的地方。 Mabye 让你感到困惑的是 return 通常不是写在 scala 中的。在合并的两个实现中，你可以放一个return，return that 和return Node(left.merge..., 意思完全一样。还有， return Node(...) 与 return new Node(...) 相同。无论如何，它是这样工作的

假设值是整数，this是

    5
   / \
  7   C
 / \
2   B
 \
  A

A, B, C 可能是单节点，整棵树，空的，我们不管，重点是2 的左 child 是空的，这是合并将发生的地方。

that 将只是 M，因为它包含的内容无关紧要。我们走吧。

这个是Node([node 7], 5, C)

我们称之为合并:

Node([node 7], 5, C).merge(M)

返回

Node([node 7].merge(M), 5, C)

重点是这段代码不返回this。它返回一个新节点，其中左子节点不是原始节点中的节点。它不再是[node 7]，而是[node 7].merge(M)。因此，让我们计算 [node 7].merge(M)。 [node 7] 是 Node([node 2], 7, B)。让我们将 M 合并到其中。

[node 7].merge(M) = Node([node 2], 7, B).merge(M) 
                  = Node([node2].merge(M), 7, B). 

同样，在返回的节点中，我们替换左子节点。再一次:[node2] 是 Node(Empty, 2, A)，所以:

[node 2].merge(M) = Node(Empty, 2, A).merge(M) 
                  = Node(Empty.merge(M), 2, A). 

现在我们进入底部。 Empty.merge(M) 是 M。我们只需要倒带，一切都会到位。

[node 2].merge(M) = Node(Empty, 2, A).merge(M) 
                  = Node(Empty.merge(M), 2, A) 
                  = Node(M, 2, A)

    2
   / \
  M   A

如您所见，我们实际上已经做了一些事情。结果 M 小于 2。

另一个进步:

[node 7].merge(m) = Node([node 2], 7, B).merge(M) 
                  = Node([Node 2].merge(M), 7, B). 

现在我们知道 [node2].merge(M) 是什么意思了。所以

Node([node 2], 7, B).merge(M) = Node(Node(M, 2, A), 7, B)

    7
   / \
  2   B
 / \
M   A

我们有 [节点 7].merge(m)，所以我们可以计算最终结果:

this.merge(m) = Node([node 7].merge(m), 5, C)

我们知道 [node 7].merge(m) 是什么，所以最终结果，如预期的那样:

        5
       / \
      7   C
     / \
    2   B
   / \
  M   A