在嵌套树结构的每个分支中插入所有父分支的总和

Question

在树结构中,如何将键/值与每个分支合并,其中值是分支值和所有父分支值的总和？

例如,从跟随树结构开始:

[{  :v 1
    :_ [{ :v 2 }
        { :v 3
          :_ [{ :v 5 }]}
        { :v 4 }]}]

怎么可以重建为:

[{  :v 1
    :sum 1
    :_ [{ :v 2
          :sum 3 }
        { :v 3
          :sum 4
          :_ [{ :v 5
                :sum 9 }]}
        { :v 4
          :sum 5 }]}]

我一直在努力walk.我认为这可能是正确的做法.但是,到目前为止我还没有管理它.

Answer 1

我认为这个递归函数可以解决问题。

(defn sums [{v :v children :_} sum]
  {:v v
   :sum (+ sum v)
   :_ (mapv #(sums % (+ sum v)) children)})

当按以下方式评估时：

(def root
   [{:v 1
      :_ [{:v 2}
          {:v 3
           :_ [{:v 5}]}
          {:v 4}]}])    

[(sums (first root) 0)]

结果是：

[{:v 1,
  :sum 1,
  :_ [{:v 2,
       :sum 3,
       :_ []}
      {:v 3,
       :sum 4,
       :_ [{:v 5,
            :sum 9,
            :_ []}]}
      {:v 4,
       :sum 5,
       :_ []}]}]

sums或者，这里有一个适用于您的树格式的相同函数的更友好版本。

(defn sums [root]
  (letfn [(f [{v :v children :_} sum]
            {:v v
             :sum (+ sum v)
             :_ (mapv #(f % (+ sum v)) children)})]
    [(f (first root) 0)]))

(sums root)
;= same result as before