f# 访问树的根元素

发布于 2024-11-03 20:10:11 字数 498 浏览 0 评论 0原文

我在 F# 中有一个规范树，即通过声明

type binaryTree = 
    | Leaf
    | Node of binaryTree * float * binaryTree

然后使用递归函数来创建树

let rec makeTree tree element = 
    match element, tree with
        | x, Leaf -> Node(Leaf,x,Leaf)
        | x, Node(l,y,r) -> Node(l,y, (makeTree r x))

这一切都很好。现在我想对树进行排序，以便在每个节点上，该节点的值都小于其所有子节点的值。我可以想象这样做。但是，我想获取树的第一个元素。也就是说，我想将树视为队列。我见过的关于树的唯一示例使用高阶函数对树执行某些操作，但是当我已经对它进行排序时，这似乎是一种浪费。

如何访问这棵树的根节点？

原文

I have a canonical tree in F#, i.e by declaring

type binaryTree = 
    | Leaf
    | Node of binaryTree * float * binaryTree

and then using a recursive function to make the tree

let rec makeTree tree element = 
    match element, tree with
        | x, Leaf -> Node(Leaf,x,Leaf)
        | x, Node(l,y,r) -> Node(l,y, (makeTree r x))

This is all fine. Now I want to sort the tree so that at each node, the value of the node is smaller than the value of all its children. I can imagine doing this. However, I want to then take the first element of the tree. That is, I want to treat the tree like a queue. The only examples I have seen with trees use higher-order functions to do something with the tree, but this seems like a waste when I have already sorted it.

How can I access the root node of this tree?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

↙厌世 2024-11-10 20:10:11

怎么样：

let rootValue (Node(_,v,_)) = v

如果树是空的，这将抛出异常。或者：

let tryGetRootValue = function
| Node(_,v,_) -> Some v
| _ -> None

这总是会成功，但会返回 float 选项 而不是 float。

How about this:

let rootValue (Node(_,v,_)) = v

This will throw an exception if the tree is empty. Alternatively:

let tryGetRootValue = function
| Node(_,v,_) -> Some v
| _ -> None

This will always succeed, but will return a float option rather than a float.

回复收藏 0 原文

肤浅与狂妄 2024-11-10 20:10:11

问题有点不清楚。据我了解，您将有一棵树，其中节点的值小于其子节点的值。（您可以通过对树进行排序或编写一个不同的函数来构造树以使其成立，从而实现这一点。）

要实现采用树的第一个（最小）元素的函数，您需要删除根（即最小），然后合并您将得到的两棵树。这可以通过将两个根中较小的一个作为新根并递归地合并您将得到的新树来完成。下面的代码片段应该可以解决问题：

let rec merge t1 t2 = 
  match t1, t2 with
  | Leaf, t | t, Leaf -> t // Merging a tree and a leaf gives the tree
  | (Node(ll, x1, lr) as t1), (Node(rl, x2, rr) as t2) ->
      // When merging two trees, take the smaller root as a new root
      // This gives you three new trees, so two of them must be recursively merged
      if x1 < x2 then Node(merge ll lr, x1, t2)
      else Node(t1, x2, merge rl rr)

let rec tryTake tree = 
  match tree with
  | Leaf -> None
  | Node(t1, y, t2) -> Some(y, merge t1 t2)

The question is a bit unclear. As I understand it, you'll have a tree where the value of node is smaller than the value of its children. (Which you can implement by sorthing the tree or by writing a different function that constructs it such that this is true.)

To implement a function that takes the first (smallest) element of the tree, you need to remove the root (which is smallest) and then merge the two trees you'll get. This can be done by taking the smaller of the two roots as the new root and recursively merging the new trees you'll get. The following snippet should do the trick:

let rec merge t1 t2 = 
  match t1, t2 with
  | Leaf, t | t, Leaf -> t // Merging a tree and a leaf gives the tree
  | (Node(ll, x1, lr) as t1), (Node(rl, x2, rr) as t2) ->
      // When merging two trees, take the smaller root as a new root
      // This gives you three new trees, so two of them must be recursively merged
      if x1 < x2 then Node(merge ll lr, x1, t2)
      else Node(t1, x2, merge rl rr)

let rec tryTake tree = 
  match tree with
  | Leaf -> None
  | Node(t1, y, t2) -> Some(y, merge t1 t2)

回复收藏 0 原文

~没有更多了~