Trouver tous les chemins de la racine aux feuilles de l'arbre dans le schéma

Étant donné un arbre, je veux trouver les chemins de la racine à chaque feuille.Trouver tous les chemins de la racine aux feuilles de l'arbre dans le schéma

Ainsi, pour cet arbre:

D 
/
    B 
/\ 
A E 
\ 
    C-F-G

a les chemins suivants de la racine (A) à feuilles (D, E, G):

(A B D), (A B E), (A C F G)

Si je représente l'arbre ci-dessus (A (B D E) (C (F G))) alors la fonction g le tour est joué:

(define (paths tree) 
    (cond ((empty? tree) 
     '()) 
     ((pair? tree) 
     (map (lambda (path) 
       (if (pair? path) 
        (cons (car tree) path) 
        (cons (car tree) (list path)))) 
       (map2 paths (cdr tree)))) 
     (else 
     (list tree)))) 

(define (map2 fn lst) 
    (if (empty? lst) 
     '() 
     (append (fn (car lst)) 
       (map2 fn (cdr lst)))))

Mais cela semble tout faux. Je n'ai pas eu à faire ce genre de réflexion depuis un moment, mais je pense qu'il devrait y avoir une façon plus simple de le faire. Des idées pour une meilleure solution (dans n'importe quelle langue) seraient appréciées.

EDIT - La solution de cartographie Svante dans le schéma donne:

(define (paths tree) 
    (if (pair? tree) 
     (append-map (lambda (node) 
       (map (lambda (path) 
        (cons (car tree) path)) 
        (paths node))) 
      (cdr tree)) 
     (list (list tree))))

qui est beaucoup plus propre que mon original.

Source

2010-06-10 grifaton

Je parle couramment le Common Lisp.

(defun paths (tree) 
    (if (atom tree) 
     (list (list tree)) 
     (mapcan (lambda (node) 
       (mapcar (lambda (path) 
          (cons (car tree) path)) 
         (paths node))) 
       (cdr tree)))) 

CL-USER> (paths '(A (B D E) (C (F G)))) 
((A B D) (A B E) (A C F G))

Source

2010-06-11 00:07:19 Svante

C'est un peu plus propre - et probablement plus correct, étant donné qu'il traite un arbre avec un seul noeud: (paths 'a) => ((a)), tandis que (g 'a) => (a). Est-ce que la carte de CL est plus ou moins équivalente à ma map2 ci-dessus? Connaissez-vous une fonction Scheme intégrée? – grifaton

Je ne sais pas grand-chose sur Scheme, mais j'aurais deviné que quelque chose comme mapcan est disponible. Peut-être que cela est considéré comme simple à mettre en œuvre, cependant. Votre 'map2' semble équivalent en principe, mais il a un mauvais appel de queue, donc il va sauter la pile quand la liste est trop longue. Peut-être que vous devriez utiliser l'accumulateur/idiome inverse. – Svante

L'équivalent du schéma 'mapcan' est" append-map "de SRFI-1. –

Je pense que vous pourriez définir l'arbre d'exemple comme (racine gauche droite) chacun une liste. Donc votre arbre d'exemple serait: (D (B (A() (C() (F() G))) E)()) et c'est plus facile à parcourir

Source

2010-06-10 23:35:23 Ismael

Je pense que vous avez mal lu mon schéma - A est la racine de l'arbre. Aussi (et ce n'est probablement pas clair à partir de la question) un nœud peut avoir plus de deux branches, et donc je ne pense pas que votre approche fonctionnerait. – grifaton

Je viens de me rendre compte que j'ai mal lu votre diagramme. Je dirais que si la fonction g fonctionne, vous devriez l'utiliser :-) – Ismael

Vous voulez un algorithme de recherche d'arbre. La traversée en largeur ou en profondeur fonctionnerait tous les deux, et cela ne fait aucune différence, car dans ce cas, vous devez ramper l'arbre entier. Chaque fois que vous arrivez à une feuille, il suffit de stocker le chemin actuel dans vos résultats.

Source

2010-06-10 23:59:59 Greg

traduction r5rs de la réponse de Svante:

 
(define (accumulate op init seq) 
    (define (iter ans rest) 
    (if (null? rest) 
     ans 
     (iter (op ans (car rest)) 
       (cdr rest)))) 
    (iter init seq)) 

(define (flatten seq) 
    (accumulate append '() seq)) 

(define (flatmap op seq) 
    (flatten (map op seq))) 

(define (atom? x) 
    (not (pair? x))) 

(define (paths tree) 
    (if (atom? tree) 
     (list (list tree)) 
     (flatmap (lambda (node) 
       (map (lambda (path) 
         (cons (car tree) path)) 
         (paths node))) 
       (cdr tree))))

Source

2010-06-11 08:51:07

Trouver tous les chemins de la racine aux feuilles de l'arbre dans le schéma

Répondre

Questions connexes