5

ケースクラスを使用して構築されたツリーがあるとします。

abstract class Tree
case class Branch(b1:Tree,b2:Tree, value:Int) extends Tree
case class Leaf(value:Int) extends Tree
var tree = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6))

そして今、あるIDを持つノードを別のノードに変更するメソッドを構築したいと考えています。このノードを見つけるのは簡単ですが、変更方法がわかりません。それを行う簡単な方法はありますか？

4

3 に答える 3

3

とても興味深い質問ですね！他の人がすでに指摘しているように、ルートから変更したいノードまでのパス全体を変更する必要があります。不変マップは非常に似ており、 Clojure の PersistentHashMap を見れば何かわかるかもしれません。

私の推奨事項は次のとおりです。

  • に変更TreeしNodeます。あなたの質問ではそれをノードと呼んでいるので、これはおそらくより良い名前です。
  • value基本クラスに引き上げます。繰り返しになりますが、あなたは質問でそれについて話しているので、おそらくこれが適切な場所です。
  • replace メソッドでは、 aNodeもその子も変更されない場合は、新しい を作成しないでくださいNode。

コメントは以下のコードにあります。

// Changed Tree to Node, b/c that seems more accurate
// Since Branch and Leaf both have value, pull that up to base class
sealed abstract class Node(val value: Int) {
  /** Replaces this node or its children according to the given function */
  def replace(fn: Node => Node): Node

  /** Helper to replace nodes that have a given value */
  def replace(value: Int, node: Node): Node =
    replace(n => if (n.value == value) node else n)
}

// putting value first makes class structure match tree structure
case class Branch(override val value: Int, left: Node, right: Node)
     extends Node(value) {
  def replace(fn: Node => Node): Node = {
    val newSelf = fn(this)

    if (this eq newSelf) {
      // this node's value didn't change, check the children
      val newLeft = left.replace(fn)
      val newRight = right.replace(fn)

      if ((left eq newLeft) && (right eq newRight)) {
        // neither this node nor children changed
        this
      } else {
        // change the children of this node
        copy(left = newLeft, right = newRight)
      }
    } else {
      // change this node
      newSelf
    }
  }
}
于 2012-02-03T16:28:15.120 に答える
2

ツリー構造は不変であるため、ノードからルートまでのパス全体を変更する必要があります。ツリーにアクセスするときは、アクセスしたノードのリストを保持してから、 pr10001で提案されているように、copyメソッドを使用して、ルートまでのすべてのノードを更新します。

于 2012-02-03T14:18:54.030 に答える
1

copyメソッド:

val tree1 = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6))
val tree2 = tree1.copy(b2 = tree1.b2.copy(b1 = Leaf(5))
// -> Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(5), Leaf(5),6))
于 2012-02-03T14:15:35.787 に答える