Add a remove method to the AVL tree class. Use a graphical user interface that a
ID: 660979 • Letter: A
Question
Add a remove method to the AVL tree class. Use a graphical user interface that allows
a user to work interactively with the AVL tree, adding and removing items as desired.
Extend the AVL tree class presented by adding a method that takes a value, locates it in
the AVL tree, and displays its level. Do this by extending the list of commands supported by the
program to include commands of the form level value. For example, if the user types in
level 12
the program displays the level of a node containing 12. The program should display -1 if the user
types a value not in the tree. If there is more than one instance of the value in the tree, the program
displays the level of any one of them.
IT HAS TO HAVE A GUI
Explanation / Answer
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;
public class AVLTree extends JFrame implements ActionListener {
protected AVLNode root,parent,node;
File file;
private AVLTree tree;
String [] word,meaning;
JTextField fs=new JTextField("enter word you want to search for");
JTextField fd=new JTextField ("enter word you want to delete");
JButton btree= new JButton("construct the tree");
JButton bprint= new JButton("print");
JButton bresult= new JButton("print result");
JButton bsearch= new JButton("do search");
JButton bs= new JButton ("DO SEARCH");
JButton bdel= new JButton("delete");
JButton bd= new JButton ("DELETE");
JButton bdraw= new JButton("draw the tree");
JButton bin= new JButton("print inorder");
JButton bpre= new JButton("print preorder");
JButton bpost= new JButton("print postorder");
/*
* default constructor
*/
public AVLTree(){
root=null;
JPanel p= new JPanel ();
p.setLayout(new GridLayout(6,1,10,20));
p.add(btree);
p.add(bprint);
p.add(bresult);
p.add(bsearch);
p.add(bdel);
p.add(bdraw);
add(p);
btree.addActionListener(this);
bprint.addActionListener(this);
bresult.addActionListener(this);
bsearch.addActionListener(this);
bdel.addActionListener(this);
bdraw.addActionListener(this);
bin.addActionListener(this);
bpre.addActionListener(this);
bpost.addActionListener(this);
}
public AVLNode getRoot(){
return root;
}
// Insert value into the AVL tree
public AVLNode insert(String value,AVLNode t) {
if( t == null ){
//if the Root is Null Create New Node
t = new AVLNode(value);
t.left=null;
t.right=null;
}
else if (value.compareTo(t.key)<0){
t.left=insert(value,t.left);
if( t.left.height - t.right.height == 2 ) {
if( value.compareTo( t.left.key ) < 0 )
t = singleRotation(t, 1);
else
t = doubleRotation(t, 1);
}
}
else if (value.compareTo(t.key)>0){
t.right=insert(value,t.right);
if( t.right.height - t.left.height == 2 ) {
if( value.compareTo( t.right.key ) > 0 )
t = singleRotation(t, 1);
else
t = doubleRotation(t, 1);
}
}
else
t.height=Math.max(t.left.height,t.right.height)+1;
return t;
}
/** In order traversal from a subtree */
private void inorder(AVLNode root) {
if (root != null){
inorder(root.left);
System.out.println(root.key + " ");
inorder(root.right);
}
}
/** Pre order traversal from a subtree */
private void preorder(AVLNode root) {
if (root != null){
System.out.println(root.key + " ");
preorder(root.left);
preorder(root.right);
}
}
/** Post order traversal from a subtree */
private void postorder(AVLNode root) {
if (root == null) {
postorder(root.left);
postorder(root.right);
System.out.println(root.key + " ");
}
}
public AVLNode search(String s){
AVLNode current = root; // start at root
while (s!=current.key){
if(s.compareTo(current.key) <0) // go left
current = current.left;
else // or go right
current = current.right;
if(current == null){ // if no child
System.out.println("Not found");
return null; // didn't find it
}
}
return current; // found
}
public void delete(String s){
AVLNode current=root;
parent=root;
boolean isLeft=false;
while(s!=current.key){ // search for node
parent = current;
if(s.compareTo(current.key) <0) // go left?
current = current.left;
else // or go right?
current = current.right;
if(current == null) // end of the line,
System.out.println("NOT found"); // didn't find it
} // end while
// if no children, simply delete it
if(current.left==null &¤t.right==null){
if(current == root) // if root,
root = null; // tree is empty
else if(isLeft){
parent.left = null;
if( current.left.height - current.right.height == 2 ) {
if( s.compareTo( current.left.key ) < 0 )
current = singleRotation(current, 1);
else
current = doubleRotation(current, 1);
}
}
else{
parent.right = null;
if( current.right.height - current.left.height == 2 ) {
if( s.compareTo( current.right.key ) > 0 )
current = singleRotation(current, 1);
else
current = doubleRotation(current, 1);
}
}
}
}
public int getHeight1(){
return getHeight1(getRoot(), 0);
}
public int getHeight1(AVLNode p, int currentHeight){
if(p == null)
return currentHeight;
else
return max(getHeight1(p.getLeft(), currentHeight ), getHeight1(p.getRight(), currentHeight));
}
public int max(int aValue, int bValue){
return aValue > bValue ? aValue : bValue;
}
public boolean isEmpty(){
return root == null;
}
private AVLNode singleRotation (AVLNode node, int side){
AVLNode temp = node; // Just to declare
if (side == 0){ // Left Rotation
temp = node.left;
node.left = temp.right;
temp.right = node;
node.height = Math.max( node.left.height, node.right.height ) + 1;
temp.height = Math.max( temp.left.height, node.height ) + 1;
}
else if (side == 1){ // Right Rotation
temp = node.right;
node.right = temp.left;
temp.left = node;
node.height = Math.max( node.left.height, node.right.height ) + 1;
temp.height = Math.max( temp.right.height, node.height ) + 1;
}
return temp;
}
private AVLNode doubleRotation(AVLNode node, int side) {
if (side == 0){ //Double Left Rotation
node.left = singleRotation( node.left, 1 );
return singleRotation( node, 0 );
}
else if (side == 1){ //Double Right Rotation
node.right = singleRotation( node.right, 0 );
return singleRotation( node, 1 );
}
return node;
}
// count method to compute the number of lines in a file
public int count(File filename) throws IOException {
InputStream is = new BufferedInputStream(new FileInputStream(filename));
byte[] c = new byte[1024];
int count = 0;
int readChars = 0;
while ((readChars = is.read(c)) != -1) {
for (int i = 0; i < readChars; i++) {
if (c[i] == ' ')
++count;
}
}
return count;
}
/** Main method */
public static void main(String[] args) {
JFrame frame = new AVLTree();
frame.setTitle("What to do");
frame.setLocationRelativeTo(null); // Center the frame
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(300, 300);
frame.setResizable(false);
frame.setVisible(true);
}
public void actionPerformed(ActionEvent e) {
if(e.getSource()==btree){
//read nodes from file
JFileChooser fb = new JFileChooser();
fb.showOpenDialog(null);
file = fb.getSelectedFile();
FileInputStream fis = null;
BufferedInputStream bis = null;
DataInputStream dis = null;
try {
fis = new FileInputStream(file);
bis = new BufferedInputStream(fis);
dis = new DataInputStream(bis);
int no_nodes = count (file);
String [] words= new String[no_nodes];
while (dis.available() != 0) {
for (int i = 0; i < words.length; i++){
tree=new AVLTree();
words[i]= dis.readLine();
System.out.println(" "+words[i]);
while (words[i]!=":"){
word[i]=words[i];
meaning[i]=words[i];
}
node=insert(word[i],node);
}
}
fis.close();
bis.close();
dis.close();
} catch (FileNotFoundException e1) {
e1.printStackTrace();
} catch (IOException e1) {
e1.printStackTrace();
}
}
if(e.getSource()==bprint){
JFrame f = new JFrame();
f.setTitle("How to print the tree");
f.setLocationRelativeTo(null);
f.setSize(300,200);
f.setVisible(true);
JPanel p1= new JPanel ();
p1.setLayout(new GridLayout(3,1,10,10));
p1.add(bin);
p1.add(bpre);
p1.add(bpost);
f.add(p1);
}
if(e.getSource()==bresult){
char a ='A';
try {
int no_nodes = count (file);
for (int i=0; i<no_nodes; i++){
}
a++;
}catch (FileNotFoundException e1) {
e1.printStackTrace();
} catch (IOException e1) {
e1.printStackTrace();
}
}
if(e.getSource()==bsearch){
JFrame f1 = new JFrame ();
f1.setTitle("SEARCH");
f1.setLocationRelativeTo(null);
f1.setSize(300,200);
f1.setVisible(true);
JPanel p= new JPanel();
p.setLayout(new GridLayout(2,1,10,10));
p.add(fs);
p.add(bs);
f1.add(p);
}
if (e.getSource()==bs){
String a= fs.getText();
node= search(a);
JOptionPane.showMessageDialog(null,"The wanted word is:"+node+" "+"and the meaning is"+meaning);
}
if(e.getSource()==bdel){
JFrame f1 = new JFrame ();
f1.setTitle("DELETE");
f1.setLocationRelativeTo(null);
f1.setSize(300,200);
f1.setVisible(true);
JPanel p= new JPanel();
p.setLayout(new GridLayout(2,1,10,10));
p.add(fd);
p.add(bd);
f1.add(p);
}
if (e.getSource()==bd){
String a= fd.getText();
delete(a);
}
if(e.getSource()==bdraw){
}
if(e.getSource()==bin){
System.out.println("The inorder form of the tree (sorted alphabetically) is"+" ");
tree.inorder(node);
}
if(e.getSource()==bpre){
System.out.println("The preorder form of the tree is"+" ");
tree.preorder(node);
}
if(e.getSource()==bpost){
System.out.println("The postorder form of the tree is"+" ");
tree.postorder(node);
}
}
/*
* AVLNode class
*/
class AVLNode {
protected String key;
protected int height;
protected AVLNode left, right,parent;
public AVLNode(String aKey){
key = aKey;
left = right = null;
}
public AVLNode(){
key = "";
height = 0;
right = left = parent = null;
}
public AVLNode(String element, AVLNode left, AVLNode right){
key = element;
this.left = left;
this.right = right;
}
public void setKey(String aKey){
key = aKey;
}
public String getKey(){
return key;
}
public void setLeft(AVLNode leftNode){
left = leftNode;
}
public AVLNode getLeft(){
return left;
}
public void setRight(AVLNode rightNode){
right = rightNode;
}
public AVLNode getRight(){
return right;
}
public void setParent(AVLNode parentNode){
parent = parentNode;
}
public AVLNode getParent(){
return parent;
}
public void setHeight(int aHeight){
height= aHeight;
}
public int getHeight(){
return height;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.