反序列化广度优先树

Question

我需要使用四叉树，如下所示：

           p
         /| |\ 
        / | | \    
       /  | |  \
      p   w b   p
    /| |\     /| |\   
   / | | \   / | | \
  b  w w  b w  b w  b

但是它们已经以广度优先的顺序序列化为字符串，因此前面的树将具有以下表示形式：

ppwbpbwwbwbwb

我正在尝试将这样的字符串转换为嵌套向量结构：

[ [ b w w b ] w b [ w b w b] ]

但有时以下代码无法正确工作：

(defn read-quad-tree [pattern]
  (loop [r                    []
         [s & rs :as stack]   []
         [p & rp :as pending] (reverse pattern)]
    (cond (nil? pending)  (first r)
          (= (count r) 4) (recur [] (conj stack (reverse r)) pending)
          (= p \p)        (recur (conj r s) rs rp)
          :else           (recur (conj r p) stack rp))))

编辑：增加一个复杂的示例：

另一个（失败的）示例。下一个树如下：

                    |
         +------+-------+------+
         |      |       |      |
         |      w       w      |
         |                     |
   +---+---+---+         +---+---+---+
   |   |   |   |         |   |   |   | 
   |   w   w   |         |   w   w   |
   |           |         |           |
+-+-+-+     +-+-+-+   +-+-+-+     +-+-+-+
| | | |     | | | |   | | | |     | | | |
b b b b     w w w w   b b w w     b w b w

将被序列化为：

ppwwppwwppwwpbbbbwwwwbbwwbwbw

目标是获取以下结构：

[ [ [ b b b b ] w w [ w w w w ] ] w w [ [ b b w w ] w w [ b w b w ] ] ]

但我的代码给出了不同的（错误的）结构。

- gimco

---

孩子节点是否总是属于一个“p”父节点，而所有其他字母都是树的叶子节点？ - trincot

是的，叶节点始终为 b 或 w，而 p 用于序列化以指示该节点具有子节点。 - gimco

这将是一个很好的使用场景，可使用 test.check 进行双向测试。 - gfredericks

看起来提供的代码可以处理给定的数据。请编辑您的问题并包括至少一个示例，其中您发布的代码无法产生所需的输出。如果可以，请包括四叉树形式的树的图表、树的序列化版本、预期结果和您得到的结果。谢谢。 - Bob Jarvis - Слава Україні

Answer 1

您的代码存在一些名称表示列表而不是（旨在表示）向量。

这已经可以从函数的返回值中看出来，它是一个列表。

请看代码的以下部分：

(loop   ...
        [s & rs :as stack]
        ...
        (recur (conj r s) rs rp)

被突出显示的[s&rs:as stack]将获得stack向量，将第一个元素命名为s，其余元素命名为list(!) rs。由于rs是一个列表，在某个时刻它会像这样传递到stack(通过最后一个recur)，然后也是一个列表，而不是一个向量。那么，下一次r有4个元素时，(conj stack ...将不会将r附加在末尾，而是将其作为前缀，因为这是应用于列表时conj的行为。引自docs：

;; 注意将向量连接到末尾

;; 注意将列表连接到开头

当然，这破坏了预期的算法，并解释了您得到的错误结果。

(reverse r)也存在类似的问题，它返回一个序列，即使r是一个向量。

您可以修复它，例如通过在您想要将列表传递为向量的位置应用(into[]...)。我看到有两个地方需要这样做：

(defn read-quad-tree [pattern]
  (loop [r                    []
         [s & rs :as stack]   []
         [p & rp :as pending] (reverse pattern)]
    (cond (nil? pending)  (first r)
          (= (count r) 4) (recur [] (conj stack (into [] (reverse r))) pending)
          (= p \p)        (recur (conj r s) (into [] rs) rp)
          :else           (recur (conj r p) stack rp))))

这个修复对于待处理的并不需要，因为它从未将其他名称与列表类型“感染”。

当以以下方式调用更正后的代码时：

(println (read-quad-tree "ppwwppwwppwwpbbbbwwwwbbwwbwbw"))

它将输出：

[[[b b b b] w w [w w w w]] w w [[b b w w] w w [b w b w]]]

在寻找问题时，我还添加了一些关于有效和无效模式的检查，这可能会引起您的兴趣。扩展代码如下：

(defn read-quad-tree [pattern]
    (loop   [r                   []
            [s & rs :as stack]   []
            [p & rp :as pending] (reverse pattern)]
        (cond
            (nil? pending)
                (if (or (seq stack) (not= (count r) 1))
                    {:error "Too few 'p'"}
                    {:tree (first r)})
            (= (count r) 4)
                (recur [] (conj stack (into [] (reverse r))) pending)
            (= p \p) 
                (if (empty? s)
                    {:error (format "'p' at %s lacks %d children" (count pending) (- 4 (count r)))}
                    (recur (conj r s) (into [] rs) rp))
            :else
                (recur (conj r p) stack rp))))

如果一切顺利，它将返回一个带有 "tree" 键的映射，如果模式不完整，则返回带有 "error" 键的映射。请注意保留 HTML 标签。

- trincot