Methode setMaximum PostOrder

Hacer

Aktives Mitglied
Ich muss eine Methode setMaximum erstellen und muss hier einen PostOrder-Tiefendurchlauf nutzen. Wenn ich es aber so implementiere dann bekomme ich aber als Ergebnis genau das Gegenteil.

Java:
public void setMaximum(){
        setMaximum(top.getNumber(), top);
    }
    private void setMaximum(int number, BinaryTreeNode node){
        if(node==null){
            return;
        }
      
      
        if(node.number<number)
            node.number=number;
        setMaximum(node.getNumber(), node.getSmaller());
        setMaximum(node.getNumber(), node.getLarger());
      
    }
 
Stell doch nicht immer alles ohne Kontext und ohne Plan hier rein: Wie man Fragen richtig stellt!

Erstens: Aufgabenstellung hinzuposten
Zweitens: Deinen ganzen lauffähigen Code dazu in Code-Tags posten: [code=java]//JAVA CODE[/code]
Drittens: Deine Ansätze beschreiben und deine Fehlermeldungen dazulegen

Das hier ist kein "hier-hast-du-bitte-mach" Forum, sondern es wird hier Eigenleistung gefordert. Also kurzum: Bei konkreten Fragen gibts konkrete Antworten.
 
@Flown Ich habe hier den Code ja selber erstellt, ich weiß nur nicht, wie man ein PostOrder-Tiefendurchlauf implementiert. In den Vorlesungsfolien gibt es ein Beispiel und ich habe mich daran gerichtet nur als Ergebnis bekomme ich ein PreOrder (und wenn ich es nach meiner Meinung als PreOrder implementiere, dann kommt als Ergebnis ein PostOrder) Binärbaum.🙁
 
.... ich habe mich daran gerichtet nur als Ergebnis bekomme ich ein PreOrder (und wenn ich es nach meiner Meinung als PreOrder implementiere, dann kommt als Ergebnis ein PostOrder) Binärbaum.🙁
Hm schon mal beide Implementierungen verglichen und geschaut welchen Unterschied es gibt? Vl hast du auch nur ein Verständnisproblem und verwechselst die beiden?
 
@Joose Das Beispiel aus den Vorlesungsfolien. Es geht ja dadrum, ob setMaximum am Anfang oder am Ende steht. Dementsprechend ändert sich auch das Ergebnis.
Java:
private void dfsPostOrder(int n){
if(leftTree!=null) leftTree.dfsPostOrder(n+1);
if(rightTree!=null) rightTree.dfsPostOrder(n+1);
System.out.println("Ebene" +n+ ":" +value);
 
Java:
public class BinaryTreeNode {

    int            number; // Nutzlast
    BinaryTreeNode    smaller; // links
    BinaryTreeNode    larger;  // rechts
   
    public BinaryTreeNode(int number){
        this.number    = number;
    }
   
    public int getNumber(){
        return number;
    }
   
    public BinaryTreeNode getSmaller(){
        return smaller;
    }
   
    public void setSmaller(BinaryTreeNode smaller){
        this.smaller = smaller;
    }
   
    public BinaryTreeNode getLarger(){
        return larger;
    }
   
    public void setLarger(BinaryTreeNode larger){
        this.larger = larger;
    }
}
Java:
public class BinaryTree {

    BinaryTreeNode top; // Wurzel des Binaeren Suchbaums

    public BinaryTree() {
        top = null;
    }

    /*
     * BEGINN des zu implementierenden Bereichs
     */

    /*
     * Mit dieser Methode soll ein neuer Knoten mit der durch den Parameter
     * number gegebenen Zahl in den Baum eingefuegt werden. Die vorhandene
     * Struktur des Baumes soll dabei nicht geaendert werden und die neue Zahl
     * als Blatt (Knoten ohne Nachfolger) im Baum zu finden sein. Ist die Zahl
     * bereits im Baum vorhanden, soll nichts geschehen.
     *
     * Beispiel: 5 / \ 2 17 / / \ -3 8 20
     *
     * Aufruf von Tree.insert(4)
     *
     * 5 / \ 2 17 / \ / \ -3 4 8 20
     */

    public void insert(int number) {

        // oeffentliche Methode zum Aufrufen und behandeln der Sonderfaelle
        // am Anfang, z.B. Behandlung des Verweises top

        // Abfrage ist der Baum leer (top==null?)

        if (top == null) {
            // Baum leer und das Element mit number muss erzeugt werden
            // und top darauf verweisen
            top = new BinaryTreeNode(number);
        } else {
            insert(number, top);
        }

    }

    private void insert(int number, BinaryTreeNode knoten) {
        // Methode, die die meiste Arbeit erledigt
        // betrachte den Knoten des BinaryTree knoten
        // 1. Fall: number schon vorhanden -> fertig, nix tun und beenden
        // 2. Fall: number ist kleiner als knoten.number
        // -> links weiter machen, aber nur, wenn der Teilbaum links (smaller)
        // nicht leer ist!
        // sonst: neuen Knoten mit number als Inhalt links anfuegen
        // 3. Fall: number ist groesser als knoten.number dann analog mit
        // rechtem Teilbaum (larger)

        // Algorithmus stellt insgesamt sicher, dass immer gilt knoten !=null
        // !!!

        if (number == knoten.number) {
            // 1. Fall -> tu nix & beenden
            return;
        } else {
            // 2. Fall oder 3. Fall
            if (number < knoten.number) {
                // also 2. Fall
                if (knoten.smaller != null) {
                    // linker Teilbaum (smaller) ist nicht leer und dann dort
                    // rekursiv weiter machen
                    insert(number, knoten.smaller);
                } else {
                    // 2. Fall und linker Teilbaum ist leer(smaller == null)
                    // dann einfuege-Stelle gefunden und neuen Knoten erzeugen
                    knoten.smaller = new BinaryTreeNode(number);
                }
            } else {
                // hier also mit Sicherheit 3. Fall: number > knoten.number
                if (knoten.larger != null) {
                    // rechter Teilbaum(larger) ist nicht leer und dann dort
                    // rekursiv weiter machen
                    insert(number, knoten.larger);
                } else {
                    // 3. Fall und rechter Teilbaum (larger) == null
                    knoten.larger = new BinaryTreeNode(number);
                }
            }
        }
    }

    /*
     * Diese Methode soll die maximale Tiefe eines Baumes zurueckgeben. Die
     * maximale Tiefe ist die Laenge des weitesten Weges den man von der Wurzel
     * des Baumes zu einem Blatt zuruecklegen kann.
     *
     * Beispiel: 5 / \ 2 17 / -3
     *
     * Die maximale Tiefe wird in diesem Baum entlang des Pfades 5 -> 2 -> -3
     * erreicht. Der Wert betraegt 3. Falls der Baum kein Element enthaelt und
     * damit leer ist, soll die zurueckgegebene Tiefe 0 sein.
     */

    public int maxDepth() {
        if (top == null) { // der leere Baum hat die Tiefe 0
            return 0;
        } else {
            return maxDepth(top);
        }
    }

    private int maxDepth(BinaryTreeNode knoten) {
        if (knoten == null) { // der leere Teilbaum hat die Tiefe 0
            return 0;
        } else { // Maximum der Tiefe der linken und rechten Teilbaeume +1 ist
                    // die
                    // Tiefe dieses Teilbaums
                    // besorge die Tiefe des linken Teilbaums
            int linketiefe = maxDepth(knoten.smaller);
            // besorge die Tiefe des rechten Teilbaums

            // nun berechne das (Maximum der Tiefe von links und rechts) +1
            int rechtetiefe = maxDepth(knoten.larger);
            if (linketiefe < rechtetiefe) {
                return rechtetiefe + 1;
            } else {
                return linketiefe + 1;
            }
        }
    }

    public int nodeCount() {
        // 1. Fall ist der Baum leer?
        if (top == null) {
            return 0;
        } else {
            return nodeCount(top);
        }
    }

    private int nodeCount(BinaryTreeNode knoten) {
        // hole die Anzahl des linken Teilbaums
        // hole die Anzahl des rechten Teilbaums
        // 0addieren plus 1 und zurueckgeben

        if (knoten == null) {
            return 0;
        } else {
            return nodeCount(knoten.smaller) + nodeCount(knoten.larger) + 1;
        }
    }
private int sumOfElements() {
        if (top == null) {
            return 0;
        } else {
            return sumOfElements(top);
        }
    }

    public int sumOfElements(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }
        int summe = 0;
        summe = sumOfElements(node.getSmaller())
                + sumOfElements(node.getLarger()) + node.getNumber();
        return summe;
    }

public void setMaximum(){
        setMaximum(top.getNumber(), top);
    }
    private void setMaximum(int number, BinaryTreeNode node){
        if(node==null){
            return;
        }
        setMaximum(node.getNumber(), node.getSmaller());
        setMaximum(node.getNumber(), node.getLarger());
       
       
        if(node.number<number)
            node.number=number;
        //setMaximum(node.getNumber(), node.getSmaller());
        //setMaximum(node.getNumber(), node.getLarger());
       
    }
public void printBT() {
        printBT(0, top);
    }

    private void printBT(int indent, BinaryTreeNode kn) {
        if (kn != null) { // linken Teilbaum ausgeben
            printBT(indent + 1, kn.smaller);
            // nun den Knoten ausgeben, um indent Blank-Zeichen einruecken
            for (int i = 0; i < indent; i++) {
                System.out.print(" ");
            }
            System.out.println(kn.number);
            // nun den rechten Teilbaum ausgeben
            printBT(indent + 1, kn.larger);
        }

    }

    /*
     * ENDE des zu implementierenden Bereichs
     */

    public static void main(String[] args) {

        // int [] numbers = {10, 30, 5,-3, 7,15,11,17,99};

        BinaryTree derBaum = new BinaryTree();
        derBaum.insert(10);
        derBaum.insert(30);
        derBaum.insert(5);
        derBaum.insert(-3);
        derBaum.insert(7);
        //derBaum.insert(15);
        //derBaum.insert(11);
        //derBaum.insert(17);
        //derBaum.insert(99);
derBaum.setMaximum();
       
        derBaum.printBT();
        System.out.println("der Baum enthaelt  " + derBaum.nodeCount()
                + " Knoten und ist so tief:" + derBaum.maxDepth());
}}
 
@Flown die Methode soll dem Attribut jedes Knotens einen neuen Wert zuweisen. Der Wert muss das Maximum des gegenwärtigen Wertes und des Wertes Elternknotens sein. Man muss aufsteigend vorgehen.
 
Also postOrder heißt nichts anderes als:
Code:
Wenn Knoten != null ist, dann
... besuche linken Knoten
... besuche rechten Knoten
... führe Operation am aktuellen Knoten aus
Genau der Algorithmus aus deiner Vorlesung. Auch die Implementierung deines setMaximum ist hiermit richtig.
Was lässt dich glauben, dass deine Implementierung falsch ist?
 
Also auf Papier habe ich den Binärbaum gezeichnet und habe es dann mit den Ergebnissen verglichen und die Ergebnisse sind unterschiedlich.
 

Anhänge

  • 20160928_190039.jpg
    20160928_190039.jpg
    1,7 MB · Aufrufe: 20
Nein das meine ich nicht. Ich meine die Ergebnisse die ich auf dem Blatt bekomme, sind anders als die die ich bei der Implementation bekomme. Vielleicht ist ja mein Binärbaum falsch 😕
 
Nachdem du den Code hier gepostet hast, habe ich ihn ein wenig überarbeitet und kann dir sagen, dass du den Baum schon richtig implementiert hast.
Lass doch den Code mal laufen bei dir und kannst ja eventuell den Unterschied erkennen:
Java:
public class Test {
  public static void main(String... args) {
    BinaryTree binaryTree = new BinaryTree();
    int[] numbers = { 10, 30, 5, -3, 7/* , 15, 11, 17, 99 */ };
    for (int i : numbers) {
      binaryTree.insert(i);
    }
   
    System.out.println(binaryTree);
    System.out.println("NodeCount: " + binaryTree.nodeCount());
    System.out.println("MaxTreeDepth: " + binaryTree.maxDepth());
    System.out.println("SumOfElements: " + binaryTree.sumOfElements());
    System.out.println(binaryTree);
    binaryTree.setMaximum();
    System.out.println(binaryTree);
  }
 
}

class BinaryTree {
 
  private BinaryTreeNode root;
 
  public BinaryTree() {
    root = null;
  }
 
  public void insert(int number) {
    if (root == null) {
      root = new BinaryTreeNode(number);
    } else {
      insert(number, root);
    }
  }
 
  private void insert(int number, BinaryTreeNode node) {
    if (number < node.getNumber()) {
      BinaryTreeNode smaller = node.getSmaller();
      if (smaller == null) {
        node.setSmaller(new BinaryTreeNode(number));
      } else {
        insert(number, smaller);
      }
    } else if (node.number < number) {
      BinaryTreeNode larger = node.getLarger();
      if (larger == null) {
        node.setLarger(new BinaryTreeNode(number));
      } else {
        insert(number, larger);
      }
    }
  }
 
  public int maxDepth() {
    return root == null ? 0 : maxDepth(root);
  }
 
  private int maxDepth(BinaryTreeNode node) {
    return node == null ? 0 : Math.max(maxDepth(node.getSmaller()), maxDepth(node.getLarger())) + 1;
  }
 
  public int nodeCount() {
    return root == null ? 0 : nodeCount(root);
  }
 
  private int nodeCount(BinaryTreeNode node) {
    return node == null ? 0 : nodeCount(node.getSmaller()) + nodeCount(node.getLarger()) + 1;
  }
 
  public int sumOfElements() {
    return root == null ? 0 : sumOfElements(root);
  }
 
  private int sumOfElements(BinaryTreeNode node) {
    return node == null ? 0 : node.getNumber() + sumOfElements(node.getSmaller()) + sumOfElements(node.getLarger());
  }
 
  public void setMaximum() {
    setMaximum(root.getNumber(), root);
  }
 
  private void setMaximum(int number, BinaryTreeNode node) {
    if (node != null) {
      int nodeNumber = node.getNumber();
      setMaximum(nodeNumber, node.getSmaller());
      setMaximum(nodeNumber, node.getLarger());
      if (nodeNumber < number) {
        node.setNumber(number);
      }
    }
  }
 
  @Override
  public String toString() {
    return toString("", root, new StringBuilder()).toString();
  }
 
  private StringBuilder toString(String indent, BinaryTreeNode node, StringBuilder builder) {
    if (node != null) {
      builder.append(indent).append(node.getNumber()).append(System.lineSeparator());
      toString(indent + " ", node.getSmaller(), builder);
      toString(indent + " ", node.getLarger(), builder);
    }
    return builder;
  }
 
  class BinaryTreeNode {
   
    private int number;
    private BinaryTreeNode smaller;
    private BinaryTreeNode larger;
   
    public BinaryTreeNode(int number) {
      this.number = number;
      this.smaller = null;
      this.larger = null;
    }
   
    public int getNumber() {
      return number;
    }
   
    public void setNumber(int number) {
      this.number = number;
    }
   
    public BinaryTreeNode getSmaller() {
      return smaller;
    }
   
    public void setSmaller(BinaryTreeNode smaller) {
      this.smaller = smaller;
    }
   
    public BinaryTreeNode getLarger() {
      return larger;
    }
   
    public void setLarger(BinaryTreeNode larger) {
      this.larger = larger;
    }
  }
}
 
Zuletzt bearbeitet:
@Flown ich glaube jetzt verstehe ich es, aber trotzdem mal eine dumme Frage.🙄 Kann ich also die if-Anweisung mit System.out.println vergleichen 😀
 

Neue Themen


Zurück
Oben