hi,,
attached a java code for a simple dictionary based on AVL tree principle,,
the 3 files are:
Node.java: the base class
AVL.java:the function
and Menu:the menu class of the programe
regards
afas87 0 Newbie Poster
package avl;
import javax.swing.*;
public class AVL {
Node root;
int count;
//make the tree empty
public void makeEmpty(){
root=null;
count=0;
}
//Find function that rerun the node of the specified word
public Node find(String element,Node root){
while( root != null )
if( element.compareTo( root.element ) < 0 )
root = root.left;
else if( element.compareTo( root.element ) > 0 )
root = root.right;
else
return root; // Match
return null; // No match
}
//FindMin function taht rerun the Node of the first of the Dictionary.. the most left node
public Node findMin(Node t){
if( t == null )
return t;
while( t.left != null )
t = t.left;
return t;
}
//Height function that return the height of the Node or -1 if the Node equlas null
public int height( Node t )
{
return t == null ? -1 : t.height;
}
//Single Right Rouatate
public Node SRR(Node k1){
Node tempParent = k1.parent;
Node k2 = k1.left; //k2 will be in position of k1
{if(tempParent!=null&&(tempParent.left==k1))
tempParent.left=k2;
else if(tempParent!=null&&(tempParent.right==k1))
tempParent.right=k2;}
k1.left = k2.right;
if(k2.right!=null)
k2.right.parent=k1;
k2.right = k1;
k2.parent=k1.parent;
k1.parent=k2;
//set the height of the rearranged Nodes
k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = Math.max( height( k2.left ), k1.height ) + 1;
if(k1==root)
root=k2; //if k1 was the root, k2 will be the route
return k2;
}
//Single Left Routate
public Node SLR(Node k1){
Node tempParent = k1.parent;
Node k2 = k1.right;
k2.parent=tempParent;
{if(tempParent!=null&&(tempParent.left==k1))
tempParent.left=k2;
else if(tempParent!=null&&(tempParent.right==k1))
tempParent.right=k2;}
k1.right=k2.left;
if(k2.left!=null)
k2.left.parent=k1;
k2.left=k1;
k1.parent=k2;
k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = Math.max( height( k2.left ), k1.height ) + 1;
if(k1==root) //if k1 was the root, k2 will be the route
root=k2;
return k2;
}
//Double Right Routate
public Node DRR(Node k1){
//DRR consists of two Single Routates, first Rouate left then rouatte right
k1.left=SLR(k1.left);
return SRR(k1);
}
public Node DLR(Node k1){
//DLF consists of two Single Routates, first Rouate right then rouatte left
k1.right=SRR(k1.right);
return SLR(k1);
}
//insert function that insert anode in the tree and check the balance
//after insertion
public Node insert(String word,String mean,Node t,Node p){
if( t == null ){
//this procedure do the insertion
{t = new Node(word,mean);
t.parent=p;
}
if(count==0)
root=t;
count++;
}
else if( word.compareTo( t.element ) < 0 )
{
t.left = insert( word,mean,t.left ,t);
//check the balance of the tree
if( height( t.left ) - height( t.right ) == 2 )
{
if( word.compareTo( t.left.element ) < 0 )
t = SRR( t );
else
t = DRR( t );}
}
else if( word.compareTo( t.element ) > 0 )
{
t.right = insert( word,mean,t.right,t );
if( height( t.right ) - height( t.left ) == 2 ){
if( word.compareTo( t.right.element ) > 0 )
t = SLR( t );
else
t = DLR( t );}
}
else
;
//set the height of the new node
t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
return t;
}
//Delete function that delete aNode from the tree
//retun true if the node deleted and false if the tree empty
public boolean delete(Node t,Node root){
if((root==null)) //if the treee empty retrun false
return false;
else if((t.left==null)&&(t.right==null))
delWithNoChild(t);
else if((t.left==null)||(t.right==null))
delWithOneChild(t);
else delWithChilds(t);
return true;
}
//delete the node with no childs
private boolean delWithNoChild(Node t){
if(t==root)
{
count=0;
t=null;
}
else
{
Node tempParent = t.parent;
if(tempParent.left==t)
t.parent.left=null;
else
tempParent.right=null;
tempParent.height=Math.max(height(tempParent.left),height(tempParent.right))+1;
if((height(tempParent.right)-height(tempParent.left))==2)
SLR(tempParent);
else if((height(tempParent.left)-height(tempParent.right))==2)
SLR(tempParent);
}
return true;
}
//delete the node with only one child
private boolean delWithOneChild(Node t){
if(t==root)//in case of the deleted node is the root
{
if(t.right==null)
{
root=t.left;
t.left.parent=null;
}
else
{
root=t.right;
t.right.parent=null;
}
}
else
{
Node temp =t;
{if(t.right==null)
temp=t.left;
else
temp=t.right;}
Node tempParent=t.parent;
if(tempParent.right==t)
tempParent.right=temp;
else
tempParent.left=temp;
temp.parent=tempParent;
tempParent.height=Math.max(tempParent.right.height,tempParent.left.height);
if((tempParent.right.height-tempParent.left.height)==2)
SRR(tempParent.left);
else if((tempParent.left.height-tempParent.right.height)==2)
SLR(tempParent.right);
}
return true;
}
//delete the node with two childs
private boolean delWithChilds(Node t){
Node temp=findMin(t.right);
t.element=(temp.element);
t.meaning=(temp.meaning);
delWithNoChild(temp);
return true;
}
//print tree in order form
public void printTree(JTextArea txt){
if(root==null)
txt.setText("Tree is Empty!!");
else {
txt.setText(" ");
printTree(root,txt);
}
}
//print the tree in postorder form
public void printPostOrderTree(JTextArea txt){
if(root==null)
txt.setText("Tree is Empty!!");
else {
txt.setText(" ");
printPostOrderTree(root,txt);
}
}
//print the tree in post order form
public void printPreOrderTree(JTextArea txt){
if(root==null)
txt.setText("Tree is Empty!!");
else {
txt.setText(" ");
printPreOrderTree(root,txt);
}
}
public void printTree(Node root,JTextArea txt){
if(root!=null)
{
printTree( root.left,txt );
txt.append(root.element+"\n ");
printTree( root.right,txt );
}
}
public void printPreOrderTree(Node root,JTextArea txt){
if(root!=null)
{
txt.append(root.element+"\n ");
printTree( root.left,txt );
printTree( root.right,txt );
}
}
public void printPostOrderTree(Node root,JTextArea txt){
if(root!=null)
{
printTree( root.left,txt );
printTree( root.right,txt );
txt.append(root.element+"\n ");
}
}
//print words with common first char
public void printWords(String sub,Node root,JTextArea txt){
if(root!=null)
{
printWords( sub,root.left,txt );
if(root.element.substring(0,1).equals(sub))
txt.append(" "+root.element+"\n");
printWords( sub,root.right,txt );
}
}
//modify word only
public void modifyWord(String word,String newWord,Node root){
Node mod = find(word,root);
if(mod==null)
System.out.println("No match");
else{
String mean=mod.meaning;
delete(mod,root);
insert(newWord,mean,root,null);
System.out.println("Modification done");
}
}
//modify word with meaning
public void modifyMean(String word,String newMeaning,Node root){
Node mod = find(word,root);
if(mod==null)
System.out.println("No match");
else{
mod.meaning=newMeaning;
System.out.println("Modification done");
}
}
}The attachment preview is chopped off after the first 10 KB. Please download the entire file.
package avl;
import java.awt.color.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.*;
import java.util.Scanner;
import javax.swing.*;
//the menu class which deal with interface of the programe//
//it generate the file edit,help menues//
public class Menu extends JFrame implements ActionListener {
static AVL tree = new AVL();
String fileName=new String();
final static JTextArea txt= new JTextArea(5,4);
public Menu() {
setTitle("AVL Tree Based Dictionary");
setSize(400, 400);
// Creates a menubar for a JFrame
JMenuBar menuBar = new JMenuBar();
JPanel textFrame = new JPanel(new BorderLayout());
txt.setBackground(Color.BLACK);
txt.setForeground(Color.WHITE);
txt.setEditable(false);
textFrame.add(txt);
add(textFrame,BorderLayout.CENTER);
// Add the menubar to the frame
setJMenuBar(menuBar);
// Define and add drop down menus to the menubar
JMenu fileMenu = new JMenu("File");
JMenu editMenu = new JMenu("Edit");
JMenu helpMenu = new JMenu("Help");
JMenu printMenu = new JMenu("Print");
JMenu searchMenu = new JMenu("Search");
menuBar.add(fileMenu);
menuBar.add(editMenu);
menuBar.add(printMenu);
menuBar.add(searchMenu);
menuBar.add(helpMenu);
// Create and add menu items to sthe drop down menu
JMenuItem newAction = new JMenuItem("New");
JMenuItem openAction = new JMenuItem("Open File");
JMenuItem updateFileAction = new JMenuItem("update file");
JMenuItem insertAction = new JMenuItem("Insert");
JMenuItem deleteAction = new JMenuItem("Delete");
JMenuItem modifyAction = new JMenuItem("Modify aWord");
JMenuItem printInOrderAction = new JMenuItem("Print InOrder");
JMenuItem printPreOrderAction = new JMenuItem("Print PreOrder");
JMenuItem printPostOrderAction = new JMenuItem("Print PostOrder");
JMenuItem searchAction = new JMenuItem("Search");
JMenuItem aboutAction = new JMenuItem("About");
fileMenu.add(newAction);
fileMenu.add(openAction);
fileMenu.addSeparator();
fileMenu.add(updateFileAction);
editMenu.add(insertAction);
editMenu.add(deleteAction);
editMenu.addSeparator();
editMenu.add(modifyAction);
printMenu.add(printInOrderAction);
printMenu.add(printPreOrderAction);
printMenu.add(printPostOrderAction);
searchMenu.add(searchAction);
helpMenu.add(aboutAction);
//creat the action performed when choose one of the menues
newAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
tree.makeEmpty();
JOptionPane.showMessageDialog(null, "the AVL Tree is now Blank!!","Blank TREE",2);
}}
);
openAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
fileName=JOptionPane.showInputDialog(null,"Type the file name with full directory","Open",1);
try {
readFromFile(fileName);}
catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();}
}}
);
updateFileAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
if(fileName.length()==0)
JOptionPane.showMessageDialog(null,"No Opened File!!","Error",JOptionPane.ERROR_MESSAGE);
else{
try {
writeToFile(fileName);}
catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
JOptionPane.showMessageDialog(null, "Done");
}
}}
);
searchAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
searchMenu();
}}
);
insertAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
insertMenu();
}}
);
deleteAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
deleteMenu();
}}
);
modifyAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
modifyMenu();
}}
);
printInOrderAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
tree.printTree(txt);
}}
);
printPreOrderAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
tree.printPreOrderTree(txt);
}}
);
printPostOrderAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
tree.printPostOrderTree(txt);
}}
);
aboutAction.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
JOptionPane.showMessageDialog(null,"BY: Abdulfattah Safa,1050187");
}}
);
}
public void readFromFile(String fileName) throws FileNotFoundException{
File file=new File(fileName);
if(!file.canRead()||!file.exists()) //if the file has erorrs
{
JOptionPane.showMessageDialog(null,"File name you have typed either does not exist or cant be read","Error",2);
fileName=null;
}
else{
String x=new String ();
String y=new String();
Scanner scanner = new Scanner(file);
while(scanner.hasNext())
{
x=scanner.next();
y=scanner.next();
tree.insert(x,y, tree.root,null);
}
JOptionPane.showMessageDialog(null,"Done");
}
file.exists();
}
public void writeToFile(String fileName) throws FileNotFoundException{
File file=new File(fileName);
PrintWriter print = new PrintWriter(file);
writeToFile(tree.root,print);
print.close();
}
public void writeToFile(Node root,PrintWriter print){
if(root!=null)
{
writeToFile(root.left,print );
print.println(root.element+" "+root.meaning);
writeToFile(root.right,print );
}
}
//construct the Edit menu item subMenus
public void insertMenu(){
final JFrame insertFrame = new JFrame();
JPanel p1 = new JPanel(new FlowLayout());
JPanel p2 = new JPanel(new FlowLayout());
JPanel p3 = new JPanel(new FlowLayout());
JButton wordPane = new JButton("New Word");
final JTextArea wordArea = new JTextArea(2,10);
wordArea.setBackground(Color.BLACK);
wordArea.setForeground(Color.white);
JButton meanPane = new JButton("Meanining");
final JTextArea meanArea = new JTextArea(2,10);
meanArea.setBackground(Color.BLACK);
meanArea.setForeground(Color.white);
JButton insertButton=new JButton("Insert");
JButton cancelButton = new JButton("Cancel");
p1.add(wordPane);
p1.add(wordArea);
p2.add(meanPane);
p2.add(meanArea);
p3.add(insertButton);
p3.add(cancelButton);
insertFrame.add(p1,BorderLayout.NORTH);
insertFrame.add(p2,BorderLayout.CENTER);
insertFrame.add(p3,BorderLayout.SOUTH);
insertFrame.setTitle("Insert New Word");
insertFrame.setSize(300,200);
insertFrame.setLocationRelativeTo(null);
insertFrame.setVisible(true);
insertButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
if(wordArea.getText().length()!=0){
tree.insert(wordArea.getText(),meanArea.getText(),tree.root,null);
JOptionPane.showMessageDialog(null,"Done");
}
}}
);
cancelButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
insertFrame.setVisible(false);
}}
);
}
public static void deleteMenu(){
String word=JOptionPane.showInputDialog(null,"Type the word tou want tod delete:","Delete",1);
if(tree.find(word,tree.root)==null)
JOptionPane.showMessageDialog(null,"The word you have typed doesnt match any word in the tree","eror",2);
else
{tree.delete(tree.find(word,tree.root),tree.root);
JOptionPane.showMessageDialog(null,"Done");}
}
public static void modifyMenu(){
final JFrame modifyFrame = new JFrame();
JPanel pa = new JPanel(new FlowLayout());
JPanel pb = new JPanel(new FlowLayout());
JPanel pc = new JPanel(new FlowLayout());
JPanel p1 = new JPanel(new FlowLayout());
JPanel p2 = new JPanel(new FlowLayout());
JPanel p3 = new JPanel(new FlowLayout());
JPanel p4 = new JPanel(new FlowLayout());
JPanel p5 = new JPanel(new FlowLayout());
JButton wordPane = new JButton("OldWord");
final JTextArea wordArea = new JTextArea(2,10);
wordArea.setBackground(Color.BLACK);
wordArea.setForeground(Color.white);
JButton meanPane = new JButton("Meaning");
final JTextArea meanArea = new JTextArea("dont fill",2,10);
meanArea.setBackground(Color.BLACK);
meanArea.setForeground(Color.white);
meanArea.setEditable(false);
JButton newWordPane = new JButton("NewWord");
final JTextArea newWordArea = new JTextArea(2,10);
newWordArea.setBackground(Color.BLACK);
newWordArea.setForeground(Color.WHITE);
JButton newMeanPane = new JButton("Meaning");
final JTextArea newMeanArea = new JTextArea(2,10);
newMeanArea.setBackground(Color.BLACK);
newMeanArea.setForeground(Color.white);
JButton modifyButton=new JButton("Modify");
JButton cancelButton = new JButton("Cancel");
p1.add(wordPane);
p1.add(wordArea);
p2.add(meanPane);
p2.add(meanArea);
p3.add(newWordPane);
p3.add(newWordArea);
p4.add(newMeanPane);
p4.add(newMeanArea);
p5.add(modifyButton);
p5.add(cancelButton);
pa.add(p1,BorderLayout.NORTH);
pa.add(p2,BorderLayout.SOUTH);
pb.add(p3,BorderLayout.NORTH);
pb.add(p4,BorderLayout.SOUTH);
pc.add(p5,BorderLayout.CENTER);
modifyFrame.add(pa,BorderLayout.NORTH);
modifyFrame.add(pb,BorderLayout.CENTER);
modifyFrame.add(pc,BorderLayout.SOUTH);
modifyFrame.setTitle("Modify Word");
modifyFrame.setSize(500,200);
modifyFrame.setLpackage avl;
public class Node {
protected String element;
protected String meaning;
protected Node left;
protected Node right;
protected Node parent;
protected int height;
public Node(String word,String mean){
element =word ;
meaning=mean;
parent=left=right=null;
height=0;
}
}- 1 Contributor
- 0 Replies
- 85 Views
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.