OCaml的 - 一棵樹

我的樹類型的鏡像是OCaml的 - 一棵樹

type 'a tree = Tree of 'a * 'a tree list;;

我怎樣才能得到這樣的樹的鏡像？對於我來說，有一個孩子的名單是令人困惑的，因爲我不知道如何分別給每個孩子做遞歸，而沒有丟失父母的蹤跡，任何想法？

編輯：我一直想，我想我得到了解決：

let spec arbol = 
     match arbol with 
     Tree(a,[])-> Tree(a,[]) 
     | Tree(a,l)-> Tree(a, List.rev (
        let rec aux = function 
         Tree(a,[])::[]->Tree(a,[])::[] 
         | Tree(a,[])::l-> [Tree(a,[])]@(aux l) 
         | Tree(a,t)::[]-> [Tree(a, (List.rev (aux t)))] 
         | Tree(a,t)::l-> [Tree(a, (List.rev (aux t)))]@(aux l) 
        in aux l));;

我已經和這棵樹試了一下：

let p = Tree(1, [ 
    Tree(2,[]); 
    Tree(3, [ 
     Tree(6,[]); 
     Tree(7,[]) 
     ]); 
    Tree(4,[]); 
    Tree(5,[]) 
]);;

而且我得到了作爲# spec p;;

結果

-: int tree = Tree (1, [ 
       Tree (5,[]); 
       Tree (4,[]); 
       Tree (3,[ 
        Tree(7,[]); 
        Tree(6,[])]); 
       Tree (2,[]) 
       ])

所以我想我的功能按預期工作。讓我知道它是否不正確

來源

2014-01-12 horro

如果我理解你正在嘗試計算的函數，那麼只需要一行代碼就可以得到一個非常簡單的答案。

不幸的是，您的代碼引入了這麼多的案例，很難用眼睛來檢查。

它在我看來像你的aux功能是爲了計算樹列表的鏡像。但是，它不適用於空列表。如果您重寫aux以在空列表上工作，您可能會發現不需要這麼多不同的情況。特別是，你可以在你的內線比賽中移除你最外面的比賽和一半的情況。

事實上，你的aux函數（如果正確的話）完成所有工作。如果你正確地看，它可以使用aux的一切。

由於您使用List.rev，我假設您也可以使用List.map。這也是值得關注的。

更新

樹木本身是遞歸結構，所以尋找一個樹算法的時候，它常常有助於想象你會如何使用遞歸你的算法。在這種情況下，你可以問自己如何將樹的所有子樹的鏡像鏡像成整個樹的鏡像。

來源

2014-01-12 23:50:12

我明白你的意思，其實我已經重寫了它這樣的： '讓規範樹= \t \t讓REC AUX =功能 \t \t [] - > [] \t \t | Tree（a，t）:: l-> [Tree（a，（List.rev（aux t）））] @（aux l） \t in List.hd（aux [tree]）;; ' 我覺得更清楚了，所有的情況也是可以考慮的。我正在尋找使用'List.map'，但我真的不知道如何在我的代碼中使用它。 – horro

你應該真的使用'List.rev_map'。然後這個函數是單線程的，'let rec spec（Tree（a，ts））= Tree（a，List.rev_map spec）' – nlucaroni

這就是我正在談論的解決方案。但OP可能會更好地弄清楚。 –

OCaml的 - 一棵樹

回答

相關問題