Binärer Baum Tiefe

[MintMinit]

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]

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]

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]

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

@OP poste doch mal deine Node-Definition

 

[MintMinit]

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]

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]

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]

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]

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]

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]

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]

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);
}

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]

Der letzte Eintrag war von mir...

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

 

[Leroy42]

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]

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: