如果让我们说填补了正常的二叉树ML:与价值观
datatype bin_tree = Empty |
Node of value * bin_tree * bin_tree
我将如何去填充一个二叉树(不是二叉搜索树,其中左边是比根小右大)。只是插入到二叉树中每个节点的列表中的值。
如果让我们说填补了正常的二叉树ML:与价值观
datatype bin_tree = Empty |
Node of value * bin_tree * bin_tree
我将如何去填充一个二叉树(不是二叉搜索树,其中左边是比根小右大)。只是插入到二叉树中每个节点的列表中的值。
Here is an answer在Java中完成相同的问题。这可能会有所帮助:)。
我很抱歉地说,但你不能再从 的真相中得到进一步的了解。这个答案是(完全)无用的,特别是在这个 上下文中。 – 2011-10-30 18:49:01
您使用您声明的值构造函数。
如果我们假设一下,如果value
是int
代替,那么我们比如有树
1
/\
2 4
/
3
由下式表示:
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))
这不是真的可能t o帮助你,而不知道你如何从给定的列表中构建你的树。但是,这是一个创建平衡树的例子。它采用第一个元素并将其用作节点值,然后通过将“左”列表中的所有“偶”元素以及所有“右‘名单奇”中的元素’:
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
塞巴斯蒂安给了一个很好的例子,下面,为如何构建一个特定的树,然而,构建从这样的`bin_tree`任何整数列表都要求您给出一个算法或解释,说明如何构建树。 – 2011-10-30 18:13:35