Pertanyaan Ubah simpul dalam pohon kelas kasus Scala


Asumsikan bahwa saya memiliki beberapa susunan pohon menggunakan kelas kasus, sesuatu seperti itu:

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))

Dan sekarang saya ingin membangun metode untuk mengubah node dengan beberapa id ke node lain. Sangat mudah untuk menemukan simpul ini, tetapi saya tidak tahu cara mengubahnya. Apakah ada cara sederhana untuk melakukan itu?


4
2018-02-03 13:52


asal


Jawaban:


Itu pertanyaan yang sangat menarik! Seperti yang telah dicatat orang lain, Anda harus mengubah seluruh jalur dari root ke node yang ingin Anda ubah. Peta yang tidak dapat diubah sangat mirip, dan Anda dapat belajar sesuatu melihat pada Clojure's PersistentHashMap.

Rekomendasi saya adalah:

  • Perubahan Tree untuk Node. Anda bahkan menyebutnya simpul dalam pertanyaan Anda, jadi ini mungkin nama yang lebih baik.
  • Tarik value sampai ke kelas dasar. Sekali lagi, Anda membicarakan hal itu dalam pertanyaan Anda, jadi ini mungkin tempat yang tepat untuk itu.
  • Dalam metode penggantian Anda, pastikan bahwa jika tidak a Node atau anak-anaknya tidak berubah, jangan buat yang baru Node.

Komentar ada dalam kode di bawah ini:

// 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
    }
  }
}

3
2018-02-03 16:28



Karena struktur pohon Anda tidak dapat diubah, Anda harus mengubah keseluruhan jalur, dari simpul ke akar. ketika Anda mengunjungi pohon Anda, menyimpan daftar node yang dikunjungi, kemudian, perbarui semua node hingga ke root, dengan metode salin, seperti yang disarankan oleh pr10001.


2
2018-02-03 14:18



Itu copy metode:

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))

1
2018-02-03 14:15