random - 随机通过二叉树？

Question

我正在制作一个程序，它采用一棵树并随机选择一个分支（左或右）并在列表中返回这些值。由于某种原因，它不起作用。有什么帮助吗？

例子：

~(rand-walk (tree 1 (leaf 2) (leaf 3)))
(1 2)

这是我到目前为止所拥有的：

(define (rand-walk tr)
 (if (empty-tree? tr) '()
   (if (leaf? tr) tr
      (if (equal? (random 1) 0)
              (cons ((root-value tr)(root-value (left-subtree tr))) '())
              (cons ((root-value tr)(root-value (right-subtree tr))) '())))))

Answer 1

免责声明：我从来没有用过Scheme，但大约15年前我和LISP有过一次短暂的接触=）

您的递归部分不是递归的。您应该调用rand-walk子树并对其进行cons处理。

          (cons ((root-value tr)(rand-walk (left-subtree tr))) '())
          (cons ((root-value tr)(rand-walk (right-subtree tr))) '())))))

Answer 2

如果你想遍历它，那么你应该在到达叶子时返回一个列表：

(if (leaf? tr) (cons tr '())

在你的递归步骤中，你应该cons使用一些递归调用：

(cons (root-value tr) (rand-walk (left-subtree tr)))

Answer 3

您的代码中存在许多问题。这是一个正确的实现：

(define (rand-walk tr)
 (cond ((empty-tree? tr) '())
       ((leaf? tr) (list (root-value tr)))
       ((equal? (random 1) 0)
        (cons (root-value tr) (rand-walk (left-subtree tr))))
       (else
        (cons (root-value tr) (rand-walk (right-subtree tr))))))

如果我在写这篇文章，我会使用尾递归方法：

(define (rand-walk tr)
  (assert (not (empty-tree? tr)))
  (let walking ((l '()) (tr tr))
    (let ((value (root-value tr)))
      (if (leaf? tr)
          (reverse (cons value l))
          (walking (cons value l))
                   ((if (zero? (random 1)) left-subtree right-subtree) tr))))))