Binärbaum verstehen

[Nummer6800]

Ich habe es bereits im Anfängerforum versucht. Ist wohl zu schwer dafuer. Ist wohl fuer Fortgeschrittene. Daher versuche ich hier mein Glueck:


Hallo.

Ich habe Probleme den binären Suchbaum nachzuvollziehen. Ich verstehe bei der Methode insertNode in der Klasse Searchtree nicht, wie damit ein Baum aufgebaut wird.

Hier die Inhalte und das Comparable implentiert:

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

Hier von welchem Typen das ist. Und natuerlich die Verzweigungen.

public class SearchTreeNode {
 	Comparable 		element;		// Objekt
 	SearchTreeNode 	left,right;		// Verzeigerung
 	
 	public SearchTreeNode(Comparable e, SearchTreeNode l, SearchTreeNode r) {
 		element = e;
 		left    = l;
        right   = r;
 	}
}

Ich bin die Sache durchgegangen Methode insertNode:

Erstes Element Hinzufuegen: root wird Werte etc zugewiesen
Zweites Element Hinzufuegen: erhalte ich als Ergebnis parent.left=new SearchTreeNode(c,null,null); oder parent.right=new SearchTreeNode(c,null,null);
Drittes Element Hinzufuegen: parent=null, child=root; dann immer noch danach parent=child; kann ich doch gar keinen Baum aufbauen???
Oder wo bleibt das zweite Element erhalten? Es verschwindet doch wieder.

Oder hat das was mit dem boolean zu tun?? Ich sehe fuer das boolean gar keine Bedeutung.

public class SearchTree {

 	SearchTreeNode root=null; 	


 	
 	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 z B was hinzfuegen zum Suchbaum in der main:

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("Mueller", "Wo anders");
        Person p4 = new Person("Schulze", "Holzweg 77");

        SearchTree st=new SearchTree();
        st.insertNode(p1); st.insertNode(p4);
        st.insertNode(p2); st.insertNode(p3);

    }
}

 

[Flown]

Du verwendest zum Aufbau deines Baumes eine verkettete Liste. Das heißt du erstellst einen Node und hängst ihn an einen anderen dran. In deinem Fall muss das sortiert von statten gehen.

Wenn du jetzt mal einen Linearisierungsalgorithmus implementierst (also in-Order, post-Order, oder wie sie alle heißen) kannst du dir ja ansehen, ob der Baum richtig aufgebaut wird oder nicht.

Der Rückgabewert sagt nur aus, ob ein Wert eingefügt wird oder nicht (also ob Duplikat existiert oder nicht).

 

[Nummer6800]

Mein Problem ist wohl diese Zeile in class SearchTree Methode p boolean insertNode:
else if (cmp<0) {child=child.left; } // links einfuegen

Alles was in child war verschwindet doch dann? Alles darin wird doch null?
Warum dann links einfuegen?

 

[Thallius]

Nein, Child zeigt dann eben auf den nächsten Eintrag im Baum oder auf Null wenn es keinen weiteren Eintrag gibt.

 

[Nummer6800]

Man fügt Dinge ein mit der Methode. Also zeigt child dann immer auf null. Denn bei child.left ist doch nichts.
Und wird niemals etwas sein. Dann faengt die Methode wieder von oben an. child = root etc.

Oder wann ist etwas bei child.left?

 

[Thallius]

Geh es doch einfach mal schritt für schritt selber durch. Meinetwegen auch im Debugger mit Einzelschritten und schau Dir die Inhalte der Variablen an.

Natuerlich ist beim ersten Element left und right = null weil nichts drin ist. Aber danach wird ja was reingeschrieben

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;

Beim nächsten mal ist also schon ein left oder ein right vorhanden. Je nachdem wo das eingefügt wurde.

 

[Nummer6800]

Du meinst also deswegen:
parent=child;
Das ist wieder das Ding das die wieder auf das gleiche Objekt zeigen, etc.
Werde es mit dem Debugger versuchen. Hoffentlich funktioniert das mit dem Punkte setzen diesmal besser.