scheme - 在方案中实现二叉搜索树

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用作 null 值，而不是'(). 在这种情况下，请在第一行中使用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)))))