a) 2te, 4te

b) 1te, 2te

c) 2te (O(n log n))

d) 2te, 3te Antwort

e) 1te und 4te

f) 1te, 4te

g) 1te, 4te

h) 1te und 3te

a)
Linksvollständiger Binärbaum:

            S
           / \
          U   C
         / \
        H   E

Binärer Suchbaum:

            S
           / \
          C   U
           \
            H
           /
          E

b)
(i) ^

(ii) ^

(iii) ^
c)
(i) pre-order: E → N → J → H → O → O → D
(ii) in-order: J → N → O → H → E → D → O
(iii) post-order: J → O → H → N → D → O → E

d)
(i) E anstelle von F ??

           E
          / \
         B   G
        / \   \
       A   C   H
            \
             D

(ii) C anstelle von B ??

           A
            \
             C
              \
               D
                \
                 E

a)
{A, B, C, D, E}
{A, B, D, E}
{A, B, C, E}
{A, B, C, D}
{F, G, H}
{A, B, C}
{A, B, E}

b)

Endergebnis: 13 | 0 | 5 | 11 | 3

c)
F –(7)–> B –(5)–> C –(6)–> D –(2)–> A
Weglänge: 7 + 5 + 6 + 2 = 20

d)

Loesung uebernommen aus dem Forum, eventuell gegenchecken https://fsi.informatik.uni-erlangen.de/forum/thread/12419-Backtracking-SS14

	static boolean exists(boolean[][] brd, int r, int c) {
		if(brd[r] == null || brd[r].length < 1) {
			return false;
		}
		if(r >= brd.length || c >= brd[r].length || r < 0 || c < 0) {
			return false;
		}
		return true;
	}
 
	static int[][] allocateSolutionArray(boolean[][] brd, int mrl) {
		int[][] sol = new int[brd.length][mrl];
		for(int i = 0; i < brd.length; i++) {
			for(int j = 0; j < mrl; j++) {
				if(exists(brd, i, j)) { //Hier noch mit &&brd[i][j] verunden
					sol[i][j] = 0;
				} else {
					sol[i][j] = -1;
				}
			}
		}
		return sol;
	}
 
        //Achtung die folgende Implementierung enthaelt fehler! Lieber die Implementierung aus 
        //<<Code zum Selber Testen>> verwenden oder weiter scrollen
	static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) {
		int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 },
				{ r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } };
		if(sol[r][c] >= 1) {
			return false;
		}
		if(n == tf) {
			sol[r][c] = n;
			return true;
		}
		sol[r][c] = n;
		for(int k = 0; k < jumps.length; k++) {
			if(exists(brd, jumps[k][0], jumps[k][1])) {
				if(solve(brd, sol, tf, jumps[k][0], jumps[k][1], n + 1)) {
					return true;
				}
			}
		}
		sol[r][c] = 0;
		return false;
	}

>>>code zum selber testen<<<

a) *

	public static boolean exists(boolean[][] brd, int r, int c) {
 
		if (r < 0 || c < 0 || r >= brd.length || (brd[r] == null || c >=  brd[r].length))
			return false;
 
		return true;
	}

b) *

  public static int[][] allocateSolutionArray(boolean[][] brd, int mrl) {
		int[][] sol = null;
 
		sol = new int[brd.length][mrl];
		for (int y = 0; y < brd.length; y++) {
			for (int x = 0; x < mrl; x++) {
 
				if (x < brd[y].length && !brd[y][x]) {
					sol[y][x] = -1;
 
				} else if (x >= brd[y].length) {
					sol[y][x] = -1;
				}
			}
		}
 
		return sol;
	}

c) Annahme: P={r, c innerhalb von sol-Array}

public static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) {
		int[][] jumps = { { r + 2, c - 1 }, { r + 1, c - 2 }, { r - 1, c - 2 }, { r - 2, c - 1 }, { r - 2, c + 1 },
				{ r - 1, c + 2 }, { r + 1, c + 2 }, { r + 2, c + 1 } };
 
 
		if (n == tf) {
			sol[r][c] = n; // Letze Möglichkeit z.B. Start ist einzigste Möglichkeit (Letzten Sprung machen -> fertig)			
			return true;
		}
 
		for (int[] jump : jumps) {
			if (exists(brd, jump[0], jump[1]) && sol[jump[0]][jump[1]] == 0) {
				sol[r][c] = n;
				if (solve(brd, sol, tf, jump[0], jump[1], n + 1)) {
					return true;
				}
				sol[r][c] = 0;
			}
		}
		return false;
	}

a) Das Element 0 wird im nächsten Schritt versickert. Daher werden die Kindelemente 5 und 2 verglichen. 5 ist größer, daher wird 5 mit 0 verglichen. 5 ist größer, weshalb 5 und 0 getauscht werden.

    => Kreuz bei Stelle 2, 5 und 6
    => Resultat: { 6, 7, 5, 3, 1, 0, 2 }

b) Ergebnis: { 6, 3, 5, 2, 1, 0, 7 }

c)

	void reheap(W[] w, Comparator<W> c, int i, int k) {
		int leftId = 2 * i + 1;
		int rightId = leftId + 1;
		int kidId;
 
		if(leftId <= k) {
			if(rightId > k || c.compare(w[leftId], w[rightId]) > 0) {
				kidId = leftId;
			} else {
				kidId = rightId;
			}
			if(c.compare(w[kidId], w[i]) > 0) {
				swap(w, i, kidId);
				reheap(w, c, kidId, k);
			}
		}
	}

d)

void heapSort(W[] w, Comparator<W> c) {
	int n = w.length;
	
	// Phase 1: Max-Heap-Eigenschaft herstellen
	//          (siehe Teilaufgabe a)
	for(int i = n / 2 - 1; i >= 0; i--) {
		reheap(w, c, i, n-1); // Beide Grenzen inklusiv
	}
	
	// Phase 2: jeweils Maximum entnehmen und sortierte Liste am Ende aufbauen
	//          (siehe Teilaufgabe b)
	for(int i = n - 1; i > 0; i--) {
		swap(w, 0, i);
		reheap(w, c, 0, i - 1);
	}
}
      

LinkedList<Node> count(String s) {
		assert s != null : new IllegalArgumentException();
		HashMap<Character, Node> map = new HashMap<>();
		for(char c : s.toCharArray()) {
			if(map.get(c) == null) {
				map.put(c, new Node(c, 1));
			} else {
				int value = map.get(c).f += 1;
                                map.put(c, value);
			}
		}
		return new LinkedList<>(map.values());
	}
 
	void merge(LinkedList<Node> nodes) {
		if(nodes.size() > 1) {
			Collections.sort(nodes);
			Node zero = nodes.removeFirst();
			Node one = nodes.removeFirst();
			nodes.addFirst(new Node(zero, one));
			merge(nodes);
		}
	}
 
	String decode(Node root, String b) {
		assert (root != null && b != null) : new IllegalArgumentException();
		return dec(root, root, b);
	}
 
	String dec(Node root, Node node, String b) {
		if(b.length() < 1 && root != node) {
			throw new IllegalArgumentException();
		}
		if(b.length() < 1) {
			return "";
		}
		if(b.charAt(0) == '0') {
			node = node.zero;
		} else if(b.charAt(0) == '1') {
			node = node.one;
		} else {
			throw new IllegalArgumentException();
		}
		if(node == null) {
			throw new IllegalArgumentException();
		}
		if(node.one == null && node.zero == null) {
			return node.c + dec(root, root, b.substring(1));
		} else {
			return dec(root, node, b.substring(1));
		}
	}