스키마의 루트에서 트리의 모든 경로 찾기

Question

트리가있는 경우 루트에서 각 리프까지의 경로를 찾고 싶습니다.

그래서,이 나무를 위해 :

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

잎 (D, E, G)에 대한 루트 (A)에서 다음 경로가 :

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

나는 위와 같이 트리를 대표하는 경우 (A (B D E) (C (F G))) 다음 기능 g 트릭을 수행합니다

(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))))) 

을하지만이 모든 잘못 보인다. 나는 잠시 동안 이런 종류의 생각을 할 필요가 없었지만, 그것을하는 더 깔끔한 방법이 있어야한다고 생각합니다. 어떤 언어로든 더 나은 솔루션을 얻으려는 아이디어는 인정 될 것입니다.

---

편집 - 계획에 매핑 반테의 솔루션을 제공합니다 : 내 원래보다 훨씬 깔끔

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

합니다.

Answer 1

커먼 리스프에 더 익숙합니다. 반테의 대답의

(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)) 

Answer 2

예제 트리를 (루트 왼쪽 오른쪽) 목록으로 정의 할 수 있다고 생각합니다. 그래서 당신의 예제 트리는 다음과 같습니다 : (D (B (A() (C (F() G))) E)()) 그리고 트래버스하기가 더 쉽습니다.

Answer 3

트리 검색 알고리즘을 원합니다. 너비 우선 또는 깊이 우선 순회는 모두 작동하며,이 경우 전체 트리를 크롤링해야하므로 아무런 차이가 없습니다. 리프가 생길 때마다 결과에 현재 경로를 저장하면됩니다.

Answer 4

R5RS 번역 :

 
(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))))