用值填充 ML 中的普通二叉树

发布于 2024-10-18 04:37:59 字数 179 浏览 3 评论 0原文

让我们说：

datatype bin_tree = Empty |
                    Node of value * bin_tree * bin_tree

我将如何填充二叉树（不是左比根小而右比根大的二叉搜索树）。只是插入二叉树中每个节点的列表中的值。

原文

Where let's say:

datatype bin_tree = Empty |
                    Node of value * bin_tree * bin_tree

How would I go about filling a binary tree (not a binary search tree where left is smaller than root and right bigger). Just values from a list inserted at each node in a binary tree.

分享到QQ

分享到微博

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

发布评论

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

眼趣 2024-10-25 04:37:59

您使用已声明的值构造函数。

如果我们暂时假设 value 是 int，那么我们可以将树

表示为：

Node (1,
    Node (2,
        Node (3, Empty, Empty),
        Empty
    ),
    Node (4, Empty, Empty)
)

或者，等效地，在一行上：

Node (1, Node (2, Node (3, Empty, Empty), Empty), Node (4, Empty, Empty))

You use the value constructors you've declared.

If we assume for a moment that value is int instead, then we for instance have that the tree

is represented by:

Node (1,
    Node (2,
        Node (3, Empty, Empty),
        Empty
    ),
    Node (4, Empty, Empty)
)

Or, equivalently, on one line:

Node (1, Node (2, Node (3, Empty, Empty), Empty), Node (4, Empty, Empty))

回复收藏 0 原文

演出会有结束 2024-10-25 04:37:59

如果不了解更多关于您希望如何根据给定列表构建树的信息，那么实际上不可能为您提供帮助。然而，这里有一个创建平衡树的示例。它采用第一个元素并将其用作节点值，然后通过采用“左”列表中的所有“偶数”元素和所有“ “右”列表中的奇数个元素：

datatype 'a bin_tree = Empty
                  | Node of 'a * 'a bin_tree * 'a bin_tree

fun list_split xs =
    let
      fun loop [] (left, right) = (rev left, rev right)
        | loop (x::y::xs) (left, right) = loop xs (x :: left, y :: right)
        | loop (x :: xs) (left, right) = loop xs (x :: left, right)
    in
      loop xs ([], [])
    end

fun built_tree [] = Empty
  | built_tree (x :: xs)  =
    let
      val (left, right) = list_split xs
      val left_tree = built_tree left
      val right_tree = built_tree right
    in
      Node (x, left_tree, right_tree)
    end

结果：

- built_tree [1,2,3,4,5,6,7,8,9];
val it =
  Node
    (1,Node (2,Node (4,Node (8,Empty,Empty),Empty),Node (6,Empty,Empty)),
     Node (3,Node (5,Node (9,Empty,Empty),Empty),Node (7,Empty,Empty)))
  : int bin_tree

It's not really possible to help you, without knowing more about how you wan't your tree constructed from a given list. However here is an example that creates a balanced tree. It takes the first element and uses it as the node value, and then it splits the rest of the list into two sub lists of equal size (if possible), by taking all "even" element in the "left" list and all "odd" elements in the "right" list:

datatype 'a bin_tree = Empty
                  | Node of 'a * 'a bin_tree * 'a bin_tree

fun list_split xs =
    let
      fun loop [] (left, right) = (rev left, rev right)
        | loop (x::y::xs) (left, right) = loop xs (x :: left, y :: right)
        | loop (x :: xs) (left, right) = loop xs (x :: left, right)
    in
      loop xs ([], [])
    end

fun built_tree [] = Empty
  | built_tree (x :: xs)  =
    let
      val (left, right) = list_split xs
      val left_tree = built_tree left
      val right_tree = built_tree right
    in
      Node (x, left_tree, right_tree)
    end

The result:

- built_tree [1,2,3,4,5,6,7,8,9];
val it =
  Node
    (1,Node (2,Node (4,Node (8,Empty,Empty),Empty),Node (6,Empty,Empty)),
     Node (3,Node (5,Node (9,Empty,Empty),Empty),Node (7,Empty,Empty)))
  : int bin_tree

回复收藏 0 原文