Блог

Я реализовал функцию для вставки узлов в двоичное дерево.
Узел дерева представляет собой список формы (left-node key right-node) .
(insert tree n) это моя функция вставки узла, где дерево — это список узлов дерева в двоичном дереве поиска, и я хочу добавить ключевое значение n в качестве нового узла.

Итак, (insert '(((() 4 ()) 5 (() 2 ())) 6 ()) 7) выдает вывод в виде
(((() 4 ()) 5 (() 2 ())) 6 (() 7 ())) .

Теперь я хочу сделать что-то вроде этого :
1. Определите список значений. (define (f) (list '1 `2 `3 `4 `5 ))
2. Выполните цикл по списку и введите значения одно за другим в дереве, начиная с пустого дерева.

Итак, когда я попытался выполнить шаг 2, я сделал следующее :

 (define x ()) ;; Tree x is initially empty
(insert x 2)  ;; This prints (() 2 ())
(insert x 1)  ;; This prints (() 1 ()). I want it to be ((() 1 ()) 2 ()).
(insert x 3)  ;; This prints (() 3 ()). I want it to be ((() 1 ()) 2 (() 3 ())).
  

Вот где я застрял.
Я предоставляю свою функцию вставки ниже.

 (define (left tree) (list-ref tree 0))
(define (value tree) (list-ref tree 1))
(define (right tree) (list-ref tree 2))

(define (insert tree n)
  (cond
    [( null? tree ) ( list () n () )]
    [(< n (cadr tree)) (list (insert (car tree) n) (cadr tree) (caddr tree))] 
    [(> n (cadr tree)) (list (car tree) (cadr tree) (insert (caddr tree) n))] 
    [else tree] 
  )
)
  

Может кто-нибудь подсказать, как я могу достичь намеченных результатов?

В вашем коде есть три проблемы. Обратите внимание, что в следующем я немного груб с кодом: я просто говорю прямо, так как пишу быстро, и я не пытаюсь быть грубым лично с вами!

Вы не определили все необходимые абстракции

Вам нужна хотя бы функция, которая создает узлы дерева, функция, которая проверяет наличие нулевого дерева, и объект, представляющий нулевые деревья. Вот более полный набор абстракций:

 (define null-tree '())

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (list left key right))

(define (left tree)
  (list-ref tree 0))

(define (value tree)
  (list-ref tree 1))

(define (right tree)
  (list-ref tree 2))
  

Ваша insert функция не использует абстракции

Он не использует те, которые вы определили, не говоря уже об отсутствующих, в результате чего получается непонятный беспорядок в стиле 1960-х годов. Вот ее версия, в которой повсюду используются абстракции (это также устраняет некоторые странные пробелы и проблемы с зависанием, которые никому не помогают читать ваш код):

 (define (insert tree n)
  (cond
    [(tree-null? tree)
     (make-tree-node null-tree n null-tree)]
    [(< n (value tree))
     (make-tree-node (insert (left tree) n)
                     (value tree)
                     (right tree))]
    [(> n (value tree))
     (make-tree-node (left tree)
                     (value tree)
                     (insert (right tree) n))]
    [else tree]))
  

Вы не поняли, что insert это функция

Он берет дерево и возвращает дерево, к которому добавлен элемент, вместо того, чтобы брать дерево и добавлять к нему элемент с помощью побочного эффекта. insert никогда не изменяет ни один из своих аргументов, а скорее создает подходящее новое дерево (или возвращает существующее дерево, если добавляемый элемент уже существует).

Итак, чтобы добавить последовательность элементов, например, вам нужно построить последовательность деревьев, в insert которые были добавлены эти элементы:

 (define (insert-elements tree elts)
  (if (null? elts)
      tree
      (insert-elements (insert tree (first elts)) (rest elts))))
  

Теперь:

 > (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'(((() 0 ()) 1 (() 2 (() 3 (() 4 ())))) 7 (((() 20 ()) 48 ()) 202 ()))
  

Зачем использовать абстракции

Если я изменю абстракции для деревьев:

 (define null-tree '/)

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (vector left key right))

(define (left tree)
  (vector-ref tree 0))

(define (value tree)
  (vector-ref tree 1))

(define (right tree)
  (vector-ref tree 2))
  

Тогда я могу использовать точно такую же функцию с этим новым типом дерева:

 > (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'#(#(#(/ 0 /) 1 #(/ 2 #(/ 3 #(/ 4 /)))) 7 #(#(#(/ 20 /) 48 /) 202 /))