方案递归地查找树的最左节点

Question

我正在编写一个函数，用于查找任何树中最左边的节点。该函数不会遍历树或给出最左边的节点，而只是给出第一个节点的最左边的子节点。

(define (far-left tree)
(cond (null? (cadr tree))
(car tree)
(far-left (cdr tree))))

示例输入，它提供了许多节点而不是所需的节点：

(display (far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))))

Answer 1

你所说的"第一个节点最左边的子节点"是(cadr tree)。
您的函数中有一个(cadr tree)，这表明第一个条件始终为真。
这就是正在发生的事情。

cond的形式是

(cond clause-1 clause-2 ...)

每个子句又具有(condition value)的形式

。那是

(cond (condition-1 value-1)
(condition-2 value-2)
(condition-3 value-3)
...)

如果将其与函数匹配，您将看到

• null?是condition-1，(cadr tree)是value-1，
• car是condition-2的，tree是value-2的，并且
• far-left是condition-3，(cdr tree)是value-3。

由于null?不#f，第一个子句总是被选中。

正确的形式是

(define (far-left tree)
(cond
((null? (cadr tree)) (car tree))
(else (far-left (cdr tree)))

但是，此代码仍然不起作用。
修复作为练习留下的错误。

Answer 2

数据定义：Tree

• Tree是Leaf或Node，其中：
  • Leaf是Number。
  • Node是子Tree的非空列表。

功能：far-left

• 条件 1：作为输入的Leaf无效，因为我们应该找到"任何树中最左边的节点。
• 条件 2：如果Node将Leaf作为其最左侧(或first(元素，则它是最左侧的节点。如果最左边的元素是不是Leaf的Tree，我们会重复使用它。

#lang typed/racket
(define-type Leaf Number)
(define-type Node (Pairof Tree (Listof Tree)))
(define-type Tree (U Leaf Node))
(: far-left (-> Tree Node))
(define (far-left tree)
(cond [(number? tree) (error "Farthest left node of a leaf does not exist!")]
[(cons? tree)   (if (number? (first tree)) tree (far-left (first tree)))]))

测试：

(far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11)))
; =>  '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))
(far-left '((3 4 (6 7 (12 13))) 1  8 9 (10 11)))
; => '(3 4 (6 7 (12 13)))
(far-left '(((6 7 (12 13)) 3 4) 1  8 9 (10 11)))
; => '(6 7 (12 13))
(far-left '((((12 13) 6 7) 3 4) 1  8 9 (10 11)))
; => '(12 13)