Определение дерева в LISP (Ракетка) - PullRequest
Новая
       12

Определение дерева в LISP (Ракетка)

0 голосов
/ 13 марта 2020

Я пытаюсь определить дерево, используя язык #plai Ракета, хотя я немного борюсь, когда дело доходит до создания дерева с помощью функции "add-node".

Тип определения Я использую это выглядит так: 

(define-type BBT
  [empty]
  [leaf (elem number?)]
  [node (elem number?) (left BBT?) (right BBT?)])

И я хотел бы построить дерево, которое выглядит следующим образом: 

(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

После этого вызова: 

(add-node 6 (add-node 4 (add-node 5 (add-node 3 (empty)))))

До сих пор я пробовал следующее: 

(define (add-node n tree)
  (match tree
    [(empty) (node n (empty) (empty))]))

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

Какие-либо советы или предложения относительно того, что мне делать? Я знаю, что я должен использовать рекурсию, когда она ловит случай «узла», но пока я не сделал успешную попытку.

Спасибо!

Ответы [ 2 ]

0 голосов
/ 14 марта 2020

В конце концов, я нашел способ построить дерево следующим образом: 

(define (add-node n tree)
  (match tree
    [(empty) (node n (empty) (empty))]
    [else (add-aux n tree)]))

(define (add-node-aux n tree)
  (match tree
    [(empty) (leaf n)]
    [(leaf e) (if (> e n)
                  (node e (leaf n) (empty))
                  (node e (empty) (leaf n)))]
    [(node e l r) (if (> e n)
                    (node e (add-node-aux n l) r)
                    (node e l (add-node-aux n r)))]))

Это делает свою работу, но мне было интересно, есть ли способ создать дерево, не полагаясь на вспомогательную функцию , По сути, я создал вспомогательный вызов, чтобы деревья с одним узлом (Root деревья) не были помечены как «листья». Таким образом, вместо того, чтобы первый элемент выводил дерево с формой (лист 3), вызывая рекурсивную функцию, можно получить дерево типа (узел 3 (пустой) (пустой)).

Есть ли способ, которым я мог бы сделать это, не делая вспомогательный вызов?

Спасибо!

0 голосов
/ 13 марта 2020

Из вашего примера: 

(add-node 6 (add-node 4 (add-node 5 (add-node 3 (empty)))))

должен производить 

(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

Это содержит много вызовов add-node, и это делает его более запутанным. Поэтому, чтобы получить лучшее представление о том, что вы хотите, я начну с самого внутреннего вызова add-node. 

(add-node 3 (empty))

Из исходного кода в вашем вопросе, похоже, это должно привести к 

(node 3 (empty) (empty))

Итак, теперь, заменяя самый внутренний вызов в вашем большом примере, он становится 

(add-node 6 (add-node 4 (add-node 5 (node 3 (empty) (empty)))))
=
(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

Теперь я должен выяснить, что должен делать следующий самый внутренний вызов. 

(add-node 5 (node 3 (empty) (empty)))

В конечном выводе 3 остается на вершине, а 5 идет к правому узлу, поэтому я могу только догадываться, что этот вызов должен произвести 

(node 3 (empty) (node 5 (empty) (empty)))

Теперь заменив этот вызов в более широком примере: 

(add-node 6 (add-node 4 (node 3 (empty) (node 5 (empty) (empty)))))
=
(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

Следующий внутренний вызов 

(add-node 4 (node 3 (empty) (node 5 (empty) (empty))))

Теперь я не понимаю вашу логику c. В соответствии с шаблоном предыдущего примера, 4 должен go в самый правый узел, "правый правый". Но в этом примере кажется, что go в левой части правого узла «правый левый». Кажется, он не идет к ближайшему пустому узлу, который был бы чисто «левым», поэтому я не знаю, какой шаблон вы пытаетесь создать.

Пожалуйста, уточните свой вопрос и добавьте больше Подробности, если вы хотите получить лучший ответ.

...