# Rekursiv Höhe Baum



## Nummer6800 (24. Mrz 2015)

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.


```
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.


```
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


```
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:



```
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:


```
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());


        
    }
}
```


----------



## Nummer6800 (25. Mrz 2015)

Ist das zu schwer? Keine Theorie? Ein Hinweis in die richtige Richtung wäre schon toll.


----------



## CSHW89 (25. Mrz 2015)

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 (26. Mrz 2015)

Danke. Ich gehe also wieder vom Endergebnis aus.
leftHeight = leftHeight + 1;
Gedanklich den Rest betrachtend in die andere Richtung (andersherum als verkettete Liste).


----------

