Interface Baum visualisieren

CptK

Bekanntes Mitglied
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
 

mihe7

Top Contributor
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.
 

CptK

Bekanntes Mitglied
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.
 

mihe7

Top Contributor
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
 

mihe7

Top Contributor
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.
 

CptK

Bekanntes Mitglied
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.
 

mihe7

Top Contributor
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);.
 

CptK

Bekanntes Mitglied
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?
 

mihe7

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

CptK

Bekanntes Mitglied
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?
 

CptK

Bekanntes Mitglied
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?
 

mihe7

Top Contributor
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.
 

CptK

Bekanntes Mitglied
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.
 

mihe7

Top Contributor
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).
 

CptK

Bekanntes Mitglied
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:

CptK

Bekanntes Mitglied
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:

CptK

Bekanntes Mitglied
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;
        }
 

mihe7

Top Contributor
Das ändert leider auch nichts daran, dass manche Schlüssel mehrfach vorkommen
OMG, bin ich blöd, das kann so und so nicht funktionieren, weil die Intervallgrenzen ganzzahlig sind. Dann nimmst Du halt das Intervall als Schlüssel. Du fügst in den linken Teilbaum ein, wenn die rechte Grenze des Schlüssels kleiner als die rechte Grenze des Wurzel-Schlüssels ist, ansonsten in den rechten Teilbaum.
 

mihe7

Top Contributor
Hier mal ein zusammengeschusteter Ansatz.

Java:
public class MergeSort {
    public interface SortingListener {
        void sorting(int[] arr, int l, int r);
    }

    private SortingListener listener;

    public void setSortingListener(SortingListener listener) {
        this.listener = listener;
    }

    public void sort(int[] data) {
        sort(data, 0, data.length);
    }
    
    private void sort(int[] arr, int l, int r) {
        sorting(arr, l, r);

        int size = r-l;
        if (size < 2) {
            return;
        }

        int m = (l+r)/2;
        sort(arr, l, m);
        sort(arr, m, r);
        merge(arr, l, m, r);
    }

    private void merge(int[] arr, int l, int m, int r) {
        int size = r-l;
        int[] copy = new int[size];
        System.arraycopy(arr, l, copy, 0, size);

        int nl = 0;
        int nr = size-1;

        for (int i = l; i < r; i++) {
            if (copy[nl] <= copy[nr]) {
                arr[i] = copy[nl];
                nl++;
            } else {
                arr[i] = copy[nr];
                nr--;
            }
        }
    }

    private void sorting(int[] arr, int l, int r) {
        if (listener != null) {
            listener.sorting(arr, l, r);
        }
    }
}

Java:
public class Node {
    public static class Entry {
        final int left;
        final int right;
        final int[] data;

        public Entry(int left, int right, int[] data) {
            this.left = left;
            this.right = right;
            this.data = data;
        }

        public boolean overlaps(Entry e) {
            return left < e.right && right > e.left;
        }

        public boolean isLeftOf(Entry e) {
            return right < e.right;
        }
    }

    static Node EMPTY = new Node() {
        @Override
        public boolean isEmpty() { return true; }
        @Override
        public Node leftTree() { return this; }
        @Override
        public Node rightTree() { return this; }
    };

    private Entry value;
    private Node left, right;

    private Node() {}

    public Node(Entry value) {
        this.value = value;
        right = left = EMPTY;
    }

    public boolean isEmpty() { return false; }
    public Entry getValue() { return value; }
    public Node leftTree() { return left; }
    public Node rightTree() { return right; }
    
    public Node insert(Entry newValue) {
        if (isEmpty()) {
            return new Node(newValue);
        } else if (value.overlaps(newValue)) {
            if (shouldBeInLeftTree(newValue)) {
                left = left.insert(newValue);
            } else {
                right = right.insert(newValue);
            }
        }
        return this;
    }

    private boolean shouldBeInLeftTree(Entry entry) {
        return left.isEmpty() && entry.isLeftOf(value) ||
                !left.isEmpty() && left.value.overlaps(entry);
    }
}

Java:
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.util.Arrays;
import javax.swing.JPanel;

public class TreePanel extends JPanel {
    private Node tree = Node.EMPTY;

    private int hGap = 10;
    private int vGap = 30;
    

    public void setTree(Node root) {
        tree = root;
        repaint();
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        if (tree.isEmpty()) {
            return;
        }

        int[] data = tree.getValue().data;
        int entryWidth = maxEntryWidth(data, g.getFontMetrics());
        int width = data.length*(entryWidth + hGap) - hGap;
        paintNode(tree, width, 0, 0, g);
    }

    private int maxEntryWidth(int[] data, FontMetrics fm) {
        int[] entry = new int[1];
        int max = 0;
        for (int value : data) {
            entry[0] = value;
            int w = fm.stringWidth(Arrays.toString(entry));
            if (w > max) { max = w; }
        }
        return max;
    }

    private void paintNode(Node node, int width, int x, int y, Graphics g) {
        if (node.isEmpty()) {
            return;
        }
        FontMetrics fm = g.getFontMetrics();
        int cy = y + fm.getAscent();
        String text = Arrays.toString(node.getValue().data);
        int cx = x + (width - fm.stringWidth(text))/2;
        g.drawString(text, cx, cy);
        if (!node.leftTree().isEmpty()) {
            g.drawLine(x+width/2, y+fm.getHeight(), x + width/4, y+fm.getHeight()+vGap);
            paintNode(node.leftTree(), width/2, x, y+fm.getHeight()+vGap, g);
        }
        if (!node.rightTree().isEmpty()) {
            g.drawLine(x+width/2, y+fm.getHeight(), x + 3*width/4, y+fm.getHeight()+vGap);
            paintNode(node.rightTree(), width/2, x+width/2, y+fm.getHeight()+vGap, g);
        }
    }
}

Java:
import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Arrays;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.SwingUtilities;

public class Main {

    private int[] data = {8,7,6,5,4,3,2,1};
    private Node tree = Node.EMPTY;
    private TreePanel panel = new TreePanel();
    private MergeSort mergeSort = new MergeSort();
    private Thread background = null;

    private ActionListener sortAction = new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            if (background != null && background.isAlive()) {
                return;
            }
            tree = Node.EMPTY;
            panel.setTree(tree);
            int[] tmp = new int[data.length];
            System.arraycopy(data,0, tmp, 0, data.length);
            background = new Thread(() -> mergeSort.sort(tmp));
            background.setPriority(Thread.MIN_PRIORITY);
            background.start();
        }
    };

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> new Main().run());
    }

    public void run() {
        mergeSort.setSortingListener(this::insert);
        JButton button = new JButton("Sortieren");
        button.addActionListener(sortAction);
        
        JFrame frame = new JFrame("Merge Sort");
        frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        frame.add(panel);
        frame.add(button, BorderLayout.SOUTH);
        frame.setSize(600,400);
        frame.setVisible(true);
    }

    private void insert(int[] arr, int left, int right) {
        int[] data = new int[right-left];
        System.arraycopy(arr, left, data, 0, data.length);
        SwingUtilities.invokeLater(() -> {
            tree = tree.insert(new Node.Entry(left, right, data));
            panel.setTree(tree);
        });
        sleep(250);
    }

    private void sleep(long ms) {
        try {
            Thread.sleep(ms);
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        }
    }
}
 

CptK

Bekanntes Mitglied
Hallo,
ich hatte das Projekt erst einmal auf Eis gelegt, deshalb die späte Antwort. Das was du geschickt hast ist schon mal genial.

12873

Allerdings war das erst die Hälfte. Bisher wird der Teil des Sortierens (im Bild das Schwarze) gezeichnet. Nun fehlt noch der zweite Teil, das Merging (im Bild das Blaue). Gibt es einfache Möglichkeit das im Code noch hinzuzufügen?
 
X

Xyz1

Gast
War nicht so gemeint... Manche schreiben auch so dass komplett nichts zu erkennen ist. ;)
Ich schaue es mir später an sobald ich wieder am PC bin...*.
 
X

Xyz1

Gast
@mihe7 Jetzt mach Du bitte weiter, habe dazu keinen Nerv.

Zudem, so wie es aussieht, habt ihr den conquer Schritt doch schon.
 

CptK

Bekanntes Mitglied
Wäre es möglich, das Ganze mit dem Array der in meiner Abbildung ganz unten steht durchlaufen zu lassen und anstatt von oben nach unten einfach von unten nach oben zu zeichnen?
 

CptK

Bekanntes Mitglied
Der ist_Stand ist im prinzip der code den mihe7 weiter oben gesendet hat weil ich alle Veränderung, nachdem sie nicht funktioniert haben, frustriert wieder gelöscht habe. Der Soll-Stand ist, dass der gesamte Baum, den ich in dem Bild geschickt habe gezeichnet wird und nicht nur der Halbe wie in mihes code.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D spezifische Knoten in einem Baum zählen Java Basics - Anfänger-Themen 9
HelpInneed Baum ausgeben (aber mal anders) Java Basics - Anfänger-Themen 3
G AVL-Baum Java Basics - Anfänger-Themen 1
G Rot-Schwarz-Baum Java Basics - Anfänger-Themen 8
L Baum aus Integer Liste erstellen Java Basics - Anfänger-Themen 0
CptK Best Practice Merge-Sort als Baum darstellen Java Basics - Anfänger-Themen 3
E Baum pfadweise durchlaufen Java Basics - Anfänger-Themen 11
O Naives links rechts einfügen in ADT Baum Java Basics - Anfänger-Themen 8
L Traversierungsverfahren Baum: LevelOrder Java Basics - Anfänger-Themen 17
L Rekursion im Baum Java Basics - Anfänger-Themen 9
L Baum Knoten zählen Java Basics - Anfänger-Themen 6
L B+Baum innere Knoten erstellen Java Basics - Anfänger-Themen 3
D B-Baum einfügen und löschen Java Basics - Anfänger-Themen 2
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
D Werte AVL-Baum löschen Java Basics - Anfänger-Themen 2
M Binären Baum Kinder setzen Java Basics - Anfänger-Themen 12
U 2-3-4 Baum Top-Down Java Basics - Anfänger-Themen 4
U 2-3-4 Baum Top-Down Java Basics - Anfänger-Themen 0
J Überprüfen, ob eine 2D Matrix ein Baum ist Java Basics - Anfänger-Themen 5
R Baum erzeugen Java Basics - Anfänger-Themen 61
B Baum Traversierung Postorder Java Basics - Anfänger-Themen 6
B OOP Über einen AVL-Baum iterieren (NullPointer) Java Basics - Anfänger-Themen 5
A Voller Baum Java Basics - Anfänger-Themen 7
S n-ärer Baum Java Basics - Anfänger-Themen 6
O Unterschied Baum <-> Automat Java Basics - Anfänger-Themen 2
K Tiefen- und Breitensuche beim Baum durch Stack und Warteschlange Java Basics - Anfänger-Themen 1
C kompletter baum Java Basics - Anfänger-Themen 2
M Collections Iterator und generischer Baum Java Basics - Anfänger-Themen 0
M Baum Code kurze frage ... Java Basics - Anfänger-Themen 6
D Ein Objekt in einem Baum finden und ausgeben. Java Basics - Anfänger-Themen 4
K Rot-Schwarz-Baum min und max-Tiefe Java Basics - Anfänger-Themen 1
A min() Methode Baum Java Basics - Anfänger-Themen 1
J Baum rekursiv durchlaufen Java Basics - Anfänger-Themen 2
J Baum Knoten löschen Java Basics - Anfänger-Themen 10
T Baum mit Turtle zeichnen Java Basics - Anfänger-Themen 2
Screen 2,4 Baum Frage Java Basics - Anfänger-Themen 6
T Rot-schwarz Baum Problem Java Basics - Anfänger-Themen 3
A Rekursion in Baum und ArrayList als Rückgabe Java Basics - Anfänger-Themen 2
P Pythagoras Baum - Berechnung der Punkte Java Basics - Anfänger-Themen 9
C 2-3 Baum Java Basics - Anfänger-Themen 6
H Baum Java Basics - Anfänger-Themen 4
L Rot Scharz Baum von Binärbaum erben Java Basics - Anfänger-Themen 9
B Baum > Baum-Swing Java Basics - Anfänger-Themen 4
L eigenen Baum schreiben Java Basics - Anfänger-Themen 5
Luk10 Anzahl der Knoten in einem Baum ausgeben! Java Basics - Anfänger-Themen 6
T Array in einen Baum zu überführen Java Basics - Anfänger-Themen 3
S Das reinschreiben einer Klasse in den Baum Java Basics - Anfänger-Themen 6
H B-Baum: Knoten Position als Parameter oder als Variable im Objekt? Java Basics - Anfänger-Themen 4
A Baum mit geometricfigur Werte Java Basics - Anfänger-Themen 6
D Datentypen Einfügen im RotSchwarz Baum Java Basics - Anfänger-Themen 2
F FileSystem in Baum darstellen/wurzel festlegen Java Basics - Anfänger-Themen 3
G List als Rückgabewert einer rekursiven Methode (Baum) Java Basics - Anfänger-Themen 3
I Baum graphisch darstellen Java Basics - Anfänger-Themen 2
P Binärer Baum mit Composite-Entwurfsmuster Java Basics - Anfänger-Themen 2
L Baum Swing AVL Java Basics - Anfänger-Themen 4
Binary.Coder 2-3-4 Baum vs. (2,4) Baum Java Basics - Anfänger-Themen 2
ModellbahnerTT Ab-Baum Applet Java Basics - Anfänger-Themen 3
P Baum-Menü in Java Java Basics - Anfänger-Themen 5
H Baum Java Basics - Anfänger-Themen 11
G AVL Baum Java Basics - Anfänger-Themen 20
J Baum spiegeln Java Basics - Anfänger-Themen 7
N 2-3 Baum, Einfügen Java Basics - Anfänger-Themen 5
G Rekursion mit Return - Baum durchlaufen Java Basics - Anfänger-Themen 4
G Baum Datenstruktur Java Basics - Anfänger-Themen 2
V Baum mit log n Aufwand für Einfügen und Löschen und. Java Basics - Anfänger-Themen 5
H Tiefensuche im binären Baum Java Basics - Anfänger-Themen 2
P Problem mit Darstellung im Baum Java Basics - Anfänger-Themen 4
G Binärer Baum Java Basics - Anfänger-Themen 3
M Binärer Baum Tiefe Java Basics - Anfänger-Themen 14
G universeller baum Java Basics - Anfänger-Themen 13
G Baum testen Java Basics - Anfänger-Themen 20
B Array To Baum Java Basics - Anfänger-Themen 2
B Baum to Array Java Basics - Anfänger-Themen 17
H Löschen in einem binären Baum führt zu einem StackOverflow Java Basics - Anfänger-Themen 2
L Binären Baum speichern Java Basics - Anfänger-Themen 6
R Pythagoras-Baum Java Basics - Anfänger-Themen 5
W Baum durchlaufen Java Basics - Anfänger-Themen 3
T binärer Baum Java Basics - Anfänger-Themen 3
G eine Knoten aus einem Baum löschen. [SOLVED] Java Basics - Anfänger-Themen 7
P allg. Baum aus Liste Java Basics - Anfänger-Themen 2
J String in binären Baum umwandeln Java Basics - Anfänger-Themen 7
R binärer Baum Java Basics - Anfänger-Themen 2
F Abstrakte Klasse Baum Java Basics - Anfänger-Themen 6
CptK Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
R Sensordaten visualisieren Java Basics - Anfänger-Themen 2
H Info von Webserver prüfen und per TrayIcon visualisieren Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Neue Themen


Oben