Interface Baum visualisieren

Hallo,
ich habe eine Arraylist:
Java:
private ArrayList<int[]> info = new ArrayList<int[]>();
Diese beinhaltet die Daten eines Baumes, den ich gerne Visualisieren würde. Das habe ich bisher:
Java:
private int x, width;

public void paintComponent(Graphics g) {
    super.paintComponent(g);
    int y = 10;
    width = getWidth();
    for(int i = 0; i < info.size(); i++) {
    if(i == 0) x = (getWidth() - g.getFontMetrics().stringWidth(Arrays.toString(info.get(i)))) / 2;
    else calcX(g.getFontMetrics().stringWidth(Arrays.toString(info.get(i))), i);
    g.drawString(Arrays.toString(info.get(i)), x, y);
    y +=20;
    }
}

public void calcX(int w, int index) {
    width /= 2;
    if(info.get(index).length == 1 && info.get(index-1).length == 1) x = (width * 2);
    else x = (width - w) / 2;
}
Allerdings ist das sehr unübersichtlich und wie ich das sehe auch nicht zielführend. Im folgenden Bild habe ich einen Beispielbaum, wobei die grünen Zahlen (die nicht gezeichnet werden sollen) den Index des jeweiligen int-Arrays in der ArrayList darstellen. Die Striche wären schön aber nicht zwingend notwendig. Wie würde ich ein System schreiben, das die Positionen der jeweiligen Strings berechnet, sodass alles schön eingerückt ist?
12776
 
Wie würde ich ein System schreiben, das die Positionen der jeweiligen Strings berechnet, sodass alles schön eingerückt ist?
Das ist nicht ganz trivial. Wir können ja mal versuchen, uns ranzutasten :)

Den meisten Platz brauchen offensichtlich die Blattknoten, die in einem festen Abstand zueinander angeordnet werden. Den Abstand bezeichnen wir mal mit hGap.

Außerdem haben wir ein Array mit n Elementen, d. h. wir brauchen Platz für n Blattknoten zzgl. (n-1)*hGap für die Abstände zwischen den Knoten.

Wie groß ist der Platz für einen Blattknoten? Da machen wir es uns einfach und sagen, dass jeder Blattknoten so groß ist, dass der breiteste String, den wir haben, hineinpasst. Nennen wir das mal leaveWidth.

Die Komponente braucht also eine Breite von n*(leaveWidth+hGap) - hGap.

Welche Höhe hat der Baum? Er verfügt über h = floor(log2(n)) + 1 Ebenen. Alle Knoten haben die gleiche Höhe nodeHeight. Außerdem gehen wir von einem festen Abstand vGap zwischen den Ebenen aus, d. h. die Komponente braucht eine Höhe von h*(nodeHeight + vGap) - vGap.

Sei ab jetzt w die Breite des Baums und h die Höhe der Komponente (in Punkten).

Ab jetzt wird es etwas einfacher: jeder Knoten wird zentriert in einem Bereich eingezeichnet, der durch eine linke Koordinate und eine Breite (l und b) in der Horizontalen begrenzt wird.

Wir beginnen bei der Wurzel. Der Bereich beginnt links bei 0 und hat eine Breite von w, d. h. (l,b) == (0,w). Der zu zeichnende String habe eine Breite von sw. Die x-Koordinate berechnet sich dann mit l + (b-sw)/2. Die y-Koordinate entspricht der Grundlinie, also fm.getAscending().

Die Kindknoten werden dann in den Bereichen (l,b/2) und (l+b/2, b/2) eingezeichnet, wobei die y-Koordinate nach jeder Ebene um vGap erhöht wird. Natürlich kann dann auch jeweils eine Linie eingezeichnet werden.
 
Das ist nicht ganz trivial. Wir können ja mal versuchen, uns ranzutasten :)

Den meisten Platz brauchen offensichtlich die Blattknoten, die in einem festen Abstand zueinander angeordnet werden. Den Abstand bezeichnen wir mal mit hGap.

Außerdem haben wir ein Array mit n Elementen, d. h. wir brauchen Platz für n Blattknoten zzgl. (n-1)*hGap für die Abstände zwischen den Knoten.

Wie groß ist der Platz für einen Blattknoten? Da machen wir es uns einfach und sagen, dass jeder Blattknoten so groß ist, dass der breiteste String, den wir haben, hineinpasst. Nennen wir das mal leaveWidth.

Die Komponente braucht also eine Breite von n*(leaveWidth+hGap) - hGap.

Welche Höhe hat der Baum? Er verfügt über h = floor(log2(n)) + 1 Ebenen. Alle Knoten haben die gleiche Höhe nodeHeight. Außerdem gehen wir von einem festen Abstand vGap zwischen den Ebenen aus, d. h. die Komponente braucht eine Höhe von h*(nodeHeight + vGap) - vGap.

Sei ab jetzt w die Breite des Baums und h die Höhe der Komponente (in Punkten).

Ab jetzt wird es etwas einfacher: jeder Knoten wird zentriert in einem Bereich eingezeichnet, der durch eine linke Koordinate und eine Breite (l und b) in der Horizontalen begrenzt wird.

Wir beginnen bei der Wurzel. Der Bereich beginnt links bei 0 und hat eine Breite von w, d. h. (l,b) == (0,w). Der zu zeichnende String habe eine Breite von sw. Die x-Koordinate berechnet sich dann mit l + (b-sw)/2. Die y-Koordinate entspricht der Grundlinie, also fm.getAscending().

Die Kindknoten werden dann in den Bereichen (l,b/2) und (l+b/2, b/2) eingezeichnet, wobei die y-Koordinate nach jeder Ebene um vGap erhöht wird. Natürlich kann dann auch jeweils eine Linie eingezeichnet werden.
Also, ich versuche mir das jetzt erstmal als Baum-Datenstruktur aufzubauen. Allerdings scheitert es bei mir da schon bei der Insert-Methode. Es soll ja zuerst die Wurzel erzeugt werden. Dann soll solange links eingefügt werden, bis die Länge des Arrays eins beträgt. So weit so gut. Dann muss er aber zurück gehen und rechts weiter machen. Da kriege ich die Rekursion irgendwie nicht hin. Was ich bisher habe:
Java:
public void insert(int[] value) {
        if(root == null) root = new Node(value, null);
        else insert(root, value);
    }
    
    private void insert(Node parent, int[] value) {
        if(parent.getLeft() == null) parent.setLeft(new Node(value, parent));
        else {
            if(parent.getLeft().getValue().length == 1) {
                if(parent.getRight() == null) {
                    parent.setRight(new Node(value, parent));
                }
            } else {
                insert(parent.getLeft(), value);
            }
        }
    }
Wichtig hierbei ist ja nicht, dass nach Größe sortiert wird, sondern dass die Struktur wie im Bild oben entsteht.

Zur Ausgabe habe ich eine Preorder-Funktion, wäre schön wenn mir da noch jemand sagen könnte, ob die richtig ist.
Java:
public void preorder(Node node) {
        System.out.println("out"+node.getValueString());
        if(node.getLeft() != null) {
            preorder(node.getLeft());
        }
        if(node.getRight() != null) {
            preorder(node.getRight());
        }
    }
Am wichstigsten ist mir natürlich die insert-Methode.
 
Das ist einfach ein binärer Suchbaum. Als Schlüssel verwendest Du die Mitte des Indexbereichs:

Java:
        public int[] sort(int l, int r) {
Schlüssel: (l+r)/2
 
Sagen wir mal, Du hast ein Array mit 16 Elementen. Dann wird sort(0,16) (16 exclusive) für die Wurzel aufgerufen. Der Schlüssel wäre (0+16)/2 == 8.

In sort wird sort rekursiv aufgerufen: sort(0,8) und sort(8,16), entsprechend dem linken und dem rechten Kind der Wurzel. Die Schlüssel sind (0+8)/2 == 4 und (8+16)/2 == 12.

Bei sort(0,8) wird nun wieder rekursiv aufgerufen: sort(0,4) und sort(4, 8). Die Schlüssel sind (0+4)/2 == 2 und (4+8)/2 == 6.
Bei sort(8,16) wird auch rekursiv aufgerufen: sort(8,12) und sort(12,16). Die Schlüssel sind (8+12)/2 == 10 und (12+16)/2 == 14.

Fügst Du also die Arrays entsprechend der Schlüssel in den Baum ein, erhältst Du (Darstellung ohne die Arrays):
Code:
          8
         / \ 
        /   \
       4    12
      / \   / \
     2  6  10 14
Und so weiter, also einen Baum, der genau den Aufrufen entspricht.
 
Sagen wir mal, Du hast ein Array mit 16 Elementen. Dann wird sort(0,16) (16 exclusive) für die Wurzel aufgerufen. Der Schlüssel wäre (0+16)/2 == 8.

In sort wird sort rekursiv aufgerufen: sort(0,8) und sort(8,16), entsprechend dem linken und dem rechten Kind der Wurzel. Die Schlüssel sind (0+8)/2 == 4 und (8+16)/2 == 12.

Bei sort(0,8) wird nun wieder rekursiv aufgerufen: sort(0,4) und sort(4, 8). Die Schlüssel sind (0+4)/2 == 2 und (4+8)/2 == 6.
Bei sort(8,16) wird auch rekursiv aufgerufen: sort(8,12) und sort(12,16). Die Schlüssel sind (8+12)/2 == 10 und (12+16)/2 == 14.

Fügst Du also die Arrays entsprechend der Schlüssel in den Baum ein, erhältst Du (Darstellung ohne die Arrays):
Code:
          8
         / \
        /   \
       4    12
      / \   / \
     2  6  10 14
Und so weiter, also einen Baum, der genau den Aufrufen entspricht.
Das klingt schon irgendwie logisch, ich weiß nur trotzdem nicht so recht, wie ich das in Code umsetzten soll.
 
OK, so aus dem Kopf heraus:
Java:
class Node {
    public static final Node EMPTY = new Node() {
        @Override
        protected boolean isEmptyNode() { return true; }
        @Override
        public Node getLeft() { return this; }
        @Override
        public Node getRight() { return this; }
    };

    private int[] value;
    private int key;
    private Node left;
    private Node right;

    private Node() {}

    public Node(int key, int[] value) {
        this.key = key;
        this.value = value;
        left = EMPTY;
        right = EMPTY;
    }

    protected boolean isEmptyNode() { return false; }

    public Node insert(Node node) {
        if (this.isEmptyNode()) {
            return node;
        } else {
            if (node.key < key) {
                left = left.insert(node);
            } else if (node.key > key) {
                right = right.insert(node);
            }
            return this;
        }
    }

    public int[] getValue() { return value; }
    public int getKey() { return key; }
    public Node getLeft() { return left; }
    public Node getRight() { return right; }
}
Damit kannst Du irgendwo einen Baum verwalten, den Du zu Beginn mit Node.EMPTY initialisierst. In sort kopierst Du den aktuell betrachteten Ausschnitt des Arrays, der von l bis r geht, in ein neues Array. Zusammen mit dem Schlüssel (l+r)/2 ergibt dies dann einen Node, den Du in Deinen Baum einfügen kannst: tree = tree.insert(newNode);.
 
Okay, dazu habe ich aber noch ein paar Fragen:
1. Ist das denn auch rekursiv, weil irgendwie habe ich das Gefühl, dass einfach immer der alter Baum überschrieben wird und am Ende nicht alle 19 Arrays gespeichert sind.
2. Gäbe es in diesem System auch die Möglichkeit für jeden Node den Parent-Node zu speichern?
3. Wie würde ich das Ganze ausgeben?
 
Ist das denn auch rekursiv, weil irgendwie habe ich das Gefühl, dass einfach immer der alter Baum überschrieben wird und am Ende nicht alle 19 Arrays gespeichert sind.
Die insert-Methode arbeitet rekursiv. Wenn Du auf tree = tree.insert(...) anspielst: das liegt nur daran, weil der Baum leer sein kann und beim Einfügen dann eine neue Wurzel erhält.

Gäbe es in diesem System auch die Möglichkeit für jeden Node den Parent-Node zu speichern?
Natürlich. Brauchst Du aber zum Zeichnen nicht.

Wie würde ich das Ganze ausgeben?
Du kannst dem Spaß eine Visitor-Methode hinzufügen:
Java:
    public void preorder(Consumer<Node> c) {
        if (isEmptyNode()) { return; }
        c.accept(this);
        preorder(left);
        preorder(right);
    }
 
Die insert-Methode arbeitet rekursiv. Wenn Du auf tree = tree.insert(...) anspielst: das liegt nur daran, weil der Baum leer sein kann und beim Einfügen dann eine neue Wurzel erhält.


Natürlich. Brauchst Du aber zum Zeichnen nicht.


Du kannst dem Spaß eine Visitor-Methode hinzufügen:
Java:
    public void preorder(Consumer<Node> c) {
        if (isEmptyNode()) { return; }
        c.accept(this);
        preorder(left);
        preorder(right);
    }
Also ich checke es nicht... Ich habe jetzt in meiner Klasse eine Variable tree. Im Constructor mache ich
Code:
this.tree = Node.EMPTY;
meine run-Methode sieht so aus:

Code:
public void run() {
    tree = tree.insert(new Node((data.length-1) / 2, data));
    sort(0, data.length-1);
    tree.preorder(tree);
    panel.setDefault();
}
und die sort-Methode so:
Code:
public int[] sort(int l, int r) {
            int[] tempArr = new int[r-l+1];
            int c = 0;
            for(int m = l; m <= r; m++) {
                tempArr[c] = data[m];
                c++;
            }
            tree.insert(new Node((l+r)/2, tempArr));
            treepanel.addData(tempArr,tree);
            //System.out.println(Arrays.toString(tempArr));
            if (l < r) {
                int q = (l + r) / 2;
                sort(l, q);
                sort(q+1, r);
                merge(l, q, r);
         
            }
            return data;
        }
Deine Ausgabe-Methode geht auch nicht, weil die übergebenen Parameter kein Consumer sind und die sich irgendwie auch nicht casten lassen. Ich habe versucht das so umzuschreiben:
Code:
public void preorder(Node c) {
        if (isEmptyNode()) { return; }
        System.out.println(Arrays.toString(value));
        preorder(left);
        preorder(right);
    }
Allerdings bekomme ich da in der Ausgabe immer nur das Selbe, nämlich das Array, das als erstes eingegeben wurde, bis ein java.lang.StackOverflowError kommt. Liegt das jetzt daran, dass das Zeug falsch eingefügt oder nur falsch ausgegeben wird?
 
UPDATE:
Ich habe jetzt meinen ursprünglichen Baum so modifiziert, dass es funktioniert:
Tree.java:
Java:
package data;

public class Tree {

    private Node root;
    
    public Tree() {
        root = null;
    }
    
    public void insert(int[] value, int key) {
        if(root == null) root = new Node(value, key);
        else insert(root, value, key);
    }
    
    private void insert(Node parent, int[] value, int key) {
        if(parent.key > key) {
            if(parent.getLeft() == null) parent.setLeft(new Node(value, key));
            else insert(parent.getLeft(), value, key);
        } else {
            if(parent.getRight() == null) parent.setRight(new Node(value, key));
            else insert(parent.getRight(), value, key);
        }
    }
    
    public void preorder(Node node) {
        System.out.println("out"+node.getValueString());
        if(node.getLeft() != null) {
            preorder(node.getLeft());
        }
        if(node.getRight() != null) {
            preorder(node.getRight());
        }
    }
    

    public Node getRoot() {
        return root;
    }
    
}
Node.java:
Java:
package data;

import java.util.Arrays;

public class Node {
    private int[] value;
    private Node left, right;
    public int key;
    
    public Node(int[] value, int key) {
        this.value = value;
        this.key = key;
    }
    
    public int[] getValue() {
        return value;
    }
    
    public String getValueString() {
        return Arrays.toString(value);
    }
    
    public Node getLeft() {
        return left;
    }
    
    public Node getRight() {
        return right;
    }
    
    public void setLeft(Node left) {
        this.left = left;
    }
    
    public void setRight(Node right) {
        this.right = right;
    }
}
Da hätte ich nur nochmal ne kleine Design-Frage: ist es besser eine Variable als public zu definieren oder lieber als private mit Getter & Setter?
 
Deine Ausgabe-Methode geht auch nicht, weil die übergebenen Parameter kein Consumer sind und die sich irgendwie auch nicht casten lassen.
Naja, ich schreibe den Code hier nur in den Editor, um die Grundidee zu zeigen. D. h. es kann durchaus sein, dass da Fehler enthalten sind. Konkret habe ich mich beim rekursiven Aufruf von preorder verschrieben:
Java:
    public void preorder(Consumer<Node> c) {
        if (isEmptyNode()) { return; }
        c.accept(this);
        left.preorder(c);
        right.preorder(c);
    }
Das ist übrigens keine Ausgabe-Methode sondern ein Visitor, mit dem die Knoten in preorder-Reihenfolge besucht werden. Die Methode funktioniert, wenn man eine Implementierung von java.util.function.Consumer mitgibt, z. B.
Java:
tree.preorder(new Consumer<Node>() {
    public void accept(Node n) {
        // mach was mit n
    }
});
Der Unterschied ist, dass es nun nicht mehr von der Klasse Node sondern vom Aufrufer abhängig ist, was mit dem besuchten Node passiert. Die Schreibweise lässt sich mit Methodenreferenzen und Lambdas schön verkürzen:
Java:
tree.preorder(n -> System.out.println(n.getKey() + ": " + Arrays.toString(n.getValuae()));
Da hätte ich nur nochmal ne kleine Design-Frage: ist es besser eine Variable als public zu definieren oder lieber als private mit Getter & Setter?
Oh, die Frage führt zu einem ganz zentralen Punkt. In der Objektorientierung geht es um Abstraktion, will man doch abstrakte Datentypen umsetzen. Andererseits stellt nicht jede Klasse einen solchen Datentyp dar bzw. braucht man manchmal einfach zusammengesetzte Datentypen, die einfach nur als Datencontainer dienen. Dort dienen Getter und Setter lediglich der Zugriffskontrolle, da das Implementierungsdetail sowieso nach außen getragen wird. Wenn keine Zugriffskontrolle notwendig ist, kann man sich die Methoden auch sparen.

Der Code hier kann diesbezüglich als schlechtes Beispiel dienen. Wenn Du meine Node-Klasse nimmst, werden dort Schlüssel und Werte konkreter Typen gespeichert und diese werden ebenso konkret einfach nach außen gegeben (getKey(), getVaue()). Es findet keinerlei Prüfung statt. Zugute halten kann man der Implementierung diesbezüglich nur, dass es keine Setter gibt.

Bzgl. left und right sieht die Sache dagegen anders aus. Wir haben zwar zwei Methoden, die getLeft() und getRight() heißen, deren Aufgabe besteht aber nicht darin left und right zurückzugeben. Die Aufgabe der Methoden besteht darin, den Wurzelknoten des linken bzw. rechten Teilbaums zu liefern. Dass sie in der Klasse Node die Attribute left bzw. right zurückgeben, ist ein Implementierungsdetail, wie man an Node.EMPTY schön sieht. Dort wird einfach this geliefert.
 
Ich hätte jetzt noch eine weitere Frage: Wie finde ich die Tiefe eines Elements heraus?
Ich habe es so versucht:

Java:
public int getElementDepht(int key) {
        int d = 0;
            if(root.key != key) {
                if(key > root.key) {
                    if(root.getRight() != null) d = getElementDepht(key, root.getRight()) + 1;
                } else {
                    if(root.getLeft() != null)d = getElementDepht(key, root.getLeft()) + 1;
                }
            }
        return d;
    }

    private int getElementDepht(int key, Node parent) {
        int d = 0;
        if(parent != null && parent.key != key) {
            if(key > root.key) {
                if(root.getRight() != null) d = getElementDepht(key, parent.getRight()) + 1;
            } else {
                if(root.getLeft() != null) d = getElementDepht(key, parent.getLeft()) + 1;
            }
        }
        return d;
    }
Allerdings stimmen die Ausgaben nicht immer. Ich habe auch das Gefühl, dass in meinem System Schlüssel in mehreren tiefen mehrfach vorkommen. Also muss ich wahrscheinlich mit dem value, also einem int[] suchen, wobei ich da noch weniger weiß wie das gehen soll.
 
Also muss ich wahrscheinlich mit dem value, also einem int[] suchen, wobei ich da noch weniger weiß wie das gehen soll.
Das solltest Du nicht tun, dazu brauchst Du einen Durchlauf.

Java:
public int getElementDepht(int key) {
    return getElementDepth(key, root);
}
Ich habe auch das Gefühl, dass in meinem System Schlüssel in mehreren tiefen mehrfach vorkommen.
Du fängst den Fall parent.key == key nicht ab (wobei das der Parameter besser root statt parent heißen sollte).
 
Damit ist das Problem, dass ein Schlüssel mehrfach vorkommt, z.B. der Schlüssel 6 einmal in Tiefe 2 und 4, doch noch nicht gelöst?
Bzw wenn ich parent.key == key mache, was soll ich dann machen? Weil ich weiß ja nicht, ob der Schlüssel nochmal vorkommt, also müsste ich dann prüfen, ob er nochmal kommt und ohne die Werte zu vergleichen weiß ich doch nicht, welche Tiefe jetzt die richtige ist.
 
Zuletzt bearbeitet:
Lass bei der Berechnung des Schlüssels die Division einfach weg. Dann ist der Schlüssel l+r.
Das ändert leider auch nichts daran, dass manche Schlüssel mehrfach vorkommen

Code:
l: 
l: 0 r: 9 key: 9
l: 0 r: 4 key: 4
l: 0 r: 2 key: 2
l: 0 r: 1 key: 1
l: 0 r: 0 key: 0
l: 1 r: 1 key: 2
l: 2 r: 2 key: 4
l: 3 r: 4 key: 7
l: 3 r: 3 key: 6
l: 4 r: 4 key: 8
l: 5 r: 9 key: 14
l: 5 r: 7 key: 12
l: 5 r: 6 key: 11
l: 5 r: 5 key: 10
l: 6 r: 6 key: 12
l: 7 r: 7 key: 14
l: 8 r: 9 key: 17
l: 8 r: 8 key: 16
l: 9 r: 9 key: 18
 
Zuletzt bearbeitet:
Das ändert leider auch nichts daran, dass manche Schlüssel mehrfach vorkommen
Habe da jetzt ne andere Idee:
Java:
private ArrayList<int[]> info;

 public void run() {
     info = new ArrayList<int[]>();
     sort(0, data.length-1);
 }

public int[] sort(int l, int r) {
    int[] tempArr = new int[r-l+1];
    int c = 0;
    for(int m = l; m <= r; m++) {
        tempArr[c] = data[m];
        c++;
    }
    if (l < r) {
        int q = (l + r) / 2;
        sort(l, q);
        info.add(tempArr);
        double key = info.indexOf(tempArr);
        sort(q+1, r);
        merge(l, q, r);
    } else {
        info.add(tempArr);
        double key = info.indexOf(tempArr);
        treepanel.addData(tempArr, key);
    }
    return data;
}
Ich habe eine ArrayList, der ich die Obkejte hinzufüge und der index in der ArrayList ist der Schlüssel. Problem ist hierbeim aber, dass zwar alles den richtigen schlüssel hat ich für die insert methode diese aber vor der if(l < r) aufrufen müsste, ich da aber den schlüssel noch nicht habe, also so:
Java:
public int[] sort(int l, int r) {
            int[] tempArr = new int[r-l+1];
            int c = 0;
            for(int m = l; m <= r; m++) {
                tempArr[c] = data[m];
                c++;
            }
            
            /////////////////////////////////////////////////
            double key = info.indexOf(tempArr);
            treepanel.addData(tempArr, key);
            /////////////////////////////////////////////////
            Problem: objekt wird erst später hinzugrfügt, also kann ich den index hier noch nicht bekommen
            
            if (l < r) {
                int q = (l + r) / 2;
                sort(l, q);
                    info.add(tempArr);
                sort(q+1, r);
                merge(l, q, r);
            } else {
                info.add(tempArr);
            }
            return data;
        }
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben