从 Clojure 中的列表创建树

Question

你好，我是 Clojure 的新手，

我正在尝试解决以下问题1

我解决这个问题的第一步是编写一个函数来接收一个列表（在我的例子中是地名列表）并将其变成一棵树。

(list 'Karlsruhe 'Stuttgart '100 'Stuttgart 'Ulm '80 'Ulm 'Muenchen '120)

我希望树看起来像这样：2

我希望树看起来像那样的原因是，我计划编写一个函数来接收目标和目的地，在新创建的树中搜索目标并记录所有右侧节点，然后在最后，检查哪个是最小的，returns那个是最小的。

我想要一些 help/guidance 谢谢。

男.

Answer 1

您尝试做的事情可以在不构建树的情况下完美完成。您的列表中有三胞胎，其中包含来源、目的地和一些数字。所以我会在这里制作一个 source 到 [destination number] 的映射，以便更好地查找，然后递归遍历它：

(def items (list 'Karlsruhe 'Stuttgart '100 
                 'Stuttgart 'Ulm '80 
                 'Ulm 'Muenchen '120))

(def items-lookup-map (into {} 
                        (map (juxt first rest) 
                             (partition 3 items)))

现在您的查找地图如下所示：

{Karlsruhe (Stuttgart 100), 
 Stuttgart (Ulm 80), 
 Ulm (Muenchen 120)}

所以现在您可以轻松编写一个函数来查找从源到目标的路径：

(defn find-path [source dest lookup-map]
  (let [[prev [dest & _]] (split-with
                           #(and (not (nil? %)) (not= % dest))
                           (iterate #(first (lookup-map %))
                                    source))]
    (when dest (concat prev [dest]))))

让我们测试一下：

user> (find-path 'Karlsruhe 'Ulm items-lookup-map)
(Karlsruhe Stuttgart Ulm)
user> (find-path 'Karlsruhe 'Prague items-lookup-map)
nil
user> (find-path 'Moscau 'Ulm items-lookup-map)
nil

现在你可以用它做任何你想做的事，例如在路径中找到一个最小数字：

(defn min-distance [src dest lookup-map]
  (when-let [path (seq (find-path src dest lookup-map))]
    (apply min (map #(second (lookup-map %)) (butlast path)))))

user> (min-distance 'Karlsruhe 'Muenchen items-lookup-map)
80

从 Clojure 中的列表创建树

Creating a tree from a list in Clojure

tree

list

clojure