相邻的二叉树

Question

我正在写一个函数，它需要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 

有人可以指导我这个问题的正确方向？我知道我可能不得不写一个辅助函数。

Answer 1

为了让递归工作，你只需要考虑两个问题：

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

• 如果t1不是空的，但你有一个功能，适用于t1的子树时正常工作，你会如何使用这个函数来得到结果？

如果你能弄明白，那么你确实有一个适用于子树的函数。

编辑

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