Binary Search Tree - Nummerierung in Inorder

[skuki]

Hallo,

beschäftige mich gerade mit Binären Suchbäumen.

Methoden wie löschen, hinzufügen ect. sind klar, doch komme ich bei einer Methode nicht weiter.

Ich möchte das Element an der x-ten Stelle bzw. mit einem bestimmten key in Inorder-Traversierung finden.

Einen Binären Baum in inorder ausgeben ist nicht das Problem

 public void inOrderTraverseTree(Node root){
		 if(root != null){
			 inOrderTraverseTree(root.leftChild);
			 System.out.println(root);
			 inOrderTraverseTree(root.rightChild); 
		 }	 
	 }

Wenn ich das ganze in eine Liste oder Array abspeichern könnte, würde es sicherlich auch irgendwie gehen es durchzunummerieren. (Schleife und fertig)

Aber wie stelle ich es an, wenn ich keine zusätzliche Datenstruktur verwenden will um Speicherplatz zu sparen?

Denke es muss rekursiv ablaufen. Doch wie beginne ich hier?

Vielen Dank für ein paar Tipps!

 

[CSHW89]

Was möchtest du denn genau haben? Jenachdem sieht die Lösung auch anders aus.
- Den Wert des x-ten Elements
- Prüfen, ob es ein Element mit einem bestimmten Key vorhanden ist (den Wert davon macht keinen Sinn, da es ja der Key ist)
- Den Weg zum x-ten Element
- Den Weg zu einem Element mit einem bestimmten Key

lg Kevin

 

[skuki]

Hallo, danke für deine Antwort.

Ich müsste nur wissen wie man über den Baum iteriert. Speziell würde mich einmal das x-te Element interessieren.

lg

 

[CSHW89]

Ok, da gibt es ein paar Möglichkeiten. Die erste ist z.b. die derzeitige Position immer zu übergeben und am Ende zurückzugeben. Das Problem dabei ist, dass du zusätzlich das gefundene Element zurückgeben willst. Einer Methode zwei Werte zurück geben zu lassen funkioniert zwar, machts aber etwas komplizierter.
Die zweite wäre die derzeitige Position als mutable Objekt (sowas wie MutableInt) zu übergeben. Wenn sich der Wert des Objekts ändert, bekommen auch alle anderen Aufrufebenen die Änderung mit. Da Java kein MutableInt hat, kann man sich mit einem int-Array mit nur einem Eintrag behelfen:

private Object getPrivate(Node root, int x, int[] position) {
    Object res = getPrivate(root.left, x, position);
    If (res != null) return res;  // im linken Teilbaum gefunden
    
    if (x == position[0])
        return root.value
    position[0]++;  // Erhöhung bekommen auch aufrufende Methoden mit, da int-Array mutable ist
    
    Object res = getPrivate(root.right, x, position);
    If (res != null) return res;  // im rechten Teilbaum gefunden
    
    return null;
}

public Object get(Node root, int x) {
    return getPrivate(root, x, {0});
}

 

[skuki]

Hallo,

erstmals vielen Dank für deine Antwort.


Habe den Code jetzt so eingefügt und nur dahingehend verändert dass ich kein Object habe sondern eine Node und den key (int) zurückgeben will an der gewissen Position.

Sieht jetzt wie folgt aus:

	 private Node getValueAtPosition(Node root, int x, int[] position) {
		    Node res = getValueAtPosition(root.leftChild, x, position);
		    
		    if(res != null) return res;  // im linken Teilbaum gefunden
	
		    if (x == position[0])
		        return root;
		    
		    position[0]++;  // Erhöhung bekommen auch aufrufende Methoden mit, da int-Array mutable ist
		 
		    res = getValueAtPosition(root.rightChild, x, position);
		    if (res != null) return res;  // im rechten Teilbaum gefunden
		 
		    return null;
		}
		 
	 
		public int valueAtPosition(int x) {
			int[] position = {0};
	        return getValueAtPosition(root, x, position ).key;
	    }

Das erste Problem ist, dass ich eine Nullpointer Ex bekomme.

Das zweite was ich mich frage ist, ob hier wirklich auch in inorder gesucht wird? Oder greift der erste rekursive Aufruf mit root.leftChild eh genau so tief?

Vielen Dank für deine Hilfe!

 

[CSHW89]

Die Nullpointer Exception bekommst du genau dann, wenn es kein x-tes Element gibt, also x zu groß ist. Dann ist die Prüfung "(x == position[0])" nie erfüllt, und die Funktion gibt auf jeder Aufrufebene null zurück.
InOrder bedeutet du suchst erst den linken Teilbaum ab, dann den Root, und dann den rechten Teilbaum, und das natürlich rekursiv. D.h. du suchst erst im linken Teilbaum, dann im linken vom linken, dann im linken vom linken vom linken usw...
Irgendwann bist du beim linkesten Blatt, das ist das erste (bzw. nullte) Element. Das zweite (bzw. erste) ist dann dessen Vater usw...

lg Kevin