Построение дерева из символического ввода

Question

Я пытаюсь построить дерево в языке схемы, начиная с ввода строки. Ниже то, что я попробовал -

(define travsal (lambda (tree) 
      (cond 
       ((null? tree) '()) 
       (#t (append (travsal (car tree)) (cons (cadr tree) 
(travsal (caddr tree)))))))) 

(define tree1 '(((() 4()) 2 (() 5())) 1 ((() 6()) 3 (() 7())))) 

    (display tree1) 
    (newline) 

    (travsal tree1) 

Как вы можете видеть его только итерация материалы, представленные и не делать то, что фактическое бинарное дерево должно делать. Я поражен логикой о том, как сохранить дерево с помощью узлов и дочернего элемента из символьного ввода, например - "(((() 4()) 2 (() 5())) 1 ((() 6()) 3 (() 7())))), а затем распечатать его, как описано выше, это печать.

Пожалуйста, помогите, я был задан этот вопрос в интервью и до сих пор не могу его решить.

Answer 1

Что значит «не делать то, что фактическое бинарное дерево должно делать»? , Код обхода в порядке, он делает in-order traversal дерева. Крепление ряд вопросов форматирования:

(define travsal 
    (lambda (tree) 
    (cond ((null? tree) '()) 
      (else (append (travsal (car tree)) 
         (cons (cadr tree) 
           (travsal (caddr tree)))))))) 

Теперь, имейте в виду, что дерево Предоставленный двоичная но не отсортированные:

(define tree1 '(((() 4()) 2 (() 5())) 1 ((() 6()) 3 (() 7())))) 

Если мы рисуем его, он будет выглядеть следующим образом:

 1 
    / \ 
    2  3 
/\ / \ 
4  5 6  7 

Который, после того, как в обход заказ будет правильно давать этот результат при использовании travsal процедуры:

(travsal tree1) 
=> '(4 2 5 1 6 3 7)