인접 목록의 트리

Question

{node [children]}의 인접성 목록에서 트리를 만드는 함수를 만들려고합니다.

{nil {:a {:b {:d nil 
       :e nil} 
      :c {:f nil}}}} 

그러나 나는 시도 발생한다

(def adjacency 
    {nil [:a] 
    :a [:b :c] 
    :b [:d :e] 
    :c [:f]}) 

, 나는 일을 가져올 수 없습니다. 재귀는 약간의 약점이며, 대부분의 재귀 예제는 트리가 아닌리스트를 통해 재귀를 처리하는 것으로 나타났습니다.

편집 됨 : 게시 당시 편집자와 원본 출처가 없어 원래 데이터 세트와 결과가 의도하지 않게 중첩되지 않았습니다. 미안합니다.

Answer 1

모든 서브맵에 하나의 항목 만 adjacency에 있습니다. 필요한가? 그리고 결과에서 같은 문제가 tree.

나는 더 명확 것입니다 희망 :

(def adjacency {:a [:b :c] 
       :b [:d :e] 
       :c [:f]}) 

그래서 솔루션입니다 :

(defn tree [m root] 
    (letfn [(tree* [l] 
      (if (contains? m l) 
       {l (into {} (map tree* (m l)))} 
       [l nil]))] 
    (tree* root))) 

테스트 :

(tree adjacency :a) 
=> {:a {:b {:d nil 
      :e nil} 
     :c {:f nil}}} 

업데이트. 중첩 된지도

(defn tree [m root] 
    (letfn [(tree* [l] 
      (if (contains? m l) 
       (list l (map tree* (m l))) 
       (list l nil)))] 
    (tree* root))) 

(tree adjacency :a) 
=> (:a ((:b ((:d nil) 
      (:e nil))) 
     (:c ((:f nil))))) 

Answer 2

같은 결과 트리가 필요하지 않은 경우 나는 보통 나무를 처리 할 때 clojure.walk를 사용하는 것을 선호합니다. 루트 노드가 adjacency 벡터의 첫 번째 노드라고 가정합니다.

(use 'clojure.walk) 

(def adjacency 
    [{nil [:a]} 
    {:a [:b :c]} 
    {:b [:d :e]} 
    {:c [:f]}]) 

(prewalk 
(fn [x] 
    (if (vector? x) 
    (let [[k v] x lookup (into {} adjacency)] 
     [k (into {} (map (fn [kk] [kk (lookup kk)]) v))]) 
    x)) 
(first adjacency)) 

이 결과 : {nil {:a {:b {:d {}, :e {}}, :c {:f {}}}}}

참고 :지도는 다음이 트리를 탐색 쉽게로 빈 아이가 {}보다는 nil로 표시됩니다, 또한 자식 요소는 맵이 아닌 벡터입니다.