Interface Baum visualisieren

Diskutiere Baum visualisieren im Java Basics - Anfänger-Themen Bereich.
mihe7

mihe7

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

mihe7

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

UnknownInnocent

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

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...*.
 
mihe7

mihe7

It's your turn :p Mir fällt gerade nichts ein, wie man das einfach hinbekommen würde.
 
X

Xyz1

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

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

UnknownInnocent

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?
 
X

Xyz1

Ok, ich helfe Dir...

Wie ist der Ist-Stand (Quelltext...) und der Soll-Stand bisher?
 
UnknownInnocent

UnknownInnocent

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.
 
Thema: 

Baum visualisieren

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben