將節點插入樹 - 球拍

我正在嘗試將新節點添加到樹中。以下是我的定義和功能類型：將節點插入樹 - 球拍

(define-struct (Some T) 
    ([value : T])) 

(define-type (Option T) 
    (U 'None (Some T))) 

(define-type BST (U 'E Nd)) 

(define-struct Nd 
    ([root : Integer] 
    [lsub : BST] 
    [rsub : BST])) 

(: insert : Integer BST -> BST) 
;; insert an item into a tree 
;; note: do not insert duplicate items 
(define (insert n x) 
    (match x 
    ('E 'E) 
    ((Nd ro ls rs) 
    (cond 
     ((= (size x) 1) (Nd ro (Nd n 'E 'E) 'E)) 
     (else 
     (Nd ro ls rs))))))

插入是將插入節點到樹中的插入。

以下是我給的命令：

(insert 10 (Nd 1 (Nd 2 (Nd 4 'E 'E) (Nd 5 'E 'E)) (Nd 3 (Nd 6 'E 'E) (Nd 7 'E 'E))))

它應該插入十成的樹。但是，我在家裏獨立學習，我不知道該怎麼做。請幫忙。非常感謝！

來源

2016-11-10 testomg

如果你已經錯過了他們有兩本免費的在線免費書籍：[SICP]（https://mitpress.mit.edu/sicp/）和[HtDP]（http://www.htdp.org/）。他們不是關於類型球拍，但原則是相同的。 – molbdnilo

你錯過了遞歸，你的基本情況是錯誤的。

插入一棵空樹會創建一棵具有一個節點的樹。

在非空BST插入有三種情況：

如果該項目是一樣的在這個節點，返回樹不變
如果該項目是比這個節點小，插入左子樹
否則，插入右子樹

喜歡的東西

(define (insert n x) 
    (match x 
    ('E (Nd n 'E 'E)) 
    ((Nd ro ls rs) 
    (cond 
     ((= n ro) x) 
     ((< n ro) (Nd ro (insert n ls) rs)) 
     (else  (Nd ro ls (insert n rs)))))))

你打算插入的樹不是BST，所以這是行不通的。

你的樹結構如下：

這些元素搜索樹應該是這樣的：

這是

(Nd 4 (Nd 2 (Nd 1 'E 'E) (Nd 3 'E 'E)) (Nd 6 (Nd 5 'E 'E) (Nd 7 'E 'E)))

來源

2016-11-10 08:08:36 molbdnilo

將節點插入樹 - 球拍

回答

相關問題