合并二叉树斯卡拉

Question

它说here：

合并两个二叉树的最简单的方法是采取迭代下来一棵树的 左子，直到达到一个节点没有左子。 然后将其他树的根添加为左边的孩子。

简单。在“常规代码”，我会写这样的事：

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是不可能的。我可以为左节点递归这个函数，但是当它返回时，最后一个节点之前的元素将不被计算。

关于我怎么能想到这个的任何提示？ 我是斯卡拉的初学者，我非常沉迷于此。

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中有一个错误，我刚刚修复，也许是你困惑的原因。马布什让你感到困惑的是，返回通常不是scala。在这两种合并的实现中，你可能会得到一个回报，return that和return Node(left.merge...，这意味着同样的事情。另外，return Node(...)与return new Node(...)相同。总之，这里是如何工作的

假设值是整数，并且this是

5 
/\ 
    7 C 
/\ 
2 B 
\ 
    A 

A，B，C可以是单节点，整个树，空的，我们不关心，点是2的左边的孩子是空的，这是合并发生的地方。

that将仅仅是M，因为它包含的内容并不重要。我们走吧。

this是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). 

再次，在返回的节点中，我们替换左侧的子节点。再来一次：[节点2]为节点（空，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). 

现在我们知道什么是[节点2] .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