Ходить случайным образом через двоичное дерево?

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

У вас есть ряд проблем в вашем коде. Вот правильная реализация:

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

Answer 2

Если вы хотите пройти его, вы должны вернуть список, когда достигнете листа:

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

И в тебе рекурсивные шаги ты должен cons с некоторым рекурсивным вызовом:

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

Answer 3

Отказ от ответственности: я никогда не писал на Схеме, но у меня была короткая встреча с LISP около 15 лет назад =)

Ваша рекурсивная часть не рекурсивна. Вы должны звонить rand-walk на поддереве и consэто

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