BinaryTree.java
package com.binarytree.test;
import java.util.*;
public class BinaryTree<E extends Comparable<E>>{
private TreeNode<E> root;
private int size=0;
public BinaryTree() {
}
public BinaryTree(E[] objects) {
for (int i = 0; i < objects.length; i++) {
insert(objects[i]);
}
｝
public boolean search(E e) {
// TODO Auto-generated method stub
TreeNode<E> current=root;
while (current!=null) {
if (e.compareTo(current.element)<0) {
current=current.left;
}else if (e.compareTo(current.element)>0) {
current=current.right;
}else
return true;
}
return false;
}
public boolean insert(E e) {
// TODO Auto-generated method stub
if (root==null) {
root=creatTreeNode(e);
}else {
TreeNode<E> parent=null;
TreeNode<E> current = root;
while (current!=null) {
if (e.compareTo(current.element)<0) {
parent=current;
current=current.left;
} else if(e.compareTo(current.element)>0){
parent=current;
current=current.right;
}else
return false;
}
if (e.compareTo(parent.element)<0) {
parent.left=creatTreeNode(e);
}
if (e.compareTo(parent.element)>0) {
parent.right=creatTreeNode(e);
}
}
size++;
return true;
}
public TreeNode<E> creatTreeNode(E e) {
return new TreeNode<E>(e);
}
public void inorder() {
inorder(root);
}
public void inorder(TreeNode<E> root) {
if (root==null) return;
inorder(root.left);
System.out.print(root.element+" ");
inorder(root.right);
}
public void postorder() {
postorder(root);
}
public void postorder(TreeNode<E> root) {
if(root==null)return ;
postorder(root.left);
postorder(root.right);
System.out.print(root.element+" ");
}
public void preorder() {
preorder(root);
}
public void preorder(TreeNode<E> root) {
if(root==null)return ;
System.out.print(root.element+" ");
preorder(root.left);
preorder(root.right);
}
public int getSize() {
return size;
}
public TreeNode getRoot() {
return root;
}
public List<TreeNode<E>> path(E e) {
List<TreeNode<E>> list=new ArrayList<TreeNode<E>>();
TreeNode<E> current=root;
while (current!=null) {
list.add(current);
if (e.compareTo(current.element)<0) {
current=current.left;
}else if (e.compareTo(current.element)>0) {
current=current.right;
}else break;
}
return list ;
}
@Override
public boolean delete(E e) {
// TODO Auto-generated method stub
TreeNode<E> parent=null;
TreeNode<E> current = root;
while (current!=null) {
if (e.compareTo(current.element)<0) {
parent=current;
current=current.left;
} else if (e.compareTo(current.element)>0) {
parent=current;
current=current.right;
} else
break;
}
if (current==null) {
return false;
}
if (current.left==null) {
if(parent==null){
root=current.right;
}else {
if (e.compareTo(parent.element)<0) {
parent.left=current.right;
}else
parent.right=current.right;
}
}//current node has left child
else {
TreeNode<E> parentOfRightMost=current;
TreeNode<E> rightMost = current.left;
while (rightMost.right!=null) {
parentOfRightMost=rightMost;
rightMost=rightMost.right;
}
current.element=rightMost.element;
if (parentOfRightMost.right==rightMost) {
parentOfRightMost.right=rightMost.left;
}else {
parentOfRightMost.left=rightMost.left;
}
}
size--;
return true;
}
public Iterator iterator() {
return inorderIterator();
}
private Iterator inorderIterator() {
// TODO Auto-generated method stub
return new InorderIterator();
}
class InorderIterator implements Iterator {
private List<E>list=new ArrayList<E>();
private int current=0;
public InorderIterator() {
inorder();
}
public void inorder(){
inorder(root);
}
private void inorder(TreeNode<E> root) {
// TODO Auto-generated method stub
if (root==null) {
return ;
}
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
public boolean hasNext() {
// TODO Auto-generated method stub
if (current<list.size()) {
return true;
}
return false;
}
@Override
public Object next() {
// TODO Auto-generated method stub
return list.get(current++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
delete(list.get(current));
list.clear();
inorder();
}
}
public void clear() {
root=null;
size=0;
}
}
Test.java
package com.binarytree.test;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
public class Test extends JPanel{
BinaryTree<Integer> root=new BinaryTree<Integer>();
TreeView treeView=new TreeView();
private JTextField jtField=new JTextField(5);
private JButton jbtInsert=new JButton("Insert");
private JButton jbtDelete=new JButton("Delete");
public Test(BinaryTree<Integer> root) {
this.root=root;
setUI();
}
private void setUI() {
// TODO Auto-generated method stub
this.setLayout(new BorderLayout()) ;
add(treeView, BorderLayout.CENTER);
JPanel panel=new JPanel();
//this.setVisible(true);
panel.add(new JLabel("Enter a key :"));
panel.add(jtField);
panel.add(jbtInsert);
panel.add(jbtDelete);
add(panel, BorderLayout.SOUTH);
jbtInsert.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent arg0) {
// TODO Auto-generated method stub
int key=Integer.parseInt(jtField.getText());
if (root.search(key)) {
JOptionPane.showMessageDialog(null, key+"is already in the tree");
}else {
root.insert(key);
treeView.repaint();
}
}
});
jbtDelete.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent arg0) {
// TODO Auto-generated method stub
int key=Integer.parseInt(jtField.getText());
if (root.search(key)) {
root.delete(key);
treeView.repaint();
} else {
JOptionPane.showMessageDialog(null, key+"is not in the tree");
}
}
});
}
class TreeView extends JPanel{
private int radius=20;
private int vGap=50;
public void paintComponent(Graphics g){
super.paintComponent(g);
if (root.getRoot()!=null) {
diaplay(g,root.getRoot(),getWidth()/2,30,getWidth()/4);
}
}
private void diaplay(Graphics g, TreeNode root, int x, int y, int hGap) {
// TODO Auto-generated method stub
g.drawOval(x-radius, y-radius, 2*radius, 2*radius);
g.drawString(root.element+"", x-6, y+4);
if(root.left!=null){
connectLeftChild(g,x-hGap,y+vGap,x,y);
diaplay(g, root.left, x-hGap, y+vGap, hGap/2);
}
if (root.right!=null) {
connectRightChild(g,x+hGap,y+vGap,x,y);
diaplay(g, root.right, x+hGap, y+vGap, hGap/2);
}
}
private void connectRightChild(Graphics g, int x1, int y1, int x2, int y2) {
// TODO Auto-generated method stub
double d=Math.sqrt(vGap*vGap+(x2-x1)*(x2-x1));
int x11=(int)(x1-radius*(x1-x2)/d);
int y11=(int)(y1-radius*vGap/d);
int x21=(int)(x2+radius*(x1-x2)/d);
int y21=(int)(y2+radius*vGap/d);
g.drawLine(x11, y11, x21, y21);
}
private void connectLeftChild(Graphics g, int x1, int y1, int x2, int y2) {
// TODO Auto-generated method stub
double d=Math.sqrt(vGap*vGap+(x2-x1)*(x2-x1));
int x11=(int)(x1+radius*(x2-x1)/d);
int y11=(int)(y1-radius*vGap/d);
int x21=(int)(x2-radius*(x2-x1)/d);
int y21=(int)(y2+radius*vGap/d);
g.drawLine(x11, y11, x21, y21);
}
}
}
TreeNode.java
package com.binarytree.test;
public class TreeNode<E extends Comparable<E>> {
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e) {
element=e;
}
}
DisplayBinary.java
import javax.swing.JApplet;
import javax.swing.JFrame;
public class DisplayBinary extends JApplet{
public DisplayBinary() {
// TODO Auto-generated constructor stub
add(new Test(new BinaryTree<Integer>()));
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
JFrame jFrame=new JFrame("Tree GUI");
jFrame.add(new DisplayBinary());
jFrame.setSize(400,400);
jFrame.setDefaultCloseOperation(jFrame.EXIT_ON_CLOSE);
jFrame.setLocationRelativeTo(null);
jFrame.setVisible(true);
}
}