binary search trees - order

[crossit]

Hallo,

habe eine weiteres Problem wo ich nicht durchblicke

unzwar möchte ich gerne eine pre-Order und in-Order bei einem BST darstellen...
habe soweit auch etwas geschafft jedoch gibt der Code mir nur den ersten wert wieder :S

	public LinkedList<Integer> preOrder(BinTreeNode root) {
		LinkedList<Integer> out = new LinkedList <Integer>();
		if (root.left != null){
                        out.addAll(preOrder(root.getLeft()));
                        out.add(root.getData());
		}
		if (root.right != null){
			out.addAll(preOrder(root.getRight()));
			
			out.add(root.getData());
		}
		return out;
	}


	public LinkedList<Integer> preOrder() {
		
		return preOrder(root);
	}
	public LinkedList<Integer> inOrder() {
		
		return inOrder(root);
	}
	
	public LinkedList <Integer> inOrder (BinTreeNode root){
		LinkedList <Integer> out = new LinkedList <Integer>();
		if (root.left != null && root.right != null){
			out.addAll(inOrder(root.getLeft()));
			out.addAll(inOrder(root.getRight));
			out.add(root.getData());
			
		}
		return out;
	}

 

[Timothy Truckle]

Vermutlich weil Du nicht (rekursiv) über die KindKnoten iterierst....

bye
TT

 

[crossit]

okay und wie mach ich das jetzt?

 

[Timothy Truckle]

okay und wie mach ich das jetzt?

erstehe ih das richig, dass Du zu Ausgabe über die von

inOrder()

zurückggebene Liste itrierst?

inOrder()

funktioniert aber nur richtig, wenn der Baum ausbalanciert ist, d.h.: jeder Knoten linken und rechten Nachfolger hat. Wenn einer von beiden fehlt gibt der Koten eine leere Liste zurück, da ist dann nicht mal sein eigener Wert drin.

Schau Dir das mal im Debugger an.

bye
TT

 

[crossit]

muss ehrlich gestehen das ich mit dem deburger noch keine erfahrung gesammelt hat er zeigt mir nur die erste anfangszahl an und genau das selbe habe ich auch bei preOrder

 

[Timothy Truckle]

Schau Dir doch mal Deine Baumstruktur genauer an, ob die beiden Nachfolger des Root-Knotens selbst beide Nachfolger haben...

bye
TT

 

[ZomgMeister]

Vermutlich weil Du nicht (rekursiv) über die KindKnoten iterierst....

bye
TT

Macht er doch?

out.addAll(inOrder(root.getLeft()));
out.addAll(inOrder(root.getRight));

auch wenn da ne Klammer fehlt

erstehe ih das richig, dass Du zu Ausgabe über die von

inOrder()

zurückggebene Liste itrierst?

inOrder()

funktioniert aber nur richtig, wenn der Baum ausbalanciert ist, d.h.: jeder Knoten linken und rechten Nachfolger hat. Wenn einer von beiden fehlt gibt der Koten eine leere Liste zurück, da ist dann nicht mal sein eigener Wert drin.

Schau Dir das mal im Debugger an.

bye
TT

Für Order-Sachen muss der Baum keine besonderen Eigenschaften erfüllen. (Abgesehen natürlich davon, dass er ein Binärer Suchbaum sein muss)
Keine Ahnung, warum der Baum dafür ausbalanciert sein muss.

Und wie stellst du dir vor, dass jeder Knoten einen rechten und linken Nachfolger hat? Dann wäre der Baum ja unendlich.

Die Methode an sich ist schon fast richtig, blos das sie so post-Order ausgeben würde. Bei In-Order fügt du den rechten Zweig ein, dann den Knoten selber, und dann den Linken Zweig. Im jetzigen Code würde er den Knoten erst zum Schluss hinzufügen.
Achja, und du musst nicht die Kinder überprüfen, ob sie null sind, sondern den aktuellen Knoten.

 

[Timothy Truckle]

Für Order-Sachen muss der Baum keine besonderen Eigenschaften erfüllen. (Abgesehen natürlich davon, dass er ein Binärer Suchbaum sein muss)
Keine Ahnung, warum der Baum dafür ausbalanciert sein muss.

Im allgemeinen hast Du recht, aber seine Implementierung funktioniert nur in einem Symmetrischen, balangierten Baum und selbst dann fehlen die Blätter...

Und wie stellst du dir vor, dass jeder Knoten einen rechten und linken Nachfolger hat? Dann wäre der Baum ja unendlich.

Ich garnicht, ich analysiere nur die Implementierung.

Achja, und du musst nicht die Kinder überprüfen, ob sie null sind, sondern den aktuellen Knoten.

Wenn der Aktuelle Knoten

null

ist bekomme ich doch eine NPE, oder?

bye
TT

 

[ZomgMeister]

Im allgemeinen hast Du recht, aber seine Implementierung funktioniert nur in einem Symmetrischen, balangierten Baum und selbst dann fehlen die Blätter...


Ich garnicht, ich analysiere nur die Implementierung.
Wenn der Aktuelle Knoten

null

ist bekomme ich doch eine NPE, oder?

bye
TT

ah, also die Zeile

if (root.left != null && root.right != null){

verursacht das Problem, dass der Baum balanciert sein muss.
Wenn diese in

if (root != null){

geändert wird, sollte es für jeden beliebigen Baum klappen.
Wobei es dann aber post-order ist.

out.addAll(inOrder(root.getLeft()));
out.add(root.getData());
out.addAll(inOrder(root.getRight));

würde dann in-order ausgeben.