0

我正在尝试编写一个输入二叉树特定深度的方案程序。例如，二叉树的根为 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])))
4

2 回答 2

2

您的主要问题是您的递归调用fetch-exp交换了参数的顺序。应该是(fetch-exp (sub1 n) (left-tree bt))和(fetch-exp (sub1 n) (right-tree bt))。或者，更改函数的参数顺序：(lambda (bt n) ...).

于 2013-08-20T23:56:32.663 回答
2

计算每个孩子的深度将永远需要，因为它本身就是一个树遍历。此外，您可能会为每一侧做两次。如果必须这样做，最好将结果绑定在 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))))))

像你这样的人只会沿着左边的树枝走。如果堆栈上的 or 语句失败，则继续尝试，直到找到合适的数据项或到达树的最右下角分支。在最坏的情况下，您最终会遍历树一次，这实际上是您在非空树中的进程的最佳情况，因为您甚至在检查 n 是否为 1 之前就遍历了树。

于 2013-08-21T03:15:10.267 回答