BinBaum rekursiv ausgeben

[jacko]

Hallo,

ich sitzte jetzt schon länger daran, die einzelnen Werte eines BinBaums rekursiv auszugeben.
Ich habe einen Binbaum schon erstellt, mir fehlt lediglich die Methode um die ganzen Knoten zu durchlaufen und sie absteigend von groß nach klein auf dem Screen auszugeben:


Folgender Baum:
9
/ \
3 12
/ \ \
0 5 13

Hier müsste also dann folgendes auf dem Bildschirm ausgegeben werden: 13 12 9 5 3 0

mein Baum bisher:

public class BinBaum<Int> {		
								
	private Integer k;
	private BinBaum<Integer> left;
	private BinBaum<Integer> right;
	
	public BinBaum(Integer k, BinBaum<Integer> left, BinBaum<Integer> right) {
		this.k=k;
		this.left=left;
		this.right=right;
	}

Wäre nett, wenn mir jemand bei der Methode helfen könnte, hab irgendwie nix passendes gefunden.

Vielen Dank.
Gruß
jacko

 

[SlaterB]

kein minimaler eigener Ansatz?
wie ist die Ausgabe wenn ein Baum keine Kinder hat, nur ein Blatt ist?

wie ist die Ausgabe wenn ein Baum ein 'right'-Kind hat?

 

[jacko]

Ich hatte jede Menge Ansätze, die waren nur alle Schrott muss ich leider sagen.

Falls der Baum leer ist, wird einfach Baum leer ausgegeben.
Falls der Baum nur einen Knoten(Wurzel) hat wird nur die Wurzel ausgegeben.

Ansonsten soll einfach wie oben beschrieben von groß nach klein ausgegeben werden.

 

[SlaterB]

> Falls der Baum leer ist, wird einfach Baum leer ausgegeben.
> Falls der Baum nur einen Knoten(Wurzel) hat wird nur die Wurzel ausgegeben.

das sind schon zwei korrekte aussagen, auch wenn noch der Code dazu fehlt

> Ansonsten soll einfach wie oben beschrieben von groß nach klein ausgegeben werden.

diese Aussage ist schlecht, sie hat so einen globalen Charakter,
du musst bei solchen Dingen immer nur an genau einen Knoten im Bauen denken

aus deinem Beispielbaum ergeben sich viele kleine Beispiele
9
/ \
3 12


3
/ \
0 5

12
\
13

überall ist das System gleich, immer das gleiche Verfahren,
wie ist die Ausgabe?
12 13 oder 13 12
3 5 oder 5 3
eigener Knoten, rechtes Kind oder rechtes Kind, eigener Knoten?

 

[jacko]

Die Methode soll quasi zuerst rechts entlang laufen (rechts, da ja hier die größeren Zahlen sind und links die kleineren) bis ganz runter, also über 9 zu 12 zu 13 und herausfinden, dass dies die höchste Zahl ist und diese ausgeben.
Dann wieder über 9 zu 12 und herausfinden, dass dies die nächste Zahl ist und 12 ausgeben.
Und dies immer so weiter bis rechts alles fertig ausgegeben wurde.
Dann die Wurzel ausgeben, also 9.
Und dann das ganze Verfahren links runter laufen.

Das ganze muss dann genau in dieser Reihenfolge ausgegeben werden: 13 - 12 - 9 - 5 - 3 - 0

Ansonsten weiß ich jetzt nicht genau was du meinst.

 

[SlaterB]

nun, weiter kann man da keine Tipps geben,
das Endergebnis ist also:

public class BinBaum
{

    private Integer k;
    private BinBaum left;
    private BinBaum right;

    public BinBaum(Integer k, BinBaum left, BinBaum right)
    {
        this.k = k;
        this.left = left;
        this.right = right;
    }

    public String getDescription()
    {
        String description = "";
        if (this.right != null)
        {
            description += this.right.getDescription();
        }
        description += k + ", ";
        if (this.left != null)
        {
            description += this.left.getDescription();
        }
        return description;
    }

    public static void main(String[] args)
    {
        BinBaum a = new BinBaum(13, null, null);
        a = new BinBaum(12, null, a);
        BinBaum b = new BinBaum(0, null, null);
        BinBaum c = new BinBaum(5, null, null);
        b = new BinBaum(3, b, c);
        b = new BinBaum(9, b, a);
        System.out.println(b.getDescription());
    }
}

 

[maki]

jacko,

es gibt nicht soviele Möglichekiten durch einen Baum zu wandern.

Hier ist eine Übersicht über die gängigsten Verfahren:
http://en.wikipedia.org/wiki/Tree_traversal

Also, findest du deine Art dort?
Wenn ja, welche wäre das?
Inorder, preorder, postorder oder gar level-order?

 

[jacko]

Ich kenn diese ganzen Ordnungen schon, aber weil davon keiner auf meine Anforderung zutraf, hab ich mich an euch hier gewandt.
Musste ja die großen Zahlen zuerst ausgeben, und es gab irgendwie keine Ordnung, die von Rechts unten nach links unten durchlief.
Aber vielen Dank an euch.
Ich kann den Code von Slater gerade nicht testen, werde dies aber Sonntagabend nachholen ;-)
Sieht aber sehr gut aus denke ich.

Gruß

 

[maki]

Inorder traversal sequence: A, B, C, D, E, F, G, H, I

* Note that the inorder traversal of a binary search tree yields an ordered list

 

[jacko]

Vielen Dank euch. Code von Slater funktioniert einwandfrei;-).

Gruß