插入二进制搜索树时对节点的颜色进行动画处理
齐思淼
问题内容：
问题答案：
我已经实现了二进制搜索树的显示。这是代码，
它在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++;
}
现在，当我将节点插入树中时，我希望父节点逐渐改变
新节点的颜色，然后最终作为子节点加入。或
要插入的新节点沿着其父节点的路径移动。或类似
的东西这里是一个例子：在此处输入图片说明
我不知道如何使用计时器或类似的方法来完成此任务。
问题答案：
好的，这花了我想要的时间（10个月大的孩子没有
耐心）
在此处输入图片说明
基本概念围绕着一个想法，即您需要
在一段时间内从一种状态更改为另一种状态。
在给定开始时间和当前时间的情况下，我们可以计算
动画运行的时间，并在给定动画总时间的情况下，计算
当前进度。
借助此方法（以及一些巧妙的数学方法），我们可以计算从
开始状态到目标状态的当前状态。
我也做了动作，所以可能会有点过头，但是基本
前提保持不变。
我在动画
属性类中放置了有关需要更改的节点的有状态信息，并使用ajavax.swing.Timer标记了动画（以
合理的稳定速率）。然后，我根据需要更新每个节点的状态
并重新绘制屏幕。
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;
}
}
Update with simple example ;)
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;
}
}
类似资料：
-
我已经实现了二进制搜索树的显示。下面是代码，它在jpanel中绘制二叉树。 我不知道如何实现这一点，用定时器或类似的方法。
-
我对如何在二叉查找树中排列节点的顺序有点困惑。左边的二叉查找树中的子树节点能比根节点大吗？ 例如，以下内容会是二叉搜索树吗？ 上面让我困惑的是1（3）的右子树是否可以大于原始根节点（2）。
-
目前，我在理解如何在没有传递节点时从二进制搜索树中删除节点时遇到了一个问题。我有两个类，BSTSet和BSTNode，每个类都有一个remove方法。。 当我被传递一个节点时，我理解删除方法，但当我在根上调用remove方法并试图从node类中删除节点时，我不知道从何处开始。有人能告诉我吗？谢谢如果您想了解更多信息，请询问。
-
类 节点： 定义初始化（自我，d）： 自我左 = 无 自我数据 = d 自我右= 无 全局 r = 无 定义插入（）： 全局 r d= int（输入（'输入数据：'）） 如果（r 为 None）： r= 节点（d） 否则： t=r 而 （t！=无）： if（d）
-
我需要创建一个递归方法，它将二进制搜索树的根节点作为参数。这个递归方法随后将返回整个二叉搜索树中节点总数的int值。 这是我目前所掌握的： main方法调用节点如下所示： 所以我是按顺序运行搜索的，一旦我到达一个没有子节点的节点，我就会删除当前节点，返回父节点并继续。我对上面的方法进行了调试，当程序最终计数并删除根节点左右两侧的所有节点并尝试返回1时，程序以NullPointerException
-
一个痛苦而愚蠢的问题，我几乎羞于不敢问。在过去的4个小时里，我一直在寻找，测试了不同的算法，在纸上尝试了不少，但仍然无法正常工作。 我将为您提供项目实现的详细信息，但基本问题是：“如何处理在预排序二叉树中插入节点。 通过预排序BST，我的意思是所有节点都应该以这样的方式插入，即使用预排序遍历（例如用于打印）遍历树时，应该按升序打印节点。 我只需要一个简单的算法。我尝试了这里给出的一个简单的插入算法