Как управлять двоичными деревьями схемы

Question

Я пытаюсь написать программу схемы, которая вводит определенную глубину двоичного дерева. Например, корень двоичного дерева равен 1, а затем корень левого под дерева равен 2 и так далее и далее. Я должен заставить его выводить выражение данных с глубиной в дереве. Сейчас у меня есть следующий код, но я постоянно получаю сообщение об ошибке:

Error in null?: expected a list; got '1'. 

Если бы вы могли объяснить это, используя одни и те же термины в коде, который я использую это было бы здорово, как я учусь, и я не знаю, как использовать некоторые из более крупных выражений.

Это код

(define fetch-exp 
    (λ (n bt) 
    (cond [(empty-tree? bt) ▽#f] 
      [(> n (tree-depth (left-tree bt))) ▽#f] 
      [(> n (tree-depth (right-tree bt))) ▽#f] 
      [(one? n) (root bt)] 
      [(> (tree-depth (left-tree bt)) (tree-depth (right-tree bt))) 
      (fetch-exp (left-tree bt) (sub1 n))] 
      [(> (tree-depth (right-tree bt)) (tree-depth (left-tree bt))) 
      (fetch-exp (right-tree bt) (sub1 n))] 
      [else ▽#f]))) 

Answer 1

Подсчет глубины каждого ребенка будет длиться вечно, поскольку он сам является обходным деревом. Кроме того, вы можете сделать это дважды для каждой стороны. Было бы лучше связать результат в выражении let, если вам нужно это сделать. (Или где-нибудь, где вы делаете анализ случая и используете результат потенциальной дорогостоящей оценки более одного раза, если на то пошло). В противном случае пересмотреть программу так, чтобы она оценивала ее только один раз.

(define (fetch-exp n bt) 
    (cond ((empty-tree? bt) #f) 
     ((= 1 n) (root bt)) 
     (else (or (fetch-exp (sub1 n) (left-tree bt)) 
        (fetch-exp (sub1 n) (right-tree bt)))))) 

Это похоже на ваше, просто пойдет по левым веткам. Если это не удается, оператор или оператор стека продолжают пытаться, пока не найдут соответствующий элемент данных или не достигнут самой нижней правой ветви дерева. В самом худшем случае вы в конечном итоге обходите дерево один раз, что на самом деле является самым лучшим случаем для вашего процесса в непустом дереве, когда вы идете по дереву даже до проверки, является ли n равным 1.

Answer 2

Ваша главная проблема в том, что ваши рекурсивные вызовы в fetch-exp обменивали порядок аргументов. Это должно быть (fetch-exp (sub1 n) (left-tree bt)) и (fetch-exp (sub1 n) (right-tree bt)). Альтернативно, измените порядок параметров функции: (lambda (bt n) ...).