# Binärer Baum Tiefe



## MintMinit (8. Dez 2006)

Halli Hallo,

bin gerade dabei für einen binären Baum die Tiefe zu schreiben. Versucht hab ich es mit folgenden Methoden:


```
public int depth(Node n){
		// Liefert die Tiefe des Knotens
		return depth(root, n.data);
	}

   
  
    private int depth(Node n, String elem){
        // Liefert die Anzahl der Kanten vom Konten n bis zu dem (eindeutigen) Element,
        // das "elem" als Wert (in der Variablen data) enthält.
        
        // Hinweis: ob ein Knoten das Element "elem" enthält, prüfen Sie mit der
        // String-Methode "equals"; also z.B. n.data.equals(elem)
        // die Prüfung auf "n.data == elem" führt nicht zum gewüschnten Ergebnis!
        int lDepth=0;
        int rDepth=0;
        if (n.isLeaf()) return 0;
        if(n.left!=null&&n.data.equals(elem))lDepth = depth(n.left,elem);	// Tiefe des li. Unterbaums berechnen
        if(n.right!=null&&n.data.equals(elem))rDepth = depth(n.right,elem);	// Tiefe des re. Unterbaums berechnen
        if (lDepth < rDepth) 		// Tiefe des tieferen Unterbaums
            return (1+lDepth);		// um 1 erhöht zurückliefern
        else
            return(1+rDepth);
         }
```

Wenn ich jetzt folgenden Baum aufbaue(dargestellt als ausschließlich Knoten):


```
M
            F                S
      D                P          X
A          E
```


Wenn ich jetzt nach dem Knoten F suche, dann hat er eine Tiefe von 1, was ja OK ist.
Wenn ich nach D suche, dann hat der auch nur eine Tiefe von 1.
Wenn ich nach A oder E suche, dann hat er auch nur ne Tiefe von 1.
Wenn ich nach M suche, dann gibt mir das Programm ne Tiefe von 2 aus.

Kann mir jemand sagen, was da falsch läuft?

Danke.[/img]


----------



## Leroy42 (8. Dez 2006)

```
private int depth(Node n, String elem) {
  if (n == null) return -1;
  if (n.data.equals(elem)) return 0;
  else 
     return 1 + depth(elem.compareTo(n.data) < 0 ? n.left : n.right);
}
```


----------



## Yzebär (8. Dez 2006)

Ich hätte erwartet, daß man anstelle 

```
if(n.left!=null&&n.data.equals(elem))
```
sowas schreibt...

```
if(n.left!=null&&n.left.data.equals(elem))
```
außerdem solltest du das noch ergänzen

```
if (n.isLeaf() || n.data.equals(elem) ) return 0;
```


----------



## Leroy42 (8. Dez 2006)

Darüber zu spekulieren ist müßig,
solange wir die Datenstruktur nicht genau kennen.

@OP poste doch mal deine Node-Definition


----------



## MintMinit (8. Dez 2006)

Hier meine Node Klasse


```
public class Node {
    
    protected String data;
    protected Node left;
    protected Node right;
    
    public Node(String d) {
        super();
        data = d;
        left = null;
        right = null;
    }
    
    public String toString(){
        return data.toString();
    }

  public boolean isLeaf(){
        boolean a=false;
        if((left==null) && (right==null))a=true;
        return a;
    }
    
    public boolean hasLeftChildren(){
        boolean a=false;
        if(left!=null) a=true;
        return a;
//        return true;
    }
    
    public boolean hasRightChildren(){
      boolean a=false;
        if(right!=null) a=true;
        return a;
//        return true;
    }
    
   }
```


----------



## Leroy42 (8. Dez 2006)

Genau, wie ich es mir gedacht habe.   

Dann müßte mein Code (ohne Yzebärs Änderungsvorschlägen)
eigentlich laufen.  ???:L 

Was ist denn falsch? (Wenn überhaupt etwas falsch ist)


----------



## Leroy42 (8. Dez 2006)

Du kannst die Klassendefinition übrigens auch _straffen_.


```
public class Node { 
    protected String data; 
    protected Node left; 
    protected Node right; 
    
    public Node(String d) {
      data = d;
    } 
    
    public String toString() {
      return data.toString();
    } 

    public boolean isLeaf() {
      return left==null && right==null;
    } 
    
    public boolean hasLeftChildren()  {return left  != null;} 
    public boolean hasRightChildren() {return right != null;}
   }
```


----------



## MintMinit (8. Dez 2006)

Bei deiner Methode von oben, da rennt er in folgende
Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError!

Kann man die auch ohne compare schreiben?
return 1 + depth(elem.compareTo(n.data) < 0 ? n.left : n.right); 

Das eigentliche Problem ist, dass dieses dämliche Programm mir bei der Wurzel die Tiefe 2 ausgibt


----------



## Gelöschtes Mitglied 5909 (8. Dez 2006)

java.lang.StackOverflowError! deutet auf zu hohe rekursion hin.
desweiteren wäre ein template sinnvoll


```
public class Node<T> {
 private T data;
 private Node<T> left;
 private Node<T> right;

}
```


----------



## Leroy42 (8. Dez 2006)

Also ich habe meinen Code jetzt mal getestet und
es klappt alles so wie es sein soll; kann es sein, daß du
beim Einfügen irgendetwas anders machst?  ???:L


----------



## Leroy42 (8. Dez 2006)

raiL hat gesagt.:
			
		

> java.lang.StackOverflowError! deutet auf zu hohe rekursion hin.


...was nur passieren kann, wenn das gesuchte Element
nicht existiert und das Programm in eine Endlosschleife
gerät.

Genau das habe ich aber berücksichtigt, und liefere in diesem
Fall eine *-1*


----------



## Guest (8. Dez 2006)

Leroy42 hat gesagt.:
			
		

> ```
> private int depth(Node n, String elem) {
> if (n == null) return -1;
> if (n.data.equals(elem)) return 0;
> ...



Ich kann mir nicht vorstellen, daß dieser Code funktioniert. Wie werden denn durch den Ausdruck "elem.compareTo(n.data) < 0 ? n.left : n.right" beide Zweige durchsucht?


----------



## Yzebär (8. Dez 2006)

Der letzte Eintrag war von mir...

Ich wollte noch anfügen, daß meine anfangs geposteten Änderungen Quatsch sind...


----------



## Leroy42 (9. Dez 2006)

Anonymous hat gesagt.:
			
		

> Wie werden denn durch den Ausdruck "elem.compareTo(n.data) < 0 ? n.left : n.right" beide Zweige durchsucht?



Je nach Ergebnis des Vergleiches liefert der tertiäre Operator (? : )
entweder den Ausdruck n.left oder n.right. Mit diesem wird dann die 
Methode depth rekursiv aufgerufen.

Aber du hast schon Recht: Die Anweisung muß natürlich heißen:


```
return 1 + depth(elem.compareTo(n.data) < 0 ? n.left : n.right, elem);
```

Etwas _weitschweifiger_ formuliert, ist mein Code
identisch zu:


```
private int depth(Node n, String elem) { 
  if (n == null) return -1; 
  if (n.data.equals(elem)) return 0; 
  else {
    if (elem.compareTo(n.data) < 0) {
      return 1 + depth(n.left, elem);
    } else {
      return 1 + depth(n.right, elem);
    }
  }
}
```


----------



## Yzebär (9. Dez 2006)

Ich sehe immer noch ein Problem, nämlich wenn der Zweig, der durchsucht wird nicht den gesuchten Knoten beinhaltet, dann gibt doch dein Code ein 1 + .... -1 zurück. Oder sehe ich das falsch?

Nachdem mir selbst keine elegante Lösung einfällt, wie das Problem zu lösen ist, wenn man sich von Knoten zu Knoten hangelt, würde ich vorschlagen, jeweils in gesamten der Knotenebene zu suchen.

Etwa so...

```
public int sucheElement (ArrayList<Node> nodeList, int depth, String elemName)
{
    // Nur Liste bearbeiten, die Elemente enthält.
    if( nodeList == null || nodeList.size() == 0 )
        return -1;

    // Einen Iterator erzeugen, der durch die Liste der Knoten iteriert.
    Iterator listIterator = nodeList.iterator();
    // Eine neue Liste für die Knoten der nächsten Ebene erzeugen.
    ArrayList<Node> childNodes = new ArrayList<Node>();
    
    while( listIterator.hasNext() )
    {
         Node node = listIterator.next();

         // Element gefunden, depth zurückgeben.
         if( node.data.equals(elemName) )
             return depth;
         // Wenn vorhanden, Knoten eine Ebene tiefer der Liste hinzufügen.
         if( node.left != null )
             childNodes.add( node.left );
         if( node.right != null )
             childNodes.add(node.right);
     }

     // Ansonsten eine Ebene Tiefe weitersuchen.
     return sucheElement( childNodes, depth + 1, elemName );
}
```
Die Sache ist jetzt allerdings nicht mehr trivial, hätte aber den Vorteil, daß man auch in der Mitte des Baumes anfangen kann zu suchen (wenn man die Tiefe weiß) und einen Baum parallel anstatt sequentiell... ähh ja, ich höre schon auf...  :bae:


----------

