Racket树深度函数(树递归)(无结构节点！)

Question

我正在尝试编写一个过程(深度树(，该过程以树为输入并返回一个整数使用Racket/Scheme 指示树的最大级别

示例：

(depth '()) => 0
(depth '(1 2 3)) => 1
(depth '(a (b (c (d))))) => 4
(depth '((((((0))))))) => 6

我不能在做这件事时使用结构，所以这对我来说是一项复杂得多的任务。我尝试过使用car/cdr递归+来实现这一点，但我不能完全正确。任何建议都将不胜感激。

Answer 1

输入是一个原子或一对；如果输入是一对，那么它可以包含原子或更多对。当输入是一对时，应该在子对的最大嵌套级别上加1。否则，输入不是一对，并且最大嵌套级别为0。请注意，在Racket中，'()不是pair?。

这些观察结果引出了一个非常简单的定义：

#lang racket
(define (max-depth xss)
(if (pair? xss)
(+ 1 (apply max (map max-depth xss)))
0))

这里，(map max-depth xss)计算为xss内所有子列表的最大嵌套级别的列表。为了找到最大值，需要apply将max应用于参数列表。由于子列表本身已经嵌套一级深，因此最大值加1。

max-depth.rkt> (max-depth 'x)
0
max-depth.rkt> (max-depth '())
0
max-depth.rkt> (max-depth '(1 2 3))
1
max-depth.rkt> (max-depth '(a (b (c (d)))))
4
max-depth.rkt> (max-depth '((((((0)))))))
6
max-depth.rkt> (max-depth '(a b (c d (e f (g)) h) (i j) (k (l (m (n (o) p))) q) r))
6

Answer 2

以下是我对这个问题的看法：

• 如果输入不是空列表，那么使用map，我们可以(递归地(检查列表中每个元素的最大递归深度，并从列表中选择map输出，即具有最大递归深度的元素，并将其加1。

• 否则，如果输入是空列表，则返回0。

代码：

(define (depth tree)
(if (null? tree)
0
(max-items (map (lambda (x)
(cond ((not (pair? x)) 1)
(else (+ 1 (depth x))))) tree))))
(define (max-items items)
(define (iter lst cur-max)
(cond ((null? lst) cur-max)
((> (car lst) cur-max) (iter (cdr lst) (car lst)))
(else (iter (cdr lst) cur-max))))
(iter (cdr items) (car items)))