import java.util.LinkedList;
import java.util.Queue;

public class Traversierung {
	public static void preOrder(Node knoten) {
		// 1. Wert des Knotens ausgeben
		System.out.print(knoten.wert + " ");

		// 2. Rekursiv für linken Teilbaum ausführen
		if (knoten.links != null)
			preOrder(knoten.links);

		// 3. Rekursiv für rechten Teilbaum ausführen
		if (knoten.rechts != null)
			preOrder(knoten.rechts);
	}

	public static void inOrder(Node knoten) {
		// 1. Rekursiv für linken Teilbaum ausführen
		if (knoten.links != null)
			inOrder(knoten.links);

		// 2. Wert des Knotens ausgeben
		System.out.print(knoten.wert + " ");

		// 3. Rekursiv für rechten Teilbaum ausführen
		if (knoten.rechts != null)
			inOrder(knoten.rechts);
	}

	public static void postOrder(Node knoten) {
		// 1. Rekursiv für linken Teilbaum ausführen
		if (knoten.links != null)
			postOrder(knoten.links);

		// 2. Rekursiv für rechten Teilbaum ausführen
		if (knoten.rechts != null)
			postOrder(knoten.rechts);

		// 3. Wert des Knotens ausgeben
		System.out.print(knoten.wert + " ");
	}

	public static void levelOrder(Node knoten) {
		// 1. Schlange anlegen
		Queue<Node> queue = new LinkedList<>();

		// 2. Wurzel zur Schlange hinzufügen
		queue.add(knoten);

		// 3. Solange die Schlange nicht leer ist...
		while (!queue.isEmpty()) {
			// 4. Linken und rechten Kindknoten zur Schlange hinzufügen
			knoten = queue.peek();
			if (knoten.links != null) queue.add(knoten.links);
			if (knoten.rechts != null) queue.add(knoten.rechts);
			
			// 5. Wert des Hauptknotens ausgeben
			System.out.print(knoten.wert + " ");
			
			// 6. Hauptknoten aus der Schlange entfernen
			queue.poll();

			// weiter bei 3....
		}
	}

	public static void main(String[] args) {
		// Beispielbaum aus der PDF-Datei
		Node wurzel = new Node(3);
		wurzel.links = new Node(1);
		wurzel.links.links = new Node(13);
		wurzel.rechts = new Node(10);
		wurzel.rechts.links = new Node(11);
		wurzel.rechts.rechts = new Node(16);
		wurzel.rechts.rechts.links = new Node(15);
		wurzel.rechts.rechts.rechts = new Node(2);

		System.out.print("Pre-order: ");
		preOrder(wurzel);
		System.out.println();
		// 3 1 13 10 11 16 15 2

		System.out.print("In-order: ");
		inOrder(wurzel);
		System.out.println();
		// 13 1 3 11 10 15 16 2

		System.out.print("Post-order: ");
		postOrder(wurzel);
		System.out.println();
		// 13 1 11 15 2 16 10 3

		System.out.print("Level-order: ");
		levelOrder(wurzel);
		System.out.println();
		// 3 1 10 13 11 16 15 2
	}
}

class Node {
	int wert;
	Node links;
	Node rechts;

	Node(int wert) {
		this.wert = wert;
	}
}