Схема - количество внутренних узлов двоичного дерева поиска, которые имеют ровно один ребенок

Question

Так же, как заголовок говорит, что я хочу найти количество узлов, у которых есть один ребенок, и не могу понять, что не так с моим кодом:

Вот как я определяю деревья

(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

Вы должны избегать использования set! при написании процедур на Схеме, это императивный способ думать о решении на других языках программирования, но не правильный подход на Схеме.

Чтобы решить эту проблему, вам нужно только тщательно изучить все случаи и добавить 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 будет отличаться для каждой рекурсии. В вышеприведенном коде хелпер имеет доступ к мутату 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))) 

Это делает точно так же как и мутационной версию, может быть, даже чуть-чуть лучше.