2011-02-17 81 views
0

如果让我们说填补了正常的二叉树ML:与价值观

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

我将如何去填充一个二叉树(不是二叉搜索树,其中左边是比根小右大)。只是插入到二叉树中每个节点的列表中的值。

+0

塞巴斯蒂安给了一个很好的例子,下面,为如何构建一个特定的树,然而,构建从这样的`bin_tree`任何整数列表都要求您给出一个算法或解释,说明如何构建树。 – 2011-10-30 18:13:35

回答

-2

Here is an answer在Java中完成相同的问题。这可能会有所帮助:)。

+2

我很抱歉地说,但你不能再从 的真相中得到进一步的了解。这个答案是(完全)无用的,特别是在这个 上下文中。 – 2011-10-30 18:49:01

4

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

如果我们假设一下,如果valueint代替,那么我们比如有树

 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)) 
1

这不是真的可能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