在球拍中創建二叉搜索樹？

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作爲空列表的別名即可。