二進制搜索樹計劃

我和我的朋友正在努力在Scheme中創建二進制搜索樹。我們無法保存我們插入的內容。我的教授說我們要用set-car！（CDR（左子樹莫名其妙，但我不知道到底哪裏把它。我們都應該使用設定的車！（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

來源

2013-09-26 Jared

這是使用Dr.Retet和R5RS。 – Jared

目前，您的BST插入正在返回與舊樹共享結構的新樹，而不是更新現有樹。你明白爲什麼？您應該只在葉子上創建一個新的樹節點，並且應該只分配其父節點的左側或右側子節點。 –

你有沒有看過[插入節點鍵和二進制搜索樹使用方案中的值]（http://stackoverflow.com/q/12910579/1281433）？ [使用set！在drscheme]（http://stackoverflow.com/q/4416862/1281433）中更改變量的值也是相關的（雖然質量不高）。 –

由於這聽起來像一個任務，我不想提供您所需要的確切的代碼，但是我會顯示兩個函數可以用來替換列表中的第n個元素，第一個函數與您的類似，因爲它會返回一個新列表並且不會修改輸入列表。 d將修改輸入列表。

(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-27 00:47:44

你已經提供'get'程序，爲什麼不從提供'set'程序開始？這樣做有助於完成「樹/節點抽象」，併爲您提供一組基本函數，以嘗試在「插入」過程中使用該函數。

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

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

現在，在insert代碼，當你想「向左走」，但沒有左，調用setLeftsubTree與新創建的葉節點。

來源

2013-09-27 14:15:42 GoZoner

二進制搜索樹計劃

回答

相關問題