1

我正在编写一个函数，该函数采用 2 个二叉树（t1 和 t2）并生成一棵将 t2 放在 t1 右下角的新树。t2 附加到右孩子为空的第一个节点，即使该节点不是叶子。

let rec adjoin_right (t1: 'a tree) (t2: 'a tree) : 'a tree

测试用例：

let test () : bool =
adjoin_right (Node (Empty, 1, Empty)) (Node (Empty, 2, Empty)) = 
Node(Empty, 1, Node (Empty, 2, Empty))
;; run_test "adjoin_right leaf" test

有人可以引导我解决这个问题吗？我知道我可能不得不编写一个辅助函数。

4

1 回答 1

2

要使递归起作用，您只需要考虑两个问题：

  • t1如果是，结果应该是Empty什么？

  • 如果t1不为空，但您有一个函数在应用于 的子树时可以正常工作t1，您将如何使用此函数来获得结果？

如果你能弄清楚这些，那么你确实有一个适用于子树的函数。

编辑

考虑递归情况。你有l（你的左子树）、r（你的右子树）和v（节点中的值）。在 FP 中，您不会更改任何这些值。您要做的是构建具有正确内容的新树。那么，您将如何递归地使用您的函数从这三种成分中生成新树？这并不难——实际上只有一行代码。

于 2013-02-02T04:39:38.750 回答