计算没有叶子的二叉树中的节点？/节点？在计划中？

Question

我正在尝试创建一个 returns 给定二叉树中节点数的函数，但我无权访问该节点？和叶子？ R5RS 语言中的函数。此外，我不太了解此类函数的终止条件，因为我尝试的大多数变体都会导致运行内存不足的错误。提前感谢您的帮助。

(define (make-tree value left right)
  (list value left right))

(define (value tree)
  (car tree))

(define (left tree)
  (cadr tree))

(define (right tree)
  (caddr tree))    

(define (tree-node-count t)
  (cond ((null? t)0)
        ((...?)
        (else (+
               (tree-node-count left)
               (tree-node-count right)))))

Answer 1

事实上，您 不需要 leaf? 或 node? 过程，如果我们要计算节点数，只需添加 1 他们每一个：

(define (tree-node-count t)
  (cond ((null? t) 0)
        (else (+ 1
                 (tree-node-count (left  t))
                 (tree-node-count (right t))))))

Answer 2

Scheme 中没有执行二叉树的标准方法，因此 left 和 right、leaf? 和 node? 等过程在不同的平台上有不同的实现数据建模的方法。例如。这是一个使用向量的方法：

(define TYPE-TREE (vector 'TREE)) ; private

(define (make-tree value left right)
  (vector TYPE-TREE value left right))

(define (tree? tree)
  (and (vector? tree)
       (eq? (vector-ref tree 0) TYPE-TREE)))

(define (tree-value tree)
  (vector-ref tree 1))

(define (tree-left tree)
  (vector-ref tree 2))

(define (tree-right tree)
  (vector-ref tree 3))

(define (tree-node-count tree)
  (let aux ((tree tree) (count 0))
    (if (not (tree? tree))
        count
        (aux (tree-right tree)
             (aux (tree-left tree) (+ 1 count))))))

(define test (make-tree 5 (make-tree 2 '() '()) (make-tree 10 '() '())))
(tree-node-count test) ; ==> 3

当然你会把它包装在一个库中并隐藏 TYPE-TREE。要回答您的问题，您需要用其实施替换程序。在上述模型的情况下 tree-node-count 将如下所示：

(define (tree-node-count tree)
  (let aux ((tree tree) (count 0))
    (if (not (and (vector? tree)
                  (eq? (vector-ref tree 0) TYPE-TREE)))
        count
        (aux (vector-ref tree 3)
             (aux (vector-ref tree 2) (+ 1 count))))))

如您所见，这是对原始过程主体的简单替换。我当然会反对它，因为这只会让代码和程序员的意图变得不那么清晰。删除抽象不会为您赢得积分。

计算没有叶子的二叉树中的节点？/节点？在计划中？

Count nodes in a binary tree without leaf?/node? in scheme?

tree

scheme