将节点插入树 - 球拍

我正在尝试将新节点添加到树中。以下是我的定义和功能类型：将节点插入树 - 球拍

(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

将节点插入树 - 球拍

回答

相关问题