Postorder Baum Traversal mit clojure.zip, um Knoten zu bearbeiten

Question

Ich habe einen Baum als verschachtelten Vektor dargestellt. Ich möchte eine Verallgemeinerung von indexed für Bäume haben, um den Index jedes Knotens wie dies zeigt,

(visit 42); => [0 42] 
(visit [6 7]); => [0 
       ;  [[0 6] 
       ;  [1 7]]] 

Die naive Implementierung direkt verwenden clojure.zip würde (as already asked here)

(defn visit [tree] 
    (loop [loc (vector-zip tree)] 
    (if (end? loc) 
     (root loc) 
     (recur 
     (next (edit loC#(conj 
          [(count (lefts loc))] 
          %))))))) 

Aber wiederkehrende mit clojure.zip/next führt eine Preorder-Traversierung durch, was in diesem Fall zu einer Endlosschleife führt (nicht besuchte Knoten erhalten conj in einen [:found] Vektor unendlich). Ein anderer Ansatz wäre die Verwendung von clojure.walk/postwalk, bietet jedoch keine strukturellen Informationen wie den Index.

Wie würden Sie das umsetzen? Gibt es eine postorder-next für Zip, die es sofort lösen würde?

Answer 1

Ich bin mir nicht sicher, ob ich verstehe, was Sie zu tun versuchen, aber die Beispiele deuten darauf hin, dass die den Knoten zugewiesenen Indizes der Anzahl ihrer linken Geschwister entsprechen (seit dem zweiten Beispiel die Wurzel) Knoten und die 6 Kind sind mit 0 gekennzeichnet). Update: Anscheinend habe ich einfach das visit Beispiel das erste Mal falsch gelesen - es macht die Absicht klar genug ... Zum Glück jetzt, dass ich es richtig gelesen habe, scheint mir, dass die Antwort unten korrekt ist.

Wenn das richtig ist, ist dies eine clojure.walk/postwalk -basierte Lösung:

(defn index-vec-tree [vt] 
    [0 (walk/postwalk 
     (fn [node] 
     (if-not (vector? node) 
      node 
      (vec (map-indexed vector node)))) 
     vt)]) 

Mit den genannten Beispielen:

user> (index-vec-tree [6 7]) 
[0 [[0 6] [1 7]]] 
user> (index-vec-tree 42) 
[0 42] 

Update: Eine einfache Lösung map-indexed (erhältlich in 1.2 unter Verwendung von ; verwenden Sie map + clojure.contrib.seq-utils/indexed in 1.1):

(defn index-vec-tree [vt] 
    (letfn [(iter [i vt] [i (if (vector? vt) 
           (vec (map-indexed iter vt)) 
           vt)])] 
    (iter 0 vt)))