在球拍中创建二叉搜索树？

Question

尝试创建不可变的二叉搜索树。我从创建构造函数开始创建空列表，以及使用以下代码逐个向树添加元素的方法。

#lang racket 
(define (constructTree) '()) 

(define (addToTree Tree k v) 

(cond [(null? Tree) 
      (cons Tree cons((cons k '()) v))] 
     [else 
     (cond [(>(car Tree) k) 
       (cons Tree cons((cons k '()) v)) 
       ] 
       [else 
       (cons Tree '() cons((cons k '()) v)) 
       ] 
      )] 
    ) 
) 


(define bst (addToTree (addToTree (addToTree (addToTree (constructTree)3 "3") 1 "1") 2 "2") 5 "5")) 
bst 

我的意思是一成不变的，如果 我叫(define b0 (constructTree))
b0应该返回'()
(define b1 (addToTree b0 4 "4"))
b1应该返回'(4 "4"()())
(define b2 (addToTree b1 6 "6"))
b2应该返回'(4 "4"() (6 "6"()()))
...等。
但我得到这个错误：应用程序：不是一个过程; 期望一个程序，可以适用于参数 给出：'（3） 参数...：
任何线索为什么我得到这个错误或我做错了什么？先谢谢你。

Answer 1

我想你可能会寻找这样的事情：

(define emptyTree '()) 

(define (addToTree Tree k v) 
    (match Tree 
    ['() 
    (list k v '() '())] 
    [(list key val left right) 
    (if (> k key) 
     (list key val left (addToTree right k v)) 
     (list key val (addToTree left k v) right))])) 

注意，由于不可改变的，没有必要每次构造一个新的空的树。您只需将emptyTree作为空列表的别名即可。