Scheme

Question

正如标题所说，我想找出有一个节点的数量 child 并且无法弄清楚我的代码有什么问题：

我是这样定义树的

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

(define (value T) (car T))

(define (left T) (cadr T))

(define (right T) (caddr T))

查找节点数的代码：

(define (count-one-child T)
  (let* ((sum 0))
    (cond ((null? T) 0)
          ((and (null? (left T))(null? (right T))) sum)
          ((and (null? (left T)) (not (null? (right T))))
           (begin (set! sum (+ 1 sum)) (count-one-child (right T)) sum))
          ((and (null? (right T))(not (null? (left T))))
           (begin (set! sum (+ 1 sum)) (count-one-child (left T)) sum))
          (else (begin (count-one-child (left T)) (count-one-child (right T)))))))

Answer 1

在 Scheme 中编写过程时应避免使用 set!，这是在其他编程语言中考虑解决方案的必要方式，但在 Scheme 中不是正确的方法。

要解决这个问题，就是要通盘考虑，条件合适才加上1。并且不要忘记推进递归，并组合每个子树的结果。试试这个：

(define (count-one-child T)
        ; empty tree
  (cond ((null? T) 0)
        ; a leaf
        ((and (null? (left  T)) (null? (right T))) 0)
        ; only right subtree exists, add 1
        ((null? (left  T))
         (+ 1 (count-one-child (right T))))
        ; only left subtree exists, add 1
        ((null? (right T))
         (+ 1 (count-one-child (left  T))))
        ; both subtrees exist
        (else
         (+ (count-one-child (left  T))
            (count-one-child (right T))))))

Answer 2

正如 Óscar 在他的回答中提到的那样，使用突变并不是首选方法，但是我看到您已经问过如何使用突变来做到这一点，这就是方法：

(define (count-one-child T)
  (define sum 0)
  (define (aux T)
    (let* ((l (left T))
           (r (right T))
           (nulll? (null? l))
           (nullr? (null? r)))      
      (if nulll?
          (cond ((not nullr?)
                 (set! sum (+ 1 sum))
                 (aux r)))
          (cond (nullr?
                 (set! sum (+ 1 sum))
                 (aux l))
                (else
                 (aux l)
                 (aux r))))))
  (when (not (null? T))     
    (aux T))

  sum)

如您所见，sum 在递归过程 aux 之外，否则每个递归的 sum 变量都是不同的。在上面的代码中，助手可以访问在应用助手之前创建的 mutate sum 。

不需要太多重写就可以正常运行。您可以将它作为参数，而不是改变变量，并在递归的同时更新它：

(define (count-one-child T)
  (define (aux T sum)
    (let* ((l (left T))
           (r (right T))
           (nulll? (null? l))
           (nullr? (null? r)))
      (if nulll?
          (if nullr?
              sum
              (aux r (+ 1 sum)))
          (if nullr?
              (aux l (+ 1 sum))
              (aux l (aux r sum))))))
  (if (null? T)
      0
      (aux T 0)))

这与变异版本一样好，甚至可能稍微好一点。

Scheme - 恰好有一个 child 的二叉搜索树的内部节点数

Scheme - Number of internal nodes of a binary search tree which have exactly one child

tree