如何在Racket编程语言中查找树的所有路径，而不使用仅映射的递归？

Question

我需要使用球拍编程语言查找树的所有路径，而无需使用地图。您只能使用递归！

示例：

((paths '(A (B D E) (C (F G))))

=>

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

Answer 1

我们从此子树中看到'(C (F G))-我们没有在处理二叉树，数据定义将说明可变数目的子树：

; Node  ::= Symbol
;
; Tree  ::= (U Symbol (list Node Tree ...))
; Trees ::= [List-of Tree]
;
; Path  ::= [List-of Node]
; Paths ::= [List-of Path]

现在，如果您想尝试解决方案，此提示可能会有用：递归计算所有子树的paths，这将为您提供路径列表。将当前树的节点添加到所有这些路径，并将它们合并为一个列表。

该解决方案看起来很长，这归因于本质上是地图工作的递归助手。

; Tree -> Paths
(define (paths tree)
  (if (symbol? tree)
      (list (list tree))
      (add-node+combine-paths (first tree)
                              (path-for-all-subtrees (rest tree)))))

; Trees -> Paths
(define (path-for-all-subtrees sub-tree-list)
  (if (empty? sub-tree-list)
      empty
      (cons (paths (first sub-tree-list))
            (path-for-all-subtrees (rest sub-tree-list)))))

; Node [List-of Paths] -> Paths
(define (add-node+combine-paths node list-of-paths)
  (combine-list-of-paths (add-node-to-list-of-paths node list-of-paths)))

; [List-of Paths] -> [List-of Path]
(define (combine-list-of-paths list-of-paths)
  (if (empty? list-of-paths)
      empty
      (append (first list-of-paths)
              (combine-list-of-paths (rest list-of-paths)))))

; Node [List-of Paths] -> [List-of Paths]
(define (add-node-to-list-of-paths node list-of-paths)
  (if (empty? list-of-paths)
      empty
      (cons (add-node-to-paths node (first list-of-paths))
            (add-node-to-list-of-paths node (rest list-of-paths)))))

; Node Paths -> Paths
(define (add-node-to-paths node paths)
  (if (empty? paths)
      empty
      (cons (add-node-to-path node (first paths))
            (add-node-to-paths node (rest paths)))))

; Node Path -> Path
(define (add-node-to-path node path)
  (cons node path))


(paths '(A (B D E) (C (F G))))

---

这里有一个不同的参考版本，可以自由使用列表抽象，循环，引号和模式匹配：

; Tree -> Paths
(define (paths2 tree)
  (match tree
    [(? symbol?) `((,tree))]
    [`(,node ,sub-trees ...)
     (combine-paths node (map paths sub-trees))]))

; Node [List-of Paths] -> Paths
(define (combine-paths node lo-paths)
  (append-map
   (λ (paths)
     (for/list ([path paths])
       (cons node path)))
   lo-paths))


(paths2 '(A (B D E) (C (F G))))