Input/Output Elemente eines Binären Suchbaums ausgeben

[undercover]

Moin Leute,
Ich bräuchte mal eure Hilfe.
Ich möchte einen Text in einen Binären Suchbaum einlesen. Am Ende soll er Mehrfacheinträge berücksichtigen ( z.B. drei mal das Wort "Hallo"), soweit bin ich allerdings noch nicht.
Ich stecke Momentan an einer anderen Stelle.
Ich lese eine Textdatei mittels BufferedReader ein :

String input;
        BinaryTree tree = new BinaryTree();
        BufferedReader in = new BufferedReader(new FileReader(filename));
        while (in.ready()) {
            input = in.readLine();
            tree.insert(input);

Hinter filename steckt der Dateipfad zu einem Textdokument welches unsortiert Wörter und Zeichen jeweils eins in einer Zeile gespeichert hat.
Mein Binärbaum sieht wie folgt aus :

public class BinaryTree {
    static class TreeNode {
        TreeNode left;
        TreeNode right;
        Object key;

        public int compareKeyTo(Comparable c) {
            return (key == null ? -1 : ((Comparable) key).compareTo(c));
        }

        public TreeNode(Object o) {
            key = o;
        }

        public Object getKey() {
            return key;
        }

        public TreeNode getLeft() {
            return left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setLeft(TreeNode n) {
            left = n;
        }

        public void setRight(TreeNode n) {
            right = n;
        }

        public String toString() {
            return key.toString();
        }
    }

    private TreeNode head;
    private TreeNode nullNode;

    public BinaryTree() {
        head = new TreeNode(null);
        nullNode = new TreeNode(null);
        head.setRight(nullNode);
        nullNode.setLeft(nullNode);
        nullNode.setRight(nullNode);
    }

    protected TreeNode findNode(Comparable c) {
        TreeNode n = head.getRight();
        while (n != nullNode) {
            int cmp = n.compareKeyTo(c);
            if (cmp == 0)
                return n;
            else
                n = (cmp > 0 ? n.getLeft() : n.getRight());
        }
        return null;
    }

    public boolean find(Comparable c) {
        return (findNode(c) != null);
    }

    public boolean insert(Comparable c) {
        TreeNode parent = head;
        TreeNode child = head.getRight();
        while (child != nullNode) {
            parent = child;
            int cmp = child.compareKeyTo(c);
            if (cmp == 0)
                return false;
            else
                child = (cmp > 0 ? child.getLeft() : child.getRight());
        }
        TreeNode node = new TreeNode(c);
        if (parent.compareKeyTo(c) > 0)
            parent.setLeft(node);
        else
            parent.setRight(node);
        node.setLeft(nullNode);
        node.setRight(nullNode);
        return true;

    }

}

Wie könnte ich prüfen ob mein Baum alles richtig abgespeichert hat? Dazu müsste ich den Baum ja komplett durchsuchen, wie printe ich das Ergebnis leserlich aus?

 

[Flown]

Da gibt es mehrere Strategien, z.B.: in-order

 

[undercover]

Hi
habe ich probiert, mein Ansatz war

public void printInorder(TreeNode n){
        if(n != nullNode){
            printInorder(n.getLeft());
            System.out.println(n.toString());
            printInorder(n.getRight());
        }
    }

Die Methode steht nach meiner insert Methode. In der BinaryTree Klasse.
Das Ganze wollte ich nach dem Einlesen durch den BufferedReader in meiner Klasse TextOutout ausgeben.
Leider klappt der Aufruf nicht.

 

[JCODA]

Versuchs mal so:

public void printInorder(){
        if(getLeft().getKey() != null){
            getLeft().printInorder();
        }        
        System.out.println(getKey());
        if(getRight().getKey() != null){
            getRight().printInorder();
        }
    }

 

[Flown]

Wie rufst du denn die Methode auf?

 

[Meniskusschaden]

Leider klappt der Aufruf nicht.

Wie macht sich das bemerkbar?

Du solltest noch ein paar null-Prüfungen einbauen. Wenn ein Knoten nicht der nullNode ist, muß es kein "normaler" Knoten sein, sondern er ist vielleicht null.

 

[undercover]

@Flown , das ist mein Problem, ich muss ja die Wurzel für den Aufruf übergeben. Ich stehe gerade auf dem Schlauch an welcher Stelle und wie ich ihn aufrufe.
@Meniskusschaden , die Prüfung umgehe ich indem ich Pseudoknoten , head und nullNode, einführe. Der Test auf einen leeren Baum und auf null-Verweise entfallen dann ja.

 

[Meniskusschaden]

@Flown , das ist mein Problem, ich muss ja die Wurzel für den Aufruf übergeben. Ich stehe gerade auf dem Schlauch an welcher Stelle und wie ich ihn aufrufe.

tree.printInorder(tree.head);

@Meniskusschaden , die Prüfung umgehe ich indem ich Pseudoknoten , head und nullNode, einführe. Der Test auf einen leeren Baum und auf null-Verweise entfallen dann ja.

Dann bin ich mal gespannt, ob wirklich keine NullPointerException fliegt.😉

 

[Flown]

public void printInOrder() {
  printInOrder(head);
}

private void printInOrder(TreeNode n){
  if(n != nullNode){
    printInorder(n.getLeft());
    System.out.println(n.toString());
    printInorder(n.getRight());
  }
}

 

[undercover]

@Flown danke habe die die Methoden in meiner BinaryTree Klasse nach der insert Methode implementiert, aufgerufen nach dem BufferedReader in meiner TextOut Klasse.
@Meniskusschaden , du hast recht mir fliegt eine NullPointerException um die Ohren. Wieso das, dachte meine Pseudo... verhindern das.
Ich muss sagen der Baum sieht komisch aus, wenn ich ihn im debugger angucke. Mir scheint es das er beim einlesen folgendes macht: (Wörter und Zeichen im Textdokument)
Head - left : "null" ; right "Jeder";
Jeder - left : "." ; right "mag"
. - left : null ; right : null;
mag - left : "Obst" ; right : "ist";

Normal müsste doch der "." an oberster Stelle stehn, so zu sagen die Wurzel.

 

[Meniskusschaden]

Um dir einen visuellen Eindruck zu verschaffen, kannst du ja erst einmal null-Prüfungen einbauen (ob die nach Fehlerbeseitigung entfallen können, kannst du ja später entscheiden) und beim Aufruf von printInOrder(TreeNode) die Knotentiefe übergeben, damit du bei der Ausgabe eine entsprechende Einrückung vorsehen kannst. Wenn du dann noch in umgedrehter inOrder-Reihenfolge ausgibst (links und rechts vertauschen) hast du einen um 90 Grad gedrehten Baum. Dann könntest du nach jeder Einfügung den Baum drucken. So würde sich für ich bin ein toller satzfolgende Ausgabe ergeben:

null
-----------
.ich
null
-----------
.ich
..bin
null
-----------
.ich
...ein
..bin
null
-----------
..toller
.ich
...ein
..bin
null
-----------
..toller
...satz
.ich
...ein
..bin
null