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)

a)

static boolean exists(boolean[][] brd, int r, int c) {
    if (brd[r] == null || brd[r].length < 1) { // Zeilen null oder leer
        return false;
    } 
    if (r >= brd.length || c >= brd[r].length || r < 0 || c < 0) { // Indizes ausserhalb der Grenzen
        return false;
    }
    return true;
}

b)

static int[][] allocateSolutionArray(boolean[][] brd, int mrl) {
    int[][] = null;
    int[][] sol = new int[brd.length][mrl];
 
    for (int r = 0; r < brd.length; r++) {
        for (int c = 0; c < mrl; c++) {
            if (exists(brd, r, c) && brd[r][c]) { // Diese Felder duerfen betreten werden
                sol[r][c] = 0;
            } else {
                sol[c][c] = -1; // Felder mit -1 vorbelegen
            }
        }
    }
    return sol;
}

c)

static boolean solve(boolean[][] brd, int[][] sol, int tf, int r, int c, int n) {
    // possible targets from (r,c)
    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 } };
 
    //Basisfall, letzter Wert muss hier noch gesetzt werden
    if (n == tf) {
        sol[r][c] = n;
        return true;
    }
    for (int j = 0; j < jumps.length; j++) {
 
        // Wert setzen
        sol[r][c] = n 
 
        // Brett brd und Loesungsfeld sol pruefen
        if (exists(brd, jumps[j][0], jumps[j][1]) && sol[jumps[j][0]][jumps[j][1]] == 0) {
 
            // Rekursion
            if (solve(brd, sol, tf, jumps[j][0], jumps[j][1], n + 1)) {
                return true;
            }
            // Backtrack
            sol[r][c] = 0;
        }        
    }        
    return false;
}

Alternative:

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			
			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;
	}

>>>code zum selber testen<<<

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)

       //vorsicht! hier sind nicht alle faelle abgedeckt! was passiert bei rightId > w.length - 1 ? ggf mit Vorlesungsfolie 13 S.39 von ws18/19 gegenchecken!!!
	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()) {
			Node n = map.get(c);
			if(n != null) {
				//variable frequenz updaten
				n.f++;
			} else {
				//neuer node in die map
				map.put(c, new Node(c,1));
			}
		}
		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));
		}
	}