问题描述
我正在尝试向树添加一个新节点。以下是我的定义和函数类型:
pre $ code(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)
;;将一个项目插入树中
;;注意:不要插入重复的项目
(define(insert nx)
(match x
('E'E)
((Nd ro rss)
cond
((=(size x)1)(Nd ro(Nd n'E'E)'E))
(else
(Nd ro rss))))))
插入是将插入节点到树中的插入。
以下是我将要提供的命令:
(插入10(Nd 1(Nd 2(Nd 4'E'E)(Nd 5'E'E))(Nd 3(Nd 6'E'E)(Nd 7'E'E))))
并且它应该在树中插入十个。但是,我在家里独立学习,不知道该怎么做。请帮忙。非常感谢!
你错过了递归,而你的基本情况是错误的。
插入一个空树会创建一个包含一个节点的树。
插入非空BST三种情况:
- 如果项目与此节点中的项目相同,则返回树不变
- 如果项目小于此节点,请插入左侧子树
- 否则,插入右侧子树
类似于
(define(insert nx)
(match x
'(nd n'E'E))
((Nd ro ls rs)
(cond
((= n ro)x)
((
你打算插入的树不是BST,所以这是行不通的。
你的树的结构如下:
1
/ \
2 3
/ \ / \
4 5 6 7
元素将如下所示:
4
/ \
2 6
/ \\ \\ / \
1 3 5 7
即$ b $ (Nd 3'E'E)(Nd 3'E'E))(Nd 6(Nd 5'E'E)(Nd 3'E'E) )(Nd 7'E'E)))
I am trying to add a new node to the tree. The following are my definitions and function type:
(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 is the insert that will insert the node into the tree.
The following is the command that I will give:
(insert 10 (Nd 1 (Nd 2 (Nd 4 'E 'E) (Nd 5 'E 'E)) (Nd 3 (Nd 6 'E 'E) (Nd 7 'E 'E))))
And it should insert ten into the tree. However, I am learning independently at home and I have NO idea what to do. Please help. Thank you so much!
You're missing the recursion, and your base case is wrong.
Inserting in an empty tree creates a tree with one node.
Inserting in a non-empty BST has three cases:
- If the item is the same as in this node, return the tree unchanged
- If the item is smaller than this node, insert in the left subtree
- Otherwise, insert in the right subtree
Something like
(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)))))))
The tree you're aiming to insert in isn't a BST though, so this won't work.
Your tree has the following structure:
1
/\
2 3
/\ /\
4 5 6 7
A search tree with those elements would look like this:
4
/\
2 6
/\ /\
1 3 5 7
which is
(Nd 4 (Nd 2 (Nd 1 'E 'E) (Nd 3 'E 'E)) (Nd 6 (Nd 5 'E 'E) (Nd 7 'E 'E)))
这篇关于将节点插入树 - 球拍的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!