Baumaufgabe - Probeklausur WS1617 Nr.7

Question

Comments

ist das richtig so?

Answer 1

Nein, der Code hat noch einige Fehler. Zum Beispiel:

- die Methode sollte nicht statisch sein
- das Array `ar` muss irgendwo (mit der richtigen Größe) erstellt werden
- getLeft und getRight waren in der Aufgabe nicht definiert
- die Schleife trägt in jeden zweiten Array-Eintrag die Markierung des aktuellen Knoten ein (Hinweis: ein weiterer Parameter für die aktuelle Einfüge-Position wäre hilfreich)

Sie können den folgenden Code benutzen, um Ihren Code mit dem Beispiel aus der Aufgabe zu testen:

import java.util.Arrays;

public class Tree {
  private TreeNode root;

  public void add(int x) {
    root = add(x, root);
  }

  private static TreeNode add(int x, TreeNode root) {
    if (root == null) {
      return new TreeNode(null, null, x);
    } else {
      if (x < root.mark) {
        root.left = add(x, root.left);
      } else if (x > root.mark) {
        root.right = add(x, root.right);
      } else { // root.mark == x
        // nothing to do
      }
      return root;
    }
  }

////////////////////////////////////////////////////////////////
// Ihre Lösung:

  public static int[] preorder() {
    return preorder(node, ar);
  }

  private int[] preorder(TreeNode node, int[] ar) {
    if(node == null){
        return ar;
    }
    for (int i=0;i<ar.length;i++){
        ar[i]=node.mark;
        i++;
    }
    preorder(node.getLeft(), ar);
    preorder(node.getRight(), ar);
  }
////////////////////////////////////////////////////////////////////////




  // main-Prozedur zum Testen:
  public static void main(String[] args) {
    Tree tree = new Tree();
    tree.add(7);
    tree.add(5);
    tree.add(3);
    tree.add(6);

    tree.add(10);
    tree.add(8);

    //             7
    //           /   \
    //         5       10
    //       /   \   /
    //      3     6 8

    int[] ar = tree.preorder();
    int[] expected = {7, 5, 3, 6, 10, 8};
    if (Arrays.equals(ar, expected)) {
      System.out.println("OK");
    } else {
      System.out.println("expected:");
      System.out.println(Arrays.toString(expected));
      System.out.println("got: ");
      System.out.println(Arrays.toString(ar));
    }
  }
}

class TreeNode {
  int mark;
  TreeNode left, right;
  TreeNode(TreeNode left, TreeNode right, int mark) {
    this.left = left;
    this.right = right;
    this.mark = mark;
  }
}

Comments

hier nun mein überarbeitetes Programm.
bei den Tests gibt er mir leider immer nur die erste Zahl aus(7), woran könnte das liegen?

public int[] preorder() {
      
      int[] ar = new int[height(root, 0)];
      preorder(root, ar, 0);
      return ar;
    }


    void preorder(TreeNode root, int[] ar, int counter) {

      if(root == null){
        return;
      }
      while(counter<=ar.length-1){
        ar[counter]=root.mark;
        counter++;
        preorder(root.left, ar, counter);
        preorder(root.right, ar, counter);
      }
      
    }
    int height(){
      return height(root, 0);
    }
    
    int height(TreeNode root, int sum){
      if(root == null){
          return sum;
      }
      sum++;
      height(root.left, sum);
      height(root.right, sum);
      return sum;
  }

---

1. Die Größe/Höhe wird falsch berechnet: Die Anweisung "sum++" ändert nur den lokalen Parameter, nicht die Variable in der Aufrufenden Funktion. Statt dessen sollte der Rückgabewert verwendet werden. Ein Beispiel ist die Prozedur height in https://softech.cs.uni-kl.de/se1/ws17/_media/offiziell/13_Baeume.pdf

2. Die Prozedur "void preorder" hat das gleiche Problem. Eine Schleife ist hier auch nicht notwendig, da die rekursiven Aufrufe schon alle Knoten des Baums besuchen sollten.

---

jetzt kommt [7,10,8] raus, also nur die Wurzel und der rechte Teilbaum, woran liegt das?
darf ich die Funktion Math.max() in der Prüfung überhaupt benutzen, wenn ich die Höhe des Baumes brauche?

public int[] preorder() {
      
      int[] ar = new int[height(root)];
      preorder(root, ar, 0);
      return ar;
    }


    void preorder(TreeNode root, int[] ar, int counter){

      if(root == null){
        return;
      }
      
        ar[counter++]=root.mark;
        
        preorder(root.left, ar, counter);
        preorder(root.right, ar, counter);
        
            
    }
    
    int height(TreeNode root){
      if(root == null){
          return 0;
      }
      return 1 + Math.max(height(root.left), height(root.right));
  }

---

Für beide rekursiven Aufrufe wird der gleiche counter-Wert übergeben. Beim zweiten Aufruf sollte aber der neue Wert verwendet werden. Dafür kann man zum Beispiel den Rückgabewert der Prozedur verwenden.