在LISP(Racket)中定义树

Question

我正试图使用Racket的#plai语言定义一个树，尽管在通过"添加节点"函数创建树时我有点困难。

我使用的定义类型如下：

(define-type BBT
[empty]
[leaf (elem number?)]
[node (elem number?) (left BBT?) (right BBT?)])

我想构建一棵看起来像这样的树：

(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

以下电话：

(add-node 6 (add-node 4 (add-node 5 (add-node 3 (empty)))))

到目前为止，我已经尝试了以下几种：

(define (add-node n tree)
(match tree
[(empty) (node n (empty) (empty))]))

这适用于空树，因为它只添加了一个两边都有空树的节点，但我还没有找到像上面分享的例子那样构建树的方法。

关于我该怎么做，有什么建议吗？我知道当它捕捉到"节点"的情况时，我应该使用递归，但到目前为止，我还没有成功的尝试。

谢谢！

Answer 1

从您的示例来看：

(add-node 6 (add-node 4 (add-node 5 (add-node 3 (empty)))))

应该产生

(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

这包含了对add-node的许多调用，这使得它更加令人困惑。因此，为了更好地了解您想要什么，我将从对add-node的最内部调用开始。

(add-node 3 (empty))

从你问题中的初始代码来看，这似乎应该会产生

(node 3 (empty) (empty))

因此，现在替换更大示例中最内部的调用，它变成

(add-node 6 (add-node 4 (add-node 5 (node 3 (empty) (empty)))))
=
(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

现在我必须弄清楚下一个最内层的呼叫应该做什么

(add-node 5 (node 3 (empty) (empty)))

在最终输出中，3保持在顶部，5转到右侧节点，所以我只能猜测这个调用应该产生

(node 3 (empty) (node 5 (empty) (empty)))

现在在更大的例子中替换该调用：

(add-node 6 (add-node 4 (node 3 (empty) (node 5 (empty) (empty)))))
=
(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

下一个最内层的呼叫是

(add-node 4 (node 3 (empty) (node 5 (empty) (empty))))

这就是我不理解你逻辑的地方。根据上一个示例的模式，4应该进入最右边的节点"right right"。但在本例中，它似乎位于右节点的左侧，即"右-左"。它似乎不会去到最近的空节点，这将是纯粹的"左"节点，所以我不知道你想做什么模式。

如果你想得到更好的答案，请澄清你的问题并添加更多细节。

Answer 2

最后，我找到了一种构建树的方法：

(define (add-node n tree)
(match tree
[(empty) (node n (empty) (empty))]
[else (add-aux n tree)]))
(define (add-node-aux n tree)
(match tree
[(empty) (leaf n)]
[(leaf e) (if (> e n)
(node e (leaf n) (empty))
(node e (empty) (leaf n)))]
[(node e l r) (if (> e n)
(node e (add-node-aux n l) r)
(node e l (add-node-aux n r)))]))

它完成了任务，但我想知道是否有一种方法可以在不依赖辅助功能的情况下创建树。基本上，我创建了辅助调用，以防止只有一个节点(根树(的树被标记为"叶子"。因此，通过调用递归函数，可以获得类似树的(节点3(空((空((，而不是让第一个元素输出一个形状为(叶3(的树。

有没有一种方法可以在不打辅助电话的情况下做到这一点？

谢谢！