0

我和我的朋友目前正致力于在 Scheme 中创建二叉搜索树。我们无法让它保存我们插入的内容。我的教授说我们要用set-car！(cdr ( 不知何故用于左子树，但我不知道将它放在哪里。我们应该使用 set-car! (cddr ( 也用于右子树。

到目前为止，我们已经正确地完成了所有这些，但我们只需要帮助它保存我们插入的节点。

代码： 

(define make-empty-BST '())

;create function to see if BST is empty
(define (emptyBST? BST) (null? BST))

;make non-empty BST with explicit list implementation
(define (make-BST root left-subtree right-subtree)  
  (list root left-subtree right-subtree))

;helper get root function
(define (getRoot BST) (car BST))

;helper get left subtree function
(define (getLeftsubTree BST) (cadr BST))   ;(car (cdr tr))

;helper get right subtree function
(define (getRightsubTree BST) (caddr BST))  ;(car (cdr (cdr tr)))

;Checks to see if a leaf is empty
(define (emptyleaf? BST) (and (null? (getLeftsubTree BST)) (null? (getRightsubTree BST))))

;inserts an item into the BST
(define (BST-insert BST item)
  (cond
    ((emptyBST? BST) ;if empty, create a new root with given item - use empty lists for left and right subtrees
     (make-BST item make-empty-BST make-empty-BST))
    ((< item (getRoot BST)) ;if item less than root, add to left subtree
     (make-BST (getRoot BST)
               (BST-insert (getLeftsubTree BST) item) ;recursion
               (getRightsubTree BST)))                                     
    ((> item (getRoot BST))                                         
     (make-BST (getRoot BST)
           (getLeftsubTree BST)
           (BST-insert (getRightsubTree BST) item)))
    (else BST)))  ; it's already in BST, do nothing
4

2 回答 2

0

您已经提供了“获取”程序，为什么不从提供“设置”程序开始呢？这样做有助于完成“树/节点抽象”，并为您提供一组基本功能，以尝试在“插入”过程中使用。

(define (setLeftsubTree BST left) 
  (set-car! (cdr BST) left))

(define (setRightsubTree BST right) 
  (set-car! (cddr BST) right))

现在，在您的insert代码中，当您想要“向左走”但没有左侧时，请使用新创建的叶节点调用 setLeftsubTree。

于 2013-09-27T14:15:42.947 回答
0

由于这听起来像是一项任务，我不想提供您需要的确切代码，但我将展示两个可以说替换列表的第 n 个元素的函数。第一个类似于您的，因为它返回一个新列表并且不修改输入列表。第二个将修改输入列表。

(define (replace-nth n element list)
  ;; return a new list like list, but whose 
  ;; nth element is element
  (if (= n 0)
      (cons element (cdr list))
      (cons (car list) (replace-nth (- n 1) element (cdr list)))))

(let ((l (list 1 2 3 4 5 6)))
  (display (replace-nth 3 'x l)) ; prints (1 2 3 x 5 6)
  (display l))                   ; prints (1 2 3 4 5 6)

第一个返回一个新列表，但不修改输入列表。cons它使用应用于旧列表的一部分和一些新值来创建一个新列表。这类似于您通过创建具有新值的新树进行插入时所做的事情。你经过的树不会有它，但树会。

(define (set-nth! n element list)
  ;; set the nth element of list to be element
  (if (= n 0)
     (set-car! list element)
     (set-nth! (- n 1) element (cdr list))))

(let ((l (list 1 2 3 4 5 6)))
  (display (set-nth! 4 'x l)) ; prints #<void>
  (display l))                ; prints (1 2 3 4 x 6)

第二个修改传递给它的列表。它的返回值并不那么重要，因为传递给它的结构实际上被修改了。这更像是您想要使用插入功能执行的操作。您需要递归，直到到达树中的正确节点，并将其左或右子节点设置为仅包含新元素的新树。

于 2013-09-27T00:47:44.217 回答