Traversierungsverfahren Baum: LevelOrder

[Lights]

Guten Tag,
wie ist es möglich einen Baum im LevelOrder verfahren wiederzugeben ? Gelungen ist es mir bereits im Inorder/PreOrder und postOrder verfahren.

package com.provinzial.www.binaerbaum;

import java.util.ArrayList;
import java.util.List;


public class Binaerbaum {

    private Knoten wurzel;

    public void einfuegen(int ordbg) {
        Knoten neu = new Knoten(ordbg);

        if (wurzel == null) {
            wurzel = neu;
        }

        else {
            Knoten lfd = wurzel;
            boolean weiter = true;

            while (weiter) {
                if (ordbg > lfd.getOrdbg()) {
                    if (lfd.getRechts() != null) {
                        lfd = lfd.getRechts();
                    } else {
                        lfd.setRechts(neu);
                        weiter = false;
                    }
                } else {
                    if (lfd.getLinks() != null) {
                        lfd = lfd.getLinks();
                    } else {
                        lfd.setLinks(neu);
                        weiter = false;
                    }
                }
            }
        }

    }

    public List<Integer> inOrder() {
        List<Integer> liste = new ArrayList<>();
        inOrder(wurzel, liste);
        return liste;
    }

    private void inOrder(Knoten knoten, List<Integer> liste) {
        if (knoten != null) {
            inOrder(knoten.getLinks(), liste);
            liste.add(knoten.getOrdbg());
            inOrder(knoten.getRechts(), liste);
         
        }
    }

    public List<Integer> preOrder() {
        List<Integer> liste = new ArrayList<>();
        preOrder(wurzel, liste);
        return liste;

    }

    public void preOrder(Knoten knoten, List<Integer> liste) {
        if (knoten != null) {
            liste.add(knoten.getOrdbg());
            preOrder(knoten.getLinks(), liste);
            preOrder(knoten.getRechts(), liste);
         
        }
    }

    public List<Integer> postOrder() {
        List<Integer> liste = new ArrayList<>();
        postOrder(wurzel, liste);
        return liste;

    }

    public void postOrder(Knoten knoten, List<Integer> liste) {
        if (knoten != null) {
            postOrder(knoten.getLinks(), liste);
            postOrder(knoten.getRechts(), liste);
            liste.add(knoten.getOrdbg());
        
        }
    }
    public List<Integer> levelOrder() {
        List<Integer> liste = new ArrayList<>();
        levelOrder(wurzel, liste);
        return liste;

    }

    public void levelOrder(Knoten knoten, List<Integer> liste) {
        if (knoten != null) {
            postOrder(knoten.getLinks(), liste);
            postOrder(knoten.getRechts(), liste);
            liste.add(knoten.getOrdbg());
        
        }
    }
   
}

 

[httpdigest]

Für eine breadth-first Traversierung eines Baumes benötigst du eine Queue-Datenstruktur und kannst einen iterativen Algorithmus bauen. In die Queue fügst du am Anfang den Root-Knoten ein und gibst ihn aus (bzw. fügst ihn in deine Ergebnisliste ein). Dann lässt du eine Schleife laufen solange wie die Queue nicht leer ist. In jeder Schleifeniteration holst du dir den Knoten am Anfang der Queue und für jeden seiner Kinder fügst du das Kind hinten in die Queue ein und gibst das Kind aus. Das war's.

 

[Lights]

also ich bekomme das leider irgendwie nicht hin, muss ich mir dafür selber noch eine Queue klasse schreiben oder reicht dafür Java.util.Queue ?

 

[httpdigest]

java.util.Queue reicht.

 

[Lights]

okey danke, bin mittlerweile soweit an der Stelle

 public void levelOrder(Knoten knoten, List<Integer> liste) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(knoten.getOrdbg());
        liste.add(knoten.getOrdbg());
      
        while (queue.isEmpty() == false)
        {
          
        }
      
    }

Wobei ich mir nicht sicher bin ob oben knoten.getOrdbg() auch die Root ist und was in die While schleife kommt habe ich leier auch nicht richtig verstanden

Habe leider vorher nie mit Queues gerabeitet und musste mir dass jetzt erst kurz alles anlesen

 

[httpdigest]

Habe leider vorher nie mit Queues gerabeitet und musste mir dass jetzt erst kurz alles anlesen

Das ist doch total okay. Nur so lernt man indem man sich in neue Sachen einliest und ausprobiert.

 

[Lights]

Haha, das stimmt wohl

Komme jetzt an der Stelle trotzdem leider nicht weiter

 

[httpdigest]

Was ist denn ganz konkret genau das Problem, wo kommst du nicht weiter?
Es geht ja jetzt nur noch hierum: "In jeder Schleifeniteration holst du dir den Knoten am Anfang der Queue und für jeden seiner Kinder fügst du das Kind hinten in die Queue ein und gibst das Kind aus."

 

[Lights]

ganz genau, würde jetzt mit Queue.element oder .peek den erste Wert aus der Queue holen, weiß aber nicht ganu was ich damit machen soll bzw wohin ich den speichern soll, und von "
für jeden seiner Kinder fügst du das Kind hinten in die Queue ein und gibst das Kind aus." verstehe ich zwar den Sinn hab aber kein Plan wie ich das im Code umsetzten soll das es ja nicht mit getLinks oder getRechts funktioniert

 

[httpdigest]

hab aber kein Plan wie ich das im Code umsetzten soll das es ja nicht mit getLinks oder getRechts funktioniert

Diesen Satz verstehe ich nicht. Wieso soll es nicht mit getLinks und getRechts funktionieren?? Das sind doch genau die Kinder eines Knotens.

 

[Lights]

bin grade völlig raus, hatte mir gedacht dass das nicht geht weil ja bei der Level Order jede "Ebene" einzelnd abgearbeitet wird, aber hastschon recht es müsste damit eigentlich auch gehen.

Stimmt den das mit .peek / .element und was mache ich dann mit dem Wert ?

 

[httpdigest]

Nein, peek() ist falsch, da es ja nicht den Wert aus der Queue entfernt. Nehme einfach:
- https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html#add(E)
- https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html#remove()

und halte dich einfach an die Beschreibung des Algorithmus.

 

[Lights]

Achso, ich hatte "rausholen" vorhin falsch verstanden, also geht es nur darum das der oberste Wert entfertn wird und in die Liste eingetragen wird oder ?

zudem versuche ich jetzt die Kinder mit Queue.add() hinzuzufügen, aber Queue.add(knoten.getLinks) funktioniert leider wirklich nicht

 

[httpdigest]

zudem versuche ich jetzt die Kinder mit Queue.add() hinzuzufügen, aber Queue.add(knoten.getLinks) funktioniert leider wirklich nicht

Was hast du denn genau versucht und was meinst du genau mit "funktioniert leider wirklich nicht". Bitte genauer sein!

 

[Lights]

 public void levelOrder(Knoten knoten, List<Integer> liste) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(knoten.getOrdbg());
        liste.add(knoten.getOrdbg());
      
        while (queue.isEmpty() == false)
        {
          
          int knoten1 = queue.remove();
          liste.add(knoten1);
          queue.add(knoten.getLinks());
           
        }
      
    }

Das funktioniert leider nicht dar getLinks bzw. Links vom Typ Knoten ist und kein int, dar Queue.add einen int erwartet

 

[httpdigest]

Warum denn Queue<Integer>? Deine Knoten sind doch keine Integers.

Und das Wort heißt "da" (im Sinne von "weswegen", "weil") und nicht "dar"

 

[Lights]

Stimmt, hatte ich so weil ich es am Anfang noch aus der Liste gecopied hatte, das geht jetzt natürlich auch, aber getOrdbg für die Wurzel funktioniert dann nicht mehr da es sich dabei um einen int handelt

 

[httpdigest]

Du musst zwischen den Daten in der Queue (deine Knoten) und dem, was du in deine Ergebnisliste füllen willst (der "payload" eines Knotens, also ein Integer) unterscheiden. Wenn du den Knoten in deine Ergebnisliste hinzufügst, musst du selbstverständlich dann eben nicht den Knoten, sondern seinen Payload hinzufügen.