Пройдите случайно через двоичное дерево?

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

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

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

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

Answer 3

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

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

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

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