代码之家 › 专栏 › 技术社区 › grifaton

在Scheme中找到从树的根到叶的所有路径

racket scheme lisp

grifaton · 技术社区 · 16 年前

给定一棵树,我想找出从根到每片叶子的路径。

所以,对于这棵树:

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

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

但这看起来完全错了。我已经有一段时间不用做这种思考了,但我觉得应该有一种更整洁的方式来做。任何更好的解决方案(任何语言)的想法都将不胜感激。

编辑-将Svante的解决方案映射到Scheme中得到:

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

比我原来的整洁多了。

4 回复 | 直到 16 年前

Svante 16 年前

我能更流利地用通俗的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))

Nietzche-jou 16 年前

斯万特答案的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))))

Ismael 16 年前

我认为您可以将示例树定义为(root left right)每个树都是一个列表。所以您的示例树是:(D(B(A()(C()(F()G)))E()),这更容易遍历

G__ 16 年前

你需要一个树搜索算法。广度优先或深度优先遍历都可以,在这种情况下,这两种遍历没有区别,因为您需要对整个树进行爬网。无论何时到达叶子,只要将当前路径存储在结果中即可。