algorithm - 反序列化给定格式的树？

Question

我有一串来自二叉树的节点，其序列化格式如下:

# <- the value of a node
(a b c) <- node b has left child a and right child c.

如果一个节点有一个 child ，它总是有两个 child 。所有节点都是独立的，它们的值只是 node.data 的值，因此许多节点可能具有相同的值(但它们仍然是不同的节点)。

例如:

(((1 6 3) 5 (8 1 2)) 10 (1 1 1))

表示树的根节点的值为 10，并且有两个值为 5 和 1 的子节点。值为 5 的子节点有两个子节点，6 和 1。6 有子节点 1 和 3，1 有子节点 8和 2，依此类推。

我试图将其解析为一棵树，但只知道如何通过修剪开始/结束括号然后扫描整个字符串直到 ( 匹配) 的数量。例如:

(((1 6 3) 5 (8 1 2)) 10 (1 1 1)) 

成为

((1 6 3) 5 (8 1 2)) 10 (1 1 1)

所以我扫描，扫描，扫描，并在我阅读 ((1 6 3) 5 (8 1 2)) 后匹配括号计数，这意味着我有左 child ，这意味着下一个角色将是 parent ，之后的一切都将是正确的 child 。递归，递归，等等。除了这种方式，我在每一步都浪费了很多时间重新扫描左边的 child 。

有更好的方法吗？

Answer 1

您没有在这里指定您选择的语言，但这看起来很像 LISP。它有一些很好的方法来处理这些列表，但尽管如此，我还是会尝试给出一个一般性的答案。

首先，这些是递归方法的步骤，在一些类似 Scala 的代码中:

def getLocalRoot(record : String) : Node
{
    val (leftChildrenString, rootPosition) = extractLeft(record)
    val rightChildrenString = extractRight(record, rootPosition)
    val localRootString = extractLocalRoot(record)
    val localRoot = new Node(localRootString) //
    if(leftChildrenString.contains('(')) //a hack, really
       localRoot.left = getLocalRoot(leftChildrenString) //not a leaf
    else
       localRoot.left = new Node(leftChildrenString)  //it is a leaf

    if(rightChildrenString.contains('('))
       localRoot.right=getLocalRoot(rightChildrenString)
    else
       localRoot.right = new Node(rightChildrenString)
    return localRoot
}

def findTreeRoot(serializedTree : String) : Node
{
    return getLocalRoot(serializedTree)
}

((1 5 6) 2 (4 3 0)) 我称粗体部分为“左边的 child ”，右边的部分为“右边的 child ”。

让我们用文字来解释。首先，您需要将字符串拆分为左侧和右侧，即 extractLeft 和 extractRight。我建议您通过从左到右解析字符串并计算括号来执行此操作。一旦计数在右括号后回到 1，下一项就是该子树的根。然后返回左边的部分。您还返回子树根的位置以将其传递给返回右 child 的函数，只是为了加快速度。返回字符串右侧部分的方法实际上应该只返回右侧的所有内容(减去结束 ))。

然后，获取当前本地根，存储它，并在左半部分和右半部分调用相同的方法，但只有如果左半部分或右半部分不是叶子。如果它是叶子，那么您可以使用它来实例化一个新节点，并将其附加到现在找到的父节点。我用了 hack，我只是检查字符串是否包含括号，你可以想出更好的解决方案。

===============替代方法===========

这只需要一次扫描，虽然我不得不用空格填充括号以便我可以更容易地解析它们，但尽管如此，关键是相同的。我基本上使用了一个堆栈。一旦你到达一个封闭的括号，从顶部弹出 3，合并它们，然后将它们推回。

trait Node

case class Leaf(value: String) extends Node

case class ComplexNode(left: Node, value: Leaf, right: Node) extends Node

object Main {

  def main(args: Array[String]) = {
    val stack = new mutable.Stack[Node]
    var input = "(((1 6 3) 5 (8 1 2)) 10 (1 1 1))"
    input = input.replace(")", " ) ").replace("(", " ( ") //just to ease up parsing, it's easier to extract the numbers

    input.split(" ").foreach(word =>
      word match {
        case ")" => {
          stack push collapse(stack)
        }
        case c : String =>  {
          if (c != "(" && c != "") 
             stack.push(Leaf(c))
        }
      }
    )
    println(stack.pop) //you have your structure on the top of the stack
  }

  def collapse(stack: mutable.Stack[Node]): Node = {
    val right = stack.pop
    val parent = stack.pop.asInstanceOf[Leaf]
    val left = stack.pop
    return new ComplexNode(left, parent, right)

  }
}