在方案中實現二叉搜索樹

Question

方案/球拍中的功能。 使用二叉搜索樹處理幾個函數。我已經定義了輔助功能是：

;; returns value of node 
(define (value node) 
    (if (null? node) '() 
     (car node))) 

;; returns left subtree of node 
(define (left node) 
    (if (null? node) '() 
    (cadr node))) 

;; returns right subtree of node 
(define (right node) 
    (if (null? node) '() 
    (caddr node))) 

，我試圖寫一個函數size這需要一棵樹作爲參數，並返回給定樹非空節點的數量

Answer 1

它看起來你非常接近。試試這個（未經測試）：

(define (size tree) 
    (if (null? tree) 0 
     (+ 1 (size (left tree)) (size (right tree))))) 

不過，就個人而言，我寧願喜歡使用#f爲空值，而不是'()。在這種情況下，請在第一行中使用not而不是null?。

Answer 2

只是一種選擇！ 您也可以使用結構，這將減少編寫三個函數的工作...

(struct node (val left right) #:transparent) 
(struct null-tree()) 

並直接寫入使用內置功能的結構上述功能，即謂詞和參數訪問。

(define (size tree) 
    (if (null-tree? tree) 0 
    (+ 1 (size (left tree)) (size (right tree)))))