打印第 n 层树的元素

Question

灌木是一棵树，树节点可以没有子节点、一个子节点或两个子节点。每个树节点存储一个类型“a”的实例。多态类型 '灌木丛定义如下。

type 'a bush = 
  None
| One of 'a*'a bush
| Two of 'a*'a bush*’a bush

写一个函数 print_level : 'a bush -> int -> unit that prints the keys 来自用第二个参数定义的给定级别的灌木节点数。

我一直在重做一些老问题，偶然发现了这个问题。我不知道如何开始。

Answer 1

你没有说级别是如何编号的。为简单起见，假设它们在根部从 0 开始编号，并且子级的级别比其父级高 1。

最简单的可能是递归思考。如果您知道参数 n 始终为 0 怎么办？该功能会是什么样子？

现在假设您要编写带有参数 n 的函数 print_level。假设您有一个适用于小于 n 的所有级别值的函数。您如何使用其他功能来解决 n 级别的问题？

然后最大的揭示是这个另一个函数就是你的函数本身，递归地调用它自己。

Answer 2

我卖掉了。递归减少 n 直到我们达到 0 并打印该级别的每个元素。树木真的很漂亮。

let rec print_level (tr:'a bush) n =
match tr with
| None -> raise Not_found
| One (v,d) when n = 0 -> print_int v
| Two (v,l,d) when n = 0 -> print_int v
| One (v,d) -> print_level d (n-1)
| Two (v,l,d) -> print_level d (n-1);
    print_level l (n-1);;

打印第 n 层树的元素

Printing elements of the tree at level n

ocaml