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.
Hier der restliche Code. Aber eigentlich interessiert mich nur die Rekursion:
Hier nur welche Form die eingefuegten Daten haben muessen.
Hier werden Dinge eingefuegt
Hier steht determineHeight() drin:
Hier werden Dinge in der main eingefuegt:
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());
}
}