插入二叉搜索树中节点颜色的动画变化 [英] Animate Change of color of nodes in insertion of binary search tree

查看:32
本文介绍了插入二叉搜索树中节点颜色的动画变化的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我已经实现了二叉搜索树的显示.这是代码,它描绘了jpanel 中的二叉树.

I already have implemented display of binary search tree . Here's the code , which paints the binary tree in a jpanel .

public void paint(Graphics g) {
    super.paint(g);
    System.out.println(" in paint");
    Graphics2D g2 = (Graphics2D) g;
    g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
            RenderingHints.VALUE_ANTIALIAS_ON);
    int num = bst.size;

    int y = 25;
    int nodes = 1;
    int level = 1;
    int length = getWidth();
    Queue<Node> q = new LinkedList<Node>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    q.add(bst.root);
    while (num > 0) {

        int pX = (int) Math.round(length / (2.0 * nodes));
        int x = pX;
        for (int i = 0; i < nodes; i++) {
            Node n = q.poll();
            //
            if (n != null) {
                num--;
                System.out.println(x);
                g2.setColor(Color.BLUE);
                String str = n.value + "";
                 System.out.println(str);
                //Font f = Font.getFont(str);
                int width = str.length();
                g2.setColor(Color.YELLOW);
                g2.fillOval(x, y, (30 - 2 * level)+width*3, (30 - 2 * level));
                g2.setColor(Color.black);
                g2.drawString(n.value + "", x + 10 - level, y + 15);
                g2.setColor(Color.black);
                if (n.left == null)
                    q.add(null);
                else
                    q.add(n.left);
                if (n.right == null)
                    q.add(null);
                else
                    q.add(n.right);
                if (level != 1) {
                    int xx = q2.poll();
                    int yy = q2.poll();
                    g2.drawLine(xx+width*2, yy, x + (15 - 1 * level)+width*2, y);
                }
            } else {
                q2.poll();
                q2.poll();
                q.add(null);
                q.add(null);
            }
            q2.add(x);
            q2.add(y + 15 - level);
            q2.add(x + 30 - 2 * level);
            q2.add(y + 15 - level);
            x += 2 * pX;

        }
        y += 40;
        nodes = 1 << level;
        level++;
    }

现在,当我将节点插入到我的树中时,我希望父节点逐渐改变新节点的颜色,然后最终作为子节点加入.或者要插入的新节点沿其父节点的路径移动.或类似的东西下面是一个例子:

Now as i insert nodes into my tree , I want the parent nodes to change color of the new node progressively , and then ultimate join as a child . or the new node to be inserted moves along the path of it's parent . or something similar Here's an example :

我不知道如何使用计时器或类似方法来实现.

I have no idea how to accomplish that , with timer or likewise .

推荐答案

好的,这比我想要的要长一点(10 个月大的孩子没有任何耐心)

Okay, this took a little longer then I wanted (10 month olds don't have any patience)

基本概念围绕着您需要在一段时间内从一种状态变为另一种状态的想法展开.

The basic concept revolves around the idea that you need to change from one state to another over a period of time.

给定开始时间和当前时间,我们可以计算动画已经运行的时间量,并给定总动画时间,当前进度.

Given a start time and the current time, we can calculate the amount of time that the animation has been running, and given the total animation time, the current progress.

通过这个(以及一些聪明的数学),我们可以计算从我们的开始状态到我们的目标状态的当前状态.

With this (and some clever maths) we can calculate the current state from our start state towards our target state.

我也做了运动,所以这可能有点过头了,但基本前提保持不变.

I've done movement as well, so that may be a little over kill, but the basic premise remains the same.

我在动画属性类中放置了有关需要更改的节点的有状态信息,并使用 javax.swing.Timer 来勾选动画(以合理的稳定速率).然后我根据需要更新每个节点的状态并重新绘制屏幕.

I place stateful information about the nodes that need to change in animation properties class and use a javax.swing.Timer to tick over the animation (at a reasonably steady rate). I then update the state of each node as required and repaint the screen.

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.text.NumberFormat;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import javax.management.StringValueExp;
import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.Timer;
import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;

public class AnimateNode {

    public static void main(String[] args) {
        new AnimateNode();
    }

    public AnimateNode() {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
                }

                JFrame frame = new JFrame("Testing");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(new NodePane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }

        });
    }

    public interface Node {
        public void paint(JComponent parent, Graphics2D g2d);
        public void setColor(Color color);
        public Color getColor();
        public Node getParent();
        public Node getLeft();
        public Node getRight();
        public void setLeftNode(Node node);
        public void setRightNode(Node node);
        public Point getLocation();
        public void setLocation(Point p);
    }

    public class DefaultNode implements Node {

        private int number;
        private Node parent;
        private Node left;
        private Node right;
        private Point location;
        private Color color;

        public DefaultNode(int number, Node parent) {
            this.parent = parent;
            color = UIManager.getColor("Panel.background");
            this.number = number;
        }

        public void setLeftNode(Node left) {
            this.left = left;
        }

        public void setRightNode(Node right) {
            this.right = right;
        }

        public Node getParent() {
            return parent;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        @Override
        public Point getLocation() {
            return location;
        }

        @Override
        public void setLocation(Point location) {
            this.location = location;
        }

        @Override
        public void paint(JComponent parent, Graphics2D g2d) {

            FontMetrics fm = g2d.getFontMetrics();
            int radius = fm.getHeight();

            Point p = getLocation();

            int x = p.x - (radius / 2);
            int y = p.y - (radius / 2);

            Ellipse2D node = new Ellipse2D.Float(x, y, radius, radius);

            g2d.setColor(getColor());
            g2d.fill(node);

            g2d.setColor(Color.GRAY);
            g2d.draw(node);

            String text = String.valueOf(number);
            x = x + ((radius - fm.stringWidth(text)) / 2);
            y = y + (((radius - fm.getHeight()) / 2) + fm.getAscent());

            g2d.drawString(text, x, y);

        }

        @Override
        public void setColor(Color color) {
            this.color = color;
        }

        @Override
        public Color getColor() {
            return color;
        }

        @Override
        public String toString() {
            return number + " @ " + getLocation();
        }

    }

    public class AnimationProperties {

        private Point startPoint;
        private Point targetPoint;
        private Color startColor;
        private Color endColor;
        private Node node;

        public AnimationProperties(Node node) {
            this.node = node;
        }

        public Node getNode() {
            return node;
        }

        public void setTargetColor(Color endColor) {
            this.endColor = endColor;
        }

        public void setStartColor(Color startColor) {
            this.startColor = startColor;
        }

        public void setStartPoint(Point startPoint) {
            this.startPoint = startPoint;
        }

        public void setTargetPoint(Point targetPoint) {
            this.targetPoint = targetPoint;
        }

        public Color getTargetColor() {
            return endColor;
        }

        public Color getStartColor() {
            return startColor;
        }

        public Point getStartPoint() {
            return startPoint;
        }

        public Point getTargetPoint() {
            return targetPoint;
        }

        public Point getLocation(float progress) {
            return calculateProgress(getStartPoint(), getTargetPoint(), progress);
        }

        public Color getColor(float progress) {
            return blend(getStartColor(), getTargetColor(), 1f - progress);
        }

        public void update(float progress) {
            node.setLocation(getLocation(progress));
            node.setColor(getColor(progress));
        }

    }

    public class NodePane extends JPanel {

        private int number;
        private Node root;
        private Map<Node, AnimationProperties> aniProperties;
        private Timer animationTimer;
        private Timer startTimer;
        private long startTime;
        private int runTime = 1000;

        public NodePane() {
            aniProperties = new HashMap<>(25);

            root = addLeftNode(null);
            root.setColor(getBackground());
            addMouseListener(new MouseAdapter() {
                private Random rand;

                @Override
                public void mouseClicked(MouseEvent e) {
                    generateNextNode(root);
                    revalidate();
//                    repaint();
                }

                protected void generateNextNode(Node parent) {
                    Node child = null;
                    if (rand == null) {
                        rand = new Random(System.currentTimeMillis());
                    }
                    boolean left = rand.nextBoolean();
                    if (left) {
                        child = parent.getLeft();
                    } else {
                        child = parent.getRight();
                    }

                    if (child == null) {
                        if (left) {
                            addLeftNode(parent);
                        } else {
                            addRightNode(parent);
                        }
                    } else {
                        generateNextNode(child);
                    }
                }

            });

            startTimer = new Timer(250, new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    stopAnimation();
                    startTime = -1;
                    animationTimer.start();
                }

            });
            startTimer.setRepeats(false);

            animationTimer = new Timer(40, new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    if (startTime < 0) {
                        startTime = System.currentTimeMillis();
                    }
                    float progress = 1f;
                    long duration = System.currentTimeMillis() - startTime;
                    if (duration >= runTime) {
                        ((Timer) e.getSource()).stop();
                    } else {
                        progress = (float) duration / (float) runTime;
                    }

                    for (AnimationProperties ap : aniProperties.values()) {
                        ap.update(progress);
                    }

                    repaint();

                    if (progress == 1f) {
                        aniProperties.clear();
                    }

                }

            });
            animationTimer.setRepeats(true);
            animationTimer.setCoalesce(true);
        }

        protected void stopAnimation() {
            if (animationTimer.isRunning()) {
                animationTimer.stop();
                for (AnimationProperties ap : aniProperties.values()) {
                    Node node = ap.getNode();
                    ap.setStartColor(node.getColor());
                    ap.setStartPoint(node.getLocation());
                }
            }
        }

        public Point getStartPoint(Node node) {

            Point startPoint = node.getLocation();
            while (startPoint == null) {
                node = node.getParent();
                startPoint = node.getLocation();
            }

            return startPoint;

        }

        protected void layoutNode(Node node, int x, int y) {

            if (node != null) {

                FontMetrics fm = getFontMetrics(getFont());
                int nodeHeight = fm.getHeight();

                if (node.getParent() != null) {

                    Point p = new Point(x, y);
                    Point sp = getStartPoint(node);

                    if (node.getLocation() == null) {
                        System.out.println("new node " + node);
                    }

                    if (node.getLocation() == null || !p.equals(node.getLocation())) {
                        AnimationProperties ap = new AnimationProperties(node);
                        ap.setStartColor(node.getColor());
                        ap.setTargetColor(getBackground());
                        ap.setStartPoint(sp);
                        ap.setTargetPoint(new Point(x, y));
                        node.setLocation(sp);
                        aniProperties.put(node, ap);
                        System.out.println("New Node to " + node);
                    } else {
                        aniProperties.remove(node);
                    }

                } else {

                    nodeHeight *= 2;

                }

                layoutNode(node.getLeft(), x - nodeHeight, y + nodeHeight);
                layoutNode(node.getRight(), x + nodeHeight, y + nodeHeight);

            }

        }

        @Override
        public void doLayout() {

            System.out.println("DoLayout");
            stopAnimation();

            FontMetrics fm = getFontMetrics(getFont());
            int nodeHeight = fm.getHeight();

            int x = getWidth() / 2;
            int y = nodeHeight;

            if (root != null) {

                root.setLocation(new Point(x, y));
                layoutNode(root, x, y);
//                Node node = root.getLeft();
//                while (node != null) {
//                    x -= nodeHeight;
//                    y += nodeHeight;
//                    layout(node, x, y);
//                    node = node.getLeft();
//                }
//                node = root.getRight();
//                x = getWidth() / 2;
//                y = nodeHeight;
//                while (node != null) {
//                    x += nodeHeight;
//                    y += nodeHeight;
//                    layout(node, x, y);
//                    node = node.getRight();
//                }

            }

            startTimer.restart();

        }

        @Override
        public Dimension getPreferredSize() {
            return new Dimension(200, 200);
        }

        protected Node createNode(Node parent) {
            DefaultNode child = new DefaultNode(++number, parent);
            child.setColor(Color.GREEN);
            System.out.println("Create new node " + child);
            return child;
        }

        protected Node addLeftNode(Node parent) {
            Node node = createNode(parent);
            if (parent != null) {
                System.out.println("Add " + node + " to left of " + parent);
                parent.setLeftNode(node);
            }
            return node;
        }

        protected Node addRightNode(Node parent) {
            Node node = createNode(parent);
            if (parent != null) {
                System.out.println("Add " + node + " to right of " + parent);
                parent.setRightNode(node);
            }
            return node;
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            if (root != null) {

                Graphics2D g2d = (Graphics2D) g.create();

                paintConnectors(root, g2d);
                paintNode(root, g2d);

                g2d.dispose();

            }

        }

        protected void paintNode(Node node, Graphics2D g2d) {
            if (node != null && node.getLocation() != null) {
                node.paint(this, g2d);
                paintNode(node.getLeft(), g2d);
                paintNode(node.getRight(), g2d);
            }
        }

        protected void paintConnectors(Node node, Graphics2D g2d) {
            if (node != null && node.getLocation() != null) {
                Node parent = node.getParent();
                if (parent != null) {
                    g2d.setColor(Color.GRAY);
                    if (parent.getLocation() != null && node.getLocation() != null) {
                        g2d.draw(new Line2D.Float(parent.getLocation(), node.getLocation()));
                    }
                }

                paintConnectors(node.getLeft(), g2d);
                paintConnectors(node.getRight(), g2d);
            }
        }

    }

    public static Point calculateProgress(Point startPoint, Point targetPoint, double progress) {

        Point point = new Point();

        if (startPoint != null && targetPoint != null) {

            point.x = calculateProgress(startPoint.x, targetPoint.x, progress);
            point.y = calculateProgress(startPoint.y, targetPoint.y, progress);

        }

        return point;

    }

    public static int calculateProgress(int startValue, int endValue, double fraction) {

        int value = 0;
        int distance = endValue - startValue;
        value = (int) Math.round((double) distance * fraction);
        value += startValue;

        return value;

    }

    public static Color calculateProgress(Color start, Color target, double progress) {

        return blend(start, target, progress);

    }

    public static Color blend(Color color1, Color color2, double ratio) {
        float r = (float) ratio;
        float ir = (float) 1.0 - r;

        float rgb1[] = new float[3];
        float rgb2[] = new float[3];

        color1.getColorComponents(rgb1);
        color2.getColorComponents(rgb2);

        float red = rgb1[0] * r + rgb2[0] * ir;
        float green = rgb1[1] * r + rgb2[1] * ir;
        float blue = rgb1[2] * r + rgb2[2] * ir;

        if (red < 0) {
            red = 0;
        } else if (red > 255) {
            red = 255;
        }
        if (green < 0) {
            green = 0;
        } else if (green > 255) {
            green = 255;
        }
        if (blue < 0) {
            blue = 0;
        } else if (blue > 255) {
            blue = 255;
        }

        Color color = null;
        try {

            color = new Color(red, green, blue);

        } catch (IllegalArgumentException exp) {

            NumberFormat nf = NumberFormat.getNumberInstance();
            System.err.println(nf.format(red) + "; " + nf.format(green) + "; " + nf.format(blue));

        }
        return color;
    }

}

用简单的例子更新;)

好的,这是一个简单的例子.基本上,它只是使节点闪烁...

Okay, this is a simple example. Basically, it just blinks the node...

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Ellipse2D;
import java.text.NumberFormat;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;
import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;

public class BlinkNode {

    public static void main(String[] args) {
        new BlinkNode();
    }

    public BlinkNode() {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
                }

                JFrame frame = new JFrame("Testing");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(new TestPane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }

    public class TestPane extends JPanel {

        // Animation stuff
        private Timer aniTimer;
        // The amount of time that each animation cycle plays for 
        // in millis
        private int aniRunTime = 1000;
        // The time the animation was started
        private long startTime = -1;

        // Our color ranges, where to start and where
        // we want to get to and the current state...
        private Color startColor;
        private Color targetColor;
        private Color color;

        public TestPane() {
            // Initial state
            startColor = getBackground();
            targetColor = Color.GREEN;
            color = startColor;
            aniTimer = new Timer(40, new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    // Set the start time it hasn't already
                    if (startTime < 0) {
                        startTime = System.currentTimeMillis();
                    }
                    // We're always finished if we run over time...
                    float progress = 1f;
                    // Calculate the duration of play
                    long duration = System.currentTimeMillis() - startTime;
                    // Have we reached the end yet??
                    if (duration >= aniRunTime) {
                        // Reset the start time, this allows the 
                        // animation to cycle.  Normally you would stop
                        // the timer, see the previous example
                        startTime = -1;
                        // Swap the start and target colors...
                        Color tmp = startColor;
                        startColor = targetColor;
                        targetColor = tmp;
                        color = startColor;
                    } else {
                        // Calculate the progress
                        progress = (float) duration / (float) aniRunTime;
                        // Blend the colors
                        color = blend(startColor, targetColor, 1f - progress);
                    }
                    // update the ui
                    repaint();
                }
            });
            aniTimer.setRepeats(true);
            aniTimer.setCoalesce(true);
            aniTimer.start();
        }

        @Override
        public Dimension getPreferredSize() {
            return new Dimension(200, 200);
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);
            Graphics2D g2d = (Graphics2D) g.create();

            int x = (getWidth() - 20) / 2;
            int y = (getHeight() - 20) / 2;
            g2d.setColor(color);
            Ellipse2D node = new Ellipse2D.Float(x, y, 20, 20);
            g2d.fill(node);
            g2d.setColor(Color.GRAY);
            g2d.draw(node);

            g2d.dispose();
        }
    }

    public static Color blend(Color color1, Color color2, double ratio) {
        float r = (float) ratio;
        float ir = (float) 1.0 - r;

        float rgb1[] = new float[3];
        float rgb2[] = new float[3];

        color1.getColorComponents(rgb1);
        color2.getColorComponents(rgb2);

        float red = rgb1[0] * r + rgb2[0] * ir;
        float green = rgb1[1] * r + rgb2[1] * ir;
        float blue = rgb1[2] * r + rgb2[2] * ir;

        if (red < 0) {
            red = 0;
        } else if (red > 255) {
            red = 255;
        }
        if (green < 0) {
            green = 0;
        } else if (green > 255) {
            green = 255;
        }
        if (blue < 0) {
            blue = 0;
        } else if (blue > 255) {
            blue = 255;
        }

        Color color = null;
        try {

            color = new Color(red, green, blue);

        } catch (IllegalArgumentException exp) {

            NumberFormat nf = NumberFormat.getNumberInstance();
            System.err.println(nf.format(red) + "; " + nf.format(green) + "; " + nf.format(blue));

        }
        return color;
    }
}

这篇关于插入二叉搜索树中节点颜色的动画变化的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆