tree - 如何通过索引获取子树？

Question

假设我有以下树:

在我的程序中，这棵树使用列表表示:'(+ (* 5 6) (sqrt 3))。

如何通过索引获取子树？

索引应该从0开始，深度优先。在上图中，我用索引标记了所有节点以显示这一点。

例如:

(define tree '(+ (* 5 6) (sqrt 3)))

(subtree tree 0)  ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree tree 1)  ; Returns: '(* 5 6)
(subtree tree 2)  ; Returns: 5
(subtree tree 3)  ; Returns: 6
(subtree tree 4)  ; Returns: '(sqrt 3)
(subtree tree 5)  ; Returns: 3

我试着像这样实现subtree:

(define (subtree tree index)
  (cond [(= index 0) tree]
        [else
         (subtree (cdr tree)
                  (- index 1))]))

但是，这不会遍历子列表。这是不正确的。

编辑:

我尝试使用连续传递样式实现子树:

(define (subtree& exp index counter f)
  (cond [(= counter index) exp]
        [(null? exp) (f counter)]
        [(list? exp)
         (let ((children (cdr exp)))
           (subtree& (car children)
                     index
                     (+ counter 1)
                     (lambda (counter2)
                       (if (null? (cdr children))
                           (f counter)
                           (subtree& (cadr children)
                                     index
                                     (+ counter2 1)
                                     f)))))]
        [else (f counter)]))

(define (subtree tree index)
  (subtree& tree
            index
            0
            (lambda (_)
              (error "Index out of bounds" index))))

这适用于像这样的树:

• '(+ 1 2)
• '(+ (* 5 6) (sqrt 3))

但是，对于像这样的树，它会失败:

• '(+ 1 2 3)

我的实现有什么问题？

Answer 1

在没有毛茸茸的控制结构的情况下做到这一点的方法是有一个议程。

但在此之前，定义抽象。每次我看到代码正在走它称为“树”的东西并且充满明确的 car，cdr &c 我必须阻止自己简单地冷启动希望我们能得到一个更好的宇宙。如果教你的人没有告诉你这个对他们说些强硬的话。

下面是树结构的一些抽象。这些特别重要，因为树结构确实是不规则的:我希望能够在任何节点上说“给我这个节点的 child ”:叶子只是没有 child 的节点，而不是某种特殊的东西。

(define (make-node value . children)
  ;; make a tree node with value and children
  (if (null? children)
      value
      (cons value children)))

(define (node-value node)
  ;; the value of a node
  (if (cons? node)
      (car node)
      node))

(define (node-children node)
  ;; the children of a node as a list.
  (if (cons? node)
      (cdr node)
      '()))

现在是议程的一些抽象。议程以列表的形式表示，但当然没有其他人知道这一点，而且更具工业实力的实现可能不想那样表示它们。

(define empty-agenda
  ;; an empty agenda
  '())

(define agenda-empty?
  ;; is an agenda empty?
  empty?)

(define (agenda-next agenda)
  ;; return the next element of an agenda if it is not empty
  ;; error if it is
  (if (not (null? agenda))
      (car agenda)
      (error 'agenda-next "empty agenda")))

(define (agenda-rest agenda)
  ;; Return an agenda without the next element, or error if the
  ;; agenda is empty
  (if (not (null? agenda))
      (cdr agenda)
      (error 'agenda-rest "empty agenda")))

(define (agenda-prepend agenda things)
  ;; Prepend things to agenda: the first element of things will be
  ;; the next element of the new agenda
  (append things agenda))

(define (agenda-append agenda things)
  ;; append things to agenda: the elements of things will be after
  ;; all elements of agenda in the new agenda
  (append agenda things))

现在很容易编写函数的纯迭代版本(议程是维护堆栈)，没有各种复杂的控制结构。

(define (node-indexed root index)
  ;; find the node with index index in root.
  (let ni-loop ([idx 0]
                [agenda (agenda-prepend empty-agenda (list root))])
    (cond [(agenda-empty? agenda)
           ;; we're out of agenda: raise an exception
           (error 'node-indexed "no node with index ~A" index)]
          [(= idx index)
           ;; we've found it: it's whatever is next on the agenda
           (agenda-next agenda)]
          [else
           ;; carry on after adding all the children of this node
           ;; to the agenda
           (ni-loop (+ idx 1)
                    (agenda-prepend (agenda-rest agenda)
                                    (node-children
                                     (agenda-next agenda))))])))

---

需要思考的一件事:如果将上述函数中的 agenda-prepend 替换为 agenda-append 会发生什么情况？