哈斯克爾轉換有序列表的成平衡樹〜代碼說明

Question

我有以下運動：

定義功能list2tree一個給定的有序列表轉換爲平衡樹 - 右邊的高度和左子樹這種樹的任何節點都可以通過最多相差1

誰能解釋這段代碼，它是如何工作的？另外我怎樣才能在控制檯中測試樹？

解決方案：

data Tree a = Leaf a 
      | Node a (Tree a) (Tree a) 
      | Null 

list2tree [] = Null 
list2tree [x] = Leaf x 
list2tree list = Node x (list2tree ltx) (list2tree gtx) 
       where 
       m = length list `div` 2 
       x = list !! m 
       ltx = take m list 
       gtx = drop (m+1) list 

Answer 1

什麼這個功能確實走的是中間元素在列表中，把它作爲節點然後迭代該列表的每半。 m是中間元件的位置，ltx（我認爲是指「低於x」）是所有元件低，比x和gtx都高於X的元素。

Answer 2

爲了在GHCI進行測試，使Tree的Show一個實例：

data Tree a = Leaf a 
      | Node a (Tree a) (Tree a) 
      | Null 
      deriving (Show) 

開始從命令行GHCI，並加載包含Tree和list2tree該文件。我把它叫做44520938.hs：

Prelude> :load 44520938.hs 
[1 of 1] Compiling Answer   (44520938.hs, interpreted) 
Ok, modules loaded: Answer. 

現在你可以調用各種輸入列表的功能測試：

*Answer> list2tree [] 
Null 
*Answer> list2tree [1] 
Leaf 1 
*Answer> list2tree [1, 2] 
Node 2 (Leaf 1) Null 
*Answer> list2tree [1, 2, 3] 
Node 2 (Leaf 1) (Leaf 3)