2017-10-31 15 views
0

Ich lerne OCaml für eine Klasse und erhielt die Aufgabe, das Spiegelbild eines Binärbaums zu berechnen. Ich bin ganz fest und bin nicht sicher, wie man überhaupt anfangen ...OCaml Binary Tree Spiegelbild

type btree = Empty | Node of int * btree * btree 
;; 

let mirror : btree -> btree 
    = fun t -> (* Code *) 

Probeneingang:

let tree1 = Node(1, Node(2, Node(3, Empty, Empty), Empty), Node(4, Empty, Empty)) 
;; 

Beispielausgabe:

mirror tree1 = Node(1, Node(4, Empty, Empty), Node(2, Empty, Node(3, Empty, Empty))) 
;; 
+1

https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions – gallais

+1

mit etwas beginnen einfach: was der Code sein könnte Spiegeln (1, leer, leer)? Knoten (1, Knoten (2, leer, leer), leer)? und generalisiere dann (siehe die Antwort von Jin unten). Veröffentlichen Sie Ihre Versuche - Sie haben dann eine größere Chance, Hilfe zu bekommen. –

+1

Normalerweise würden Sie in ML Mustervergleiche verwenden, aber es ist interessant, wie Sie (oder Ihr Lehrer) das Beispiel geben, das an [s-Ausdrücke] erinnert (https://en.wikipedia.org/wiki/Cons). – PieOhPah

Antwort

2

Verwenden Sie die match Funktion.

Sie können match auf die Struktur des Werts, wie durch seinen Typ definiert. In Ihrem Beispiel wird ein Wert des Typs btree mit dem Empty-Konstruktor oder einem Tupelkonstruktor von Node of int * btree * btree erstellt. Sie sollten mit etwas am Ende wie folgt:

... 
match t with 
| Node (num, lt, rt) -> (* do something to switch the subtrees, and mirror the subtrees themselves *) 
| Empty -> (* do nothing *) 
... 

und da die mirror Funktion vom Typ ist btree -> btree, jedes Ihrer Match Fällen müssen einen gültigen Wert vom Typ btree zurück.

See: http://ocaml.org/learn/tutorials/data_types_and_matching.html#Pattern-matching-on-datatypes