Rekursiv Höhe Baum

Nummer6800

Aktives Mitglied
Hallo.

Ich habe folgendes Problem.

Rekursiv wird die Höhe eines Baumes ermittelt. Der Rest des Codes ist unwichtig.
Mir geht es hier nur darum die Rekursion zu verstehen.


Mein Hauptproblem ist wohl das determineHeight() keinen Parameter erwartet.
Gibt aber leftHeight + 1 zurueck. So komme ich immer hoechstens zur Null.

left.determineHeight() wird durch Rekursion erneut gestartet.
Dann kriege ich als return z.B. leftHeight + 1

Was ist aber wenn die naechste unter Stufe left auch nicht null ist.
Wie muesste ich mir dann die naechste Stufe vorstellen?

1. leftHeight = left.determineHeight();
2. Dank Rekursion komme ich wieder auf :

if (left != null) { // angenommen das danach kommende left waere nicht null
leftHeight = left.determineHeight();

Was jetzt danach kommt.

Wie sieht dieses Ergebnis aus? Ich meine nicht die Werte. Sondern im Sinne von Worten.
Die Werte steigen tatsaechlich. Habe ich im Debugger versucht zu verfolgen.

Java:
public int determineHeight() {

 int leftHeight = -1;
 int rightHeight = -1;

 if (left != null) {
  leftHeight = left.determineHeight();

 }

 if (right != null) {
  rightHeight = right.determineHeight();
 }
 	     
 if (leftHeight > rightHeight) {
  return leftHeight + 1;
 	       
 } else {
  return rightHeight + 1;
 }
}



Hier der restliche Code. Aber eigentlich interessiert mich nur die Rekursion:



Hier nur welche Form die eingefuegten Daten haben muessen.

Java:
public class Person implements Comparable {
 	String name;
 	String address;
 	
 	public Person(String n, String a) { 
 		name    = n;
 		address = a; 
 	}
 	
 	public int compareTo(Object o) {
 		return name.compareTo(((Person)o).name);
 	}
 	
    public String toString() {
        return name+" "+address;
    }
}




Hier werden Dinge eingefuegt

Java:
public class SearchTree {

 	SearchTreeNode root=null; 	

 	public SearchTreeNode findNode(Comparable c) { 
 		SearchTreeNode n=root;
 		while (n!=null) {
 			int cmp = c.compareTo(n.element);
 			if (cmp==0) 		{ return n;    }
 			else if (cmp<0) 	{ n = n.left;  }
 			else 				{ n = n.right; }
 		}
 		return null;
 	}

    public String toString() {
  		return root.toString(); 
 	} 	
 	
 	public boolean insertNode(Comparable c) {    
        SearchTreeNode parent=null, child=root;
   
        // Blatt suchen, nachdem eingefuegt wird
        while(child!=null) {
            parent=child;
            int cmp = c.compareTo(child.element); // Vergleich
            if (cmp==0)     {return false;      } // Element doppelt?
            else if (cmp<0) {child=child.left;  } // links einfuegen
            else            {child=child.right; } // rechts einfuegen
        }
        
        // Einfuegen: root, links oder rechts
        if (parent==null)
            root=new SearchTreeNode(c,null,null);
        else if (c.compareTo(parent.element)<0)
            parent.left=new SearchTreeNode(c,null,null);
        else
            parent.right=new SearchTreeNode(c,null,null);

        return true;
  }

}


Hier steht determineHeight() drin:


Java:
 public class SearchTreeNode {
 	Comparable 		element;		// Objekt
 	SearchTreeNode 	left,right;		// Verzeigerung
 	
 	public SearchTreeNode(Comparable e, SearchTreeNode l, SearchTreeNode r) {
 		element = e;
 		left    = l;
        right   = r;
 	}

 	public String toString() {
 		String s="";
 		if (left!=null) s = s+left.toString();
 		s = s+element.toString()+" ";
 		if (right!=null) s = s+right.toString();
 		return s;
 	}
 	
 	
 	  public int determineHeight() {

 	      int leftHeight = -1;
 	      int rightHeight = -1;

 	     if (left != null) {
 	        leftHeight = left.determineHeight();
 	        
 	       System.out.println("leftHeight: " + leftHeight);
 	     }

 	     if (right != null) {
 	        rightHeight = right.determineHeight();
 	     }
 	     
 	    System.out.println("rightHeight: " + rightHeight);

 	    if (leftHeight > rightHeight) {
 	       return leftHeight + 1;
 	       
 	    } else {
 	       return rightHeight + 1;

 	}
 	 	}
 	
 	
}





Hier werden Dinge in der main eingefuegt:

Java:
public class TestSearchTree {
 
    public static void main(String[] args) {

    	Person p1 = new Person("Meier", "Holzweg 10");
    	Person p2 = new Person("Mueller", "Holzweg 11");
    	Person p3 = new Person("Schulze", "Holzweg 77");
    	Person p4 = new Person("Anders", "Holzweg 2");
    	Person p5 = new Person("Geier", "Holzweg 82");
    	Person p6 = new Person("Stein", "Holzweg 15");
    	Person p7 = new Person("Buchmann", "Holzweg 101");
    	Person p8 = new Person("Klingel", "Holzweg 45");
    	Person p9 = new Person("Polster", "Holzweg 17");

    	SearchTree st=new SearchTree();
    	st.insertNode(p1);
    	st.insertNode(p2);
    	st.insertNode(p3);
    	
    	System.out.println(st.root.determineHeight());
    	
    	st.insertNode(p4);
    	st.insertNode(p5);
    	st.insertNode(p6);
    	
    	System.out.println(st.root.determineHeight());
    	
    	st.insertNode(p7);
    	st.insertNode(p8);
    	st.insertNode(p9);

    	System.out.println(st.root.determineHeight());


        
    }
}
 

CSHW89

Bekanntes Mitglied
Möchtest du verstehen, wie determineHeight genau arbeitet?
Also bei rekursiven Funktionen sollte man immer erstmal den Basisfall verstehen. Der ist in diesem Fall, dass ein Baum erstmal aus nur einem Knoten besteht. Dieser Baum hat eine Höhe von 0. Im Code sind bei einem Baum aus nur einem Knoten die Variablen left und right gleich null. Also bleiben leftHeight und rightHeight gleich -1, der else-Teil wird ausgeführt und die Funktion gibt 0 zurück. Funktioniert also.
Nun kommen wir zum zweiten Fall, wenn der Baum einen linken und/oder einen rechten Teilbaum besitzt. Gehen wir jetzt davon aus, dass wir die Höhe des linken und rechten Teilbaums schon kennen. Dann ist die Höhe des Baums immer die größere Höhe von links oder rechts plus 1. Im Code sieht das dann wie folgt aus. Berechne erstmal die Höhe des linken Teilbaums (falls er existiert), dann die Höhe des rechten Teilbaums (falls er existert). Nun sind diese vorhanden, und wir können die Höhe des gesamten Baums mit der einfachen if-Abfrage berechnen.

lg Kevin
 

Nummer6800

Aktives Mitglied
Danke. Ich gehe also wieder vom Endergebnis aus.
leftHeight = leftHeight + 1;
Gedanklich den Rest betrachtend in die andere Richtung (andersherum als verkettete Liste).
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Wie könnte man den Codeschnipsel rekursiv darstellen? Allgemeine Java-Themen 1
M Endrekursiv vs Rekursiv Allgemeine Java-Themen 4
Aboya Kugel mit Hilfe von Dreiecken rekursiv zeichnen Allgemeine Java-Themen 2
Aboya Char Array rekursiv vergleichen Allgemeine Java-Themen 15
H Heron Verfahren Tail-rekursiv lösen Allgemeine Java-Themen 7
Kingamadeus2000 Alle mehrfach vorkommenden Buchstaben rekursiv aus einem String entfernen. Allgemeine Java-Themen 6
I Diskussion zu: Tribonacci Folge Rekursiv Allgemeine Java-Themen 15
R Warum ist die Methode unendlich oft rekursiv? Allgemeine Java-Themen 5
D 2,3-Baum rekursiv erstellen Allgemeine Java-Themen 20
denny86 NetBeans Ordnernamen rekursiv auslesen und in Variable verarbeiten Allgemeine Java-Themen 38
B Primfaktorzerlegung Rekursiv Allgemeine Java-Themen 2
B Primzahltest rekursiv Allgemeine Java-Themen 15
S Verkettete (Teil)Liste sortieren ( rekursiv bis n) Allgemeine Java-Themen 2
L Alle möglichen Additionen (Rekursiv) Allgemeine Java-Themen 3
H Vektor rekursiv erzeugen Allgemeine Java-Themen 2
J Breitensuche in Graph rekursiv Allgemeine Java-Themen 2
E ordner rekursiv durchsuchen Allgemeine Java-Themen 6
E Ordner rekursiv kopieren Allgemeine Java-Themen 8
R synchronized methode rekursiv aufrufen Allgemeine Java-Themen 5
S MergeSort iterativ und rekursiv? Allgemeine Java-Themen 8
G Array rekursiv durchlaufen Allgemeine Java-Themen 2
S JAVA JTree rekursiv umschreiben Allgemeine Java-Themen 5
leifg Rekursiv mit Threads Programmieren Allgemeine Java-Themen 2
sparrow Ant build-files rekursiv aus ant aufrufen Allgemeine Java-Themen 3
K zinsen rekursiv/iterativ Allgemeine Java-Themen 17
K Verzeichnis rekursiv aus JAR-Datei extrahieren Allgemeine Java-Themen 6
F Filelisting iterativ, nicht rekursiv Allgemeine Java-Themen 7
L Spielerei: Frame rekursiv darstellen Allgemeine Java-Themen 3
M Rekursiv Verzeichnisse ansehen und auf Muster matchen Allgemeine Java-Themen 6
X FontMetrics - Negative Breite/Höhe bei großer Schrift Allgemeine Java-Themen 6
D JAI Verliere Bildinformationen (Höhe, und Breite) Allgemeine Java-Themen 4
G iText: Wie stellt man die Höhe eines Strings fest? Allgemeine Java-Themen 3
E XML - Datei Darstellung in IntelliJ als Baum Allgemeine Java-Themen 2
Karl_Der_Nette_Anfänger Hat wer ne Lösung für verknüpfte Postleitzahlen? (Baum/Wurzel Struktur) Allgemeine Java-Themen 11
D Datentypen 2-3 Baum erstellen mit geordnetem int-array Allgemeine Java-Themen 0
L Dependency Injection für Baum-Einträge Allgemeine Java-Themen 9
M Iterator für trinären Baum Allgemeine Java-Themen 0
D Baum zeichnen hilfe Allgemeine Java-Themen 4
D if - else Baum vereinfachen Allgemeine Java-Themen 4
A AVL-Baum - Testen ob einer vorliegt Allgemeine Java-Themen 4
M Eclipse Stackoverflow beim Einlesen von großen Bilder in kd Baum Allgemeine Java-Themen 15
G Datentypen TreeMap nach Color sortiert (kd-Baum) Allgemeine Java-Themen 8
M Baum nach Stack plus Objektkonvertierung Allgemeine Java-Themen 5
S Baum mit vordefinierten Werten befüllen Allgemeine Java-Themen 2
D Datenstruktur für Hierarchie/Baum mit Tiefe 3 Allgemeine Java-Themen 8
D Rot-Schwart-Baum denkfehler im code? Allgemeine Java-Themen 6
M Baum Allgemeine Java-Themen 3
K Dependency Baum erstellen/analysieren Allgemeine Java-Themen 2
J Baum mit Adjazensmatrix Allgemeine Java-Themen 8
MQue Tidy HTML baum durchlaufen Allgemeine Java-Themen 5
C Breitendurchlauf Baum. Vorgehen unklar. Allgemeine Java-Themen 23
C Fehler im Quellcode. Suche in einem Baum Allgemeine Java-Themen 3
R Daten aus Baum entsprechend in jTree einfuegen Allgemeine Java-Themen 2
C Daten möglichst schnell einem Baum zuordnen Allgemeine Java-Themen 2
S Datenstruktur für einen Baum Allgemeine Java-Themen 5
N Baum aus Datei laden. Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben