Wie übergebe ich einen Binärbaum für eine Liste von Listen in OCaml?

Question

Ich muss einen Binärbaum für eine Liste von Listen übergeben, weiß aber nicht weiter. Irgendein Vorschlag?

Answer 1

Der übliche Weg, um eine Baumstruktur (oder allgemeiner eine Gesamtstruktur) als Liste der Liste anzuzeigen, ist ihre "Pfaddarstellung". Sie können einen Binärbaum als Daten aller Pfade von der Wurzel bis zu den Blättern darstellen (Sie haben also so viele Pfade wie Blätter in Ihrem Baum).

Beispiel:

1. links, links
2. links, rechts, links
3. Links, Rechts, Rechts
4. Rechts:

    /\ 
       /\ 
       / \ 
       /\ /\ 
       /\ /\ 
        /\ 
   

   wie die folgende Liste dargestellt werden , Links, Links

5. Rechts, Links, Rechts, Links
6. rechts, links, rechts, rechts
7. rechts, rechts

Es gibt viele Variationen dieser Darstellung sind. Wenn zum Beispiel die Knoten Informationen übertragen, ist es einfacher, den Graphen als die Liste der Pfade zu jedem Knoten (und nicht nur zu den Blättern) darzustellen. Sie müssen diese Antwort wahrscheinlich anpassen, um Ihr spezielles Problem zu lösen.

Dies kann aufgebaut werden, indem Sie Ihren Baum in einer Tiefe-zuerst-Weise durchlaufen. Umgekehrt können Sie Ihren Baum dann rekursiv aus der Liste der Pfade rekonstruieren.

type binary_tree = 
    | Empty 
    | Node of binary_tree * binary_tree 

type branch = 
    | Left 
    | Right 

let rec to_paths tree = 
    match tree with 
    | Empty -> [[]] 
    | Node (left, right) -> 
     (List.map (fun l -> Left :: l) (to_paths left)) 
    @ (List.map (fun l -> Right :: l) (to_paths right)) 

let rec of_paths = function 
    | [[]] -> Empty 
    | l -> 
    let lefts, rights = List.partition (function 
     | [] -> failwith "of_paths: not at binary tree" 
     | Left :: _ -> true 
     | Right :: _ -> false) l 
    in 
    Node (of_paths (List.map List.tl lefts), 
      of_paths (List.map List.tl rights)) 

(* A little test : *)  
let tree = 
    Node (Node(Empty, Node (Empty, Empty)), 
     Node (Node(Empty, Node (Empty, Empty)), Empty)) 

let() = assert (tree = of_paths (to_paths tree))