Tiefe im Binärbaum

[kwonilchang]

Hallo!

Möchte in einem Binärbaum zu jedem Knoten die Tiefe ausgeben lassen. Das Prinzip eines Baumes und seiner Tiefe habe ich soweit verstanden, nur kann ich daraus kein Java-Programm machen. Habe mal an dieser Methode gebastelt:

int depth(BinaryNode n) { 
        int leftHeight; 
        int rightHeight; 
        
        if (n.left == null) { 
           leftHeight = -1; 
        } else { 
           leftHeight = depth(n.left); 
        } 
        if (n.right == null) { 
           rightHeight = -1; 
        } else { 
           rightHeight = depth(n.right); 
        } 
        return 1 + Math.max(leftHeight, rightHeight);
     }

Hierbei wird zwar eine Tiefe ausgegeben, aber in falscher Reihenfolge (Wurzel soll ja Tiefe 0 haben). Anscheinend verstehe ich noch nicht wirklich, was diese Methode eigentlich genau macht. Kann mir das jemand erklären oder vielleicht einen Tipp geben, wie ich die richtige Tiefe erhalte?

Danke schonmal!

Viele Grüße,

kwonilchang

 

[Marco13]

Das was diese Methode ausrechnet, würde ich eher als die "Höhe" bezeichnen. Aber wie sagte schon mein Inf3-Dozent sinngemäß: Namen sind Schall und Rauch, es geht um das Zurechtfinden im abstrakten Gerüst der Definitionen. Wenn du etwas haben willst, was für die Wurzel 0 liefert, und für die Nachfolger der Wurzel dann 1, usw. dann mußt du der Methode wohl die Wurzel mit übergeben. Im Pseudocode wäre das dann ungefähr sowas wie

public int getDepth(Node node, Node root)
{
    if (root == null) return -1;
    if (node == root) return 0;
    int depthL = getDepth(node, root.left);
    if (depthL != -1) return 1+depthL;
    int depthR = getDepth(node, root.right);
    if (depthR != -1) return 1+depthR;
    return -1;
}

 

[mabe83]

Oder mit anderen Worten ausgedrückt:

Das was du da machen möchtest nennt man Traversierung. Im Prinzip es das ganz einfach. Du schaust dir, ausgehend vom Wurzelknoten, zuerst die linken Verzweigungen an und dann die rechten.
Der Algorithmus arbeitet rekursiv, d.h. in dem Beispiel, jedesmal wenn ein weitere Unterknoten entdeckt wurde (!= null), dann wird die Funktion "depth" aufgerufen, diesmal allerdings mit dem Unterknoten als Startknoten.
Der Spaß geht solange bis links / später rechts, kein Unterknoten mehr vorhanden ist.
Nun werden die Rekursionen aufgelöst. Du gibst vom tiefsten Knoten an immer 1 an die Aufrufende Funktion zurück. Im Endeffekt werden so alle Knoten aufaddiert.
Math.max(leftHeight, rightHeight) entscheidet noch welche Verzweigung die tiefste ist, denn die Tiefe orientiert sich am jeweils tiefsten Zweig (der linke oder der rechte).

Falls noch Unklarheiten bestehen, Wiki hilft da auch ganz gut: http://de.wikipedia.org/wiki/Binärbaum