使用方案在二进制搜索树中插入节点密钥和值

问题描述

我要在树形图t中插入一个键key和一个值val，以返回一个新树，该树的节点在适当的位置包含键和值.

I am inserting a key key and a value val into the tree-map t returning a new tree with a node containing the key and the value in the appropriate location.

我有这个定义:

(define (tree-node key value left right)(list key value left right))

(define (get-key tn) (node_key tn))
(define (get-val tn) (node_val tn))
(define (get-left tn) (node_left tn))
(define (get-right tn) (node_right tn))

(define (node_key tn) (list-ref tn 0))
(define (node_val tn) (list-ref tn 1))
(define (node_left tn) (list-ref tn 2))
(define (node_right tn) (list-ref tn 3))

我正在尝试这种insert方法

(define (insert t key val)

  (cond (empty? t))
  (tree-node (key val '() '()))

  ((equal key (get-key t))
   (tree-node (key val (get-left t) (get-right t)))

   ((<key (get-key t))
    (tree-node ((get-key t) (get-val t) (insert (get-left t key val)) (get-right t)))
    (tree-node ((get-key t) (get-val t) (get-left t) (insert (get-right t key val)))))))

我正在使用它来定义

(define right (insert (insert empty 3 10) 5 20))

我在DrRacket中遇到此错误

and I'm getting this error in DrRacket

application: not a procedure;
expected a procedure that can be applied to arguments
given: (list 0 1 2)
arguments...: [none]

推荐答案

正在发生的事情是，在期望功能的位置返回了一个树节点(仅是一个列表). Scheme无法执行该列表-它不是一个函数，因此很抱怨.

What is happening is that a tree-node (which is just a list) is being returned in a position where a function is expected. Scheme cannot execute the list - it's not a function, so it's complaining.

我怀疑这是因为您弄乱了括号.

I suspect this is because you have messed up your parentheses.

(cond (empty? t))

是一个自包含的复合表达.将对其求值，并返回t的值.之后的表达式不作为cond的一部分进行评估.

Is a self-contained compound expression. It is evaluated, returning the value of t. The expressions after that are not evaluated as part of the cond.

这篇关于使用方案在二进制搜索树中插入节点密钥和值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！