将节点插入树 - 球拍 [英] Insert Node into a Tree - Racket

问题描述

我正在尝试向树添加一个新节点。以下是我的定义和函数类型：

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)))

这篇关于将节点插入树 - 球拍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！