计算clojure中两个不同子树中的节点

Question

对 Clojure 很陌生，我不知道如何做，我需要遍历一个预制的二叉搜索树并计算 2 个不同子树中的节点数，就像这个问题

https://uva.onlinejudge.org/external/116/11615.pdf

非常感谢您提供的任何帮助，只需推动即可开始使用

(defn familytree [tree i x]
  (cond
    (= (first(tree) i) )
      (count (zip/children))

    (= (first(tree) x))
      (count (zip/children))

    :else
      (familytree (rest tree)x i)
      ))

输入数据 (def test1 '[ 1 [ 2 [ 4 [8 9 ] 5 [ 10 11 ]] 3 [ 6 [ 12 13 ] 7 [ 14 15 ]]]])

Answer 1

卡梅伦

首先决定将信息存储在哪种 Clojure 持久数据类型中。一旦决定：

看看 Clojure zippers。
看看 Clojure walk
正如您对递归的了解，根据树的大小，您可能会选择放弃诸如拉链之类的东西来直接递归。在这种情况下 for、loop 和 reduce 可能适用。

已更新

以下是我对需求的理解：

输入树将采用 vector/nested 向量结构
树中的每个向量都有一个 'node identifier'（在你的例子中是一个数字）
需要一个函数，当节点匹配某些条件时，为节点计算 children
应该能够指定返回计数的多个节点

鉴于此，我决定使用 zipper，因为它合理地展示了实现需求目标的逻辑分解。我还抽象了一些方面来实现它，因此用于计数的谓词 children 可能会改变。

您需要阅读 clojure.zip（inter-web 上有大量相关信息。

计数器 现在已经涵盖了核心遍历 (zippers) 让我们从计数函数开始。根据要求：无论我如何到达节点，我都想计算节点的 children：

(defn count-children-at-node
  "Takes a zipper location and counts
  elements of it's chidren vector. Uses flatten on the
  children to sequence all the elements for counting.
  Returns a tuple identifiying the node and it's children count"
  [loc]
  (let [cnodes (zip/right loc)]
    [:node (zip/node loc)
     :count (if (nil? cnodes) ; test for no children
              0
              (count (flatten (zip/node cnodes))))]))

主力军 这就是遍历发生的地方。它将是详尽无遗的，以便找到所有可能的感兴趣节点。计数也将包括在内（见下面的结果）。我也想积累我的结果，并有一个灵活的谓词函数来测试是否包含在结果中：

(defn find-nodes-to-count
  "Accumulate results of performing a reduction function on a node in
  the tree that matches the predicate criteria"
  [acc predfn redfn loc]
  (if (zip/end? loc)
    acc
    (if (predfn (zip/node loc))
      (recur (conj acc (redfn loc)) predfn redfn (zip/next loc))
      (recur  acc predfn redfn (zip/next loc)))))

包装器 有了我的核心计数器和遍历机制，使用一个简单的包装函数来锻炼核心：

(defn nodes-counter
  "Takes a tree collection and variable number of node identifiers
  and return an accumulation of tuples, each identifying the node and it's children
  count"
  [coll & nodevals]
  (find-nodes-to-count
    []                                  ; accumultator
    #(contains? (into #{} nodevals) %)  ; predicate function
    count-children-at-node              ; reduction function
    (zip/vector-zip coll)))             ; the tree collection

Test/Verify 使用节点标识符变体调用 nodes-counter 的一些 REPL 示例：

(def mytree [1 [2 [4 [8 9] 5 [ 10 11 ]] 3 [ 6 [ 12 13 ] 7 [ 14 15 ]]]])

(nodes-counter mytree 16)  ; => []
(nodes-counter mytree 15)  ; => [[:node 15 :count 0]]
(nodes-counter mytree 2 4) ; => [[:node 2 :count 6] [:node 4 :count 2]]
(nodes-counter mytree 4 2) ; => [[:node 2 :count 6] [:node 4 :count 2]]

计算clojure中两个不同子树中的节点

Counting nodes in two different subtrees in clojure

clojure

tree-traversal

subtree