與價值觀

Question

如果讓我們說填補了正常的二叉樹ML：

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

我將如何去填充一個二叉樹（不是二叉搜索樹，其中左邊是比根小右大）。只是插入到二叉樹中每個節點的列表中的值。

Answer 1

Here is an answer在Java中完成相同的問題。這可能會有所幫助:)。

Answer 2

您使用您聲明的值構造函數。

如果我們假設一下，如果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)) 

Answer 3

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