File : BSTDemo.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package binsearchtree;
import javax.swing.*;
import java.awt.event.*;
import java.awt.Graphics;
import java.awt.BorderLayout;
import javax.swing.border.BevelBorder;
import java.awt.Point;
import java.awt.Color;
import java.awt.Dimension;
public class BSTDemo extends DrawPanel implements ActionListener {
private static JLabel status;
private static BSTDemo myPanel;
private int yStart;
private BinSearchTree<Integer,String> bst;
private JTextField inputBox;
public BSTDemo() {
super();
bst = new BinSearchTree<Integer,String>();
yStart = 50;
JButton addButton = new JButton("Click to Add");
addButton.addActionListener(this);
add(addButton,BorderLayout.NORTH);
inputBox = new JTextField("",10);
add(inputBox,BorderLayout.NORTH);
JButton findButton = new JButton("Find");
findButton.addActionListener(this);
add(findButton,BorderLayout.NORTH);
JButton delButton = new JButton("Delete");
delButton.addActionListener(this);
add(delButton,BorderLayout.NORTH);
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
drawTree(g);
//g.drawString("Hello",10,yStart);
}
public Dimension getPreferredSize() {
return new Dimension(800,400);
}
public void actionPerformed(ActionEvent ae) {
String choice = ae.getActionCommand();
if (choice.equals("Quit")) {
System.exit(0);
}
else if (choice.equals("Click to Add")) {
//yStart += 10;
String[] nodeVals = JOptionPane.showInputDialog(
this,"Enter key and value separated by colon " +
" (key:value) ","key:value").split(":");
int key = Integer.parseInt(nodeVals[0].trim());
String val = nodeVals[1];
bst.add(key,val);
repaint();
status.setText("Added " + key + " : " + val);
}
else if (choice.equals("Find")) {
int key = Integer.parseInt(inputBox.getText());
String val = bst.find(key);
if (val != null) {
JOptionPane.showMessageDialog(this,
"Found " + val + " at " + key);
status.setText("Found " + val);
}
else {
JOptionPane.showMessageDialog(this,
"Key not found");
status.setText("Could not find key");
}
}
else if (choice.equals("Delete")) {
int key = Integer.parseInt(inputBox.getText());
String val = bst.find(key);
if (val != null) {
bst.delete(key);
repaint();
status.setText("Deleted " + key);
}
else {
status.setText("No such key to delete");
JOptionPane.showMessageDialog(this,
"Cannot delete, key doesn't exist");
}
}
}
public void drawTree(Graphics g) {
bst.draw(myPanel,g);
}
public static void main(String[] args) {
SwingUtilities.invokeLater(new Runnable(){
public void run() {
createAndShowGui();
}
});
}
public static void createAndShowGui() {
JFrame myApp = new JFrame("Binary Search Tree");
myPanel = new BSTDemo();
myApp.add(myPanel);
initMenu(myApp);
int width = (int)myPanel.getPreferredSize().getWidth();
initStatus(myApp,600);
myApp.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
myApp.pack();
myApp.setVisible(true);
}
private static void initMenu(JFrame frame) {
JMenuBar menuBar = new JMenuBar();
frame.setJMenuBar(menuBar);
JMenu file = new JMenu("File");
menuBar.add(file);
JMenuItem quit = new JMenuItem("Quit");
quit.addActionListener(myPanel);
file.add(quit);
}
private static void initStatus(JFrame frame, int width) {
status = new JLabel("Program loaded");
JPanel panel = new JPanel();
panel.setBorder(new BevelBorder(BevelBorder.LOWERED));
panel.setPreferredSize(new Dimension(width,25));
panel.setLayout(new BoxLayout(panel,BoxLayout.X_AXIS));
panel.add(status);
status.setHorizontalAlignment(SwingConstants.LEFT);
frame.add(panel,BorderLayout.SOUTH);
}
}
===========================================
DrawPanel.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package binsearchtree;
import javax.swing.*;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.BasicStroke;
import java.awt.BorderLayout;
import javax.swing.border.BevelBorder;
import java.awt.Point;
import java.awt.Dimension;
import java.awt.geom.Line2D;
import java.awt.geom.Rectangle2D;
import java.awt.RenderingHints;
import java.awt.Color;
public class DrawPanel extends JPanel {
protected JLabel status;
public DrawPanel() {
super();
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
}
public void drawLine(Graphics g, Point start,
Point end, float thickness, Color color) {
Graphics2D g2 = (Graphics2D)g;
Color oldColor = g2.getColor();
BasicStroke oldStroke = (BasicStroke)g2.getStroke();
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
g2.setStroke(new BasicStroke(thickness));
g2.setColor(color);
g2.draw(new Line2D.Float(start.x,start.y,end.x,
end.y));
g2.setStroke(oldStroke);
g2.setColor(oldColor);
}
public void drawLine(Graphics g, Point start, Point end) {
drawLine(g,start,end,2,Color.black);
}
public void drawLine(Graphics g, Point start, Point end,
float thickness) {
drawLine(g,start,end,thickness,Color.black);
}
public void drawRectangle(Graphics g, Point start,
float width, float height, float thickness,
Color color) {
Graphics2D g2 = (Graphics2D)g;
Color oldColor = g2.getColor();
BasicStroke oldStroke = (BasicStroke)g2.getStroke();
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
g2.setStroke(new BasicStroke(thickness));
g2.setColor(color);
g2.draw(new Rectangle2D.Float(start.x,start.y,width,
height));
g2.setStroke(oldStroke);
g2.setColor(oldColor);
}
public void drawRectangle(Graphics g, Point start,
float width, float height) {
drawRectangle(g,start,width,height,2,Color.black);
}
public void drawLinkNode(Graphics g, Point head) {
Point p = new Point(head.x,head.y-10);
drawRectangle(g,p,40,20);
drawLine(g,new Point(p.x+30,p.y),
new Point(p.x+30,p.y+20));
}
public void appendLinkNode(Graphics g, Point tail) {
drawLinkNode(g,tail);
}
}
=========================================
BinSearchTree.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package binsearchtree;
import java.awt.Graphics;
import java.awt.Point;
public class BinSearchTree<K extends Comparable<K>, V> {
class TreeNode {
K key;
V value;
TreeNode left;
TreeNode right;
int x;
int y;
int width;
String childType;
public TreeNode(K k, V val) {
key = k;
value = val;
left = null;
right = null;
x = 0;
y = 0;
width = 0;
childType = "";
}
public String toString() {
String temp = key + ":" + value + ":" +
x + ":" + y + ":" + childType;
return temp;
}
}
private TreeNode root;
private String childType;
private int parentX;
private int parentY;
public BinSearchTree() {
root = null;
childType = "";
parentX = 0;
parentY = 0;
}
public void add(K key, V val) {
root = i_add(root, key, val);
}
private TreeNode i_add(TreeNode nd, K key, V val) {
if (nd == null) {
return new TreeNode(key,val);
}
int cmp = key.compareTo(nd.key);
if (cmp == 0) {
nd.value = val; //replace
}
else if (cmp > 0) {
nd.right = i_add(nd.right,key,val);
}
else {
nd.left = i_add(nd.left,key,val);
}
return nd;
}
public void printInOrder() {
i_printInOrder(root);
}
private void i_printInOrder(TreeNode nd) {
if (nd == null) {
return;
}
i_printInOrder(nd.left);
System.out.println(nd);
i_printInOrder(nd.right);
}
public int height() {
return i_height(root);
}
private int i_height(TreeNode nd) {
if (nd == null) {
return 0;
}
int leftHt = i_height(nd.left);
int rightHt = i_height(nd.right);
if (leftHt > rightHt) {
return leftHt + 1;
}
else {
return rightHt + 1;
}
}
public void draw(BSTDemo panel,Graphics g) {
if (root != null) {
calcCoords(new Point(400,50));
printByLevel(panel,g);
}
}
public void calcCoords(Point startPt) {
int height = height();
root.x = startPt.x;
root.y = startPt.y;
for (int depth = 2; depth <= height; depth++) {
int spacing = (int)Math.pow(2,(height-depth))*40;
i_calcCoords(root,depth,spacing);
}
}
public void i_calcCoords(TreeNode nd, int depth, int width) {
if (nd == null) {
return;
}
if (depth == 1) {
if (childType == "left") {
nd.x = parentX - width/2;
nd.childType = "left";
}
else if (childType == "right") {
nd.x = parentX + width/2;
nd.childType = "right";
}
nd.y = parentY + 50;
nd.width = width;
}
else {
parentX = nd.x;
parentY = nd.y;
childType = "left";
i_calcCoords(nd.left, depth-1, width);
childType = "right";
i_calcCoords(nd.right, depth-1, width);
}
}
public void drawNode(BSTDemo panel,Graphics g, TreeNode nd) {
//g.drawRect(nd.x,nd.y,30,30);
panel.drawRectangle(g,new Point(nd.x,nd.y),30,30);
String key = "" + nd.key;
int x = nd.x + (4-key.length())*4;
g.drawString("" + nd.key,x,nd.y+20);
if (nd != root) {
int x2 = 0;
int y2 = 0;
if (nd.childType == "left") {
x2 = nd.x + nd.width/2;
}
else if (nd.childType == "right") {
x2 = nd.x - nd.width/2;
}
y2 = nd.y - 20;
panel.drawLine(g,new Point(nd.x+15,nd.y),new Point(x2+15,y2));
}
}
public void printByLevel(BSTDemo panel,Graphics g) {
int height = height();
for (int depth = 1; depth <= height; depth++) {
i_printByLevel(root,depth,panel,g);
System.out.println("");
}
}
private void i_printByLevel(TreeNode nd, int depth, BSTDemo panel,Graphics g) {
if (nd == null) {
return;
}
if (depth == 1) {
System.out.print(nd + " ");
drawNode(panel,g,nd);
}
else {
i_printByLevel(nd.left,depth-1,panel,g);
i_printByLevel(nd.right,depth-1,panel,g);
}
}
public V find(K key) {
return i_find(root, key);
}
private V i_find(TreeNode nd, K key) {
if (nd == null) {
return null;
}
int cmp = key.compareTo(nd.key);
if (cmp < 0) {
return i_find(nd.left, key);
}
else if (cmp > 0) {
return i_find(nd.right, key);
}
else {
return nd.value;
}
}
public TreeNode deleteMin() {
return i_deleteMin(root);
}
private TreeNode i_deleteMin(TreeNode nd) {
if (nd.left == null) {
return nd.right;
}
nd.left = i_deleteMin(nd.left);
return nd;
}
public TreeNode minimum() {
return i_minimum(root);
}
private TreeNode i_minimum(TreeNode nd) {
if (nd.left == null) {
return nd;
}
return i_minimum(nd.left);
}
public void delete(K key) {
root = i_delete(root,key);
}
private TreeNode i_delete(TreeNode nd, K key) {
if (nd == null) {
return null;
}
int cmp = key.compareTo(nd.key);
if (cmp < 0) {
nd.left = i_delete(nd.left,key);
}
else if (cmp > 0) {
nd.right = i_delete(nd.right,key);
}
else {
if (nd.right == null) {
return nd.left;
}
if (nd.left == null) {
return nd.right;
}
TreeNode old = nd;
nd = i_minimum(old.right);
nd.right = i_deleteMin(old.right);
nd.left = old.left;
}
return nd;
}
}
Tidak ada komentar:
Posting Komentar