Java: Modify the program to have two classes of nodes instead one. So, the progr
ID: 660589 • Letter: J
Question
Java: Modify the program to have two classes of nodes instead one. So, the program prompts user to enter two different values which will be stored in their respective nodes. But, they should have a common key. So, whenever user uses the search, traverse or delete option. They could perform those functions by just searhing that common key.
Please kindly provide the solution asap, thanks!
// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
class Node
{
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} // end class Node
////////////////////////////////////////////////////////////////
class Tree
{
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print(" Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print(" Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print(" Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
// -------------------------------------------------------------
} // end class Tree
////////////////////////////////////////////////////////////////
class TreeApp
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();
theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);
while(true)
{
System.out.print("Enter first letter of show, ");
System.out.print("insert, find, delete, or traverse: ");
int choice = getChar();
switch(choice)
{
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value, value + 0.9);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print(" ");
}
else
System.out.print("Could not find ");
System.out.print(value + ' ');
break;
case 'd':
System.out.print("Enter value to delete: ");
value = getInt();
boolean didDelete = theTree.delete(value);
if(didDelete)
System.out.print("Deleted " + value + ' ');
else
System.out.print("Could not delete ");
System.out.print(value + ' ');
break;
case 't':
System.out.print("Enter type 1, 2 or 3: ");
value = getInt();
theTree.traverse(value);
break;
default:
System.out.print("Invalid entry ");
} // end switch
} // end while
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // end class TreeApp
////////////////////////////////////////////////////////////////
Explanation / Answer
001 public class BinaryTree {
002
003 Node root;
004
005 public void addNode(int key, String name) {
006
007 // Create a new Node and initialize it
008
009 Node newNode = new Node(key, name);
010
011 // If there is no root this becomes root
012
013 if (root == null) {
014
015 root = newNode;
016
017 } else {
018
019 // Set root as the Node we will start
020 // with as we traverse the tree
021
022 Node focusNode = root;
023
024 // Future parent for our new Node
025
026 Node parent;
027
028 while (true) {
029
030 // root is the top parent so we start
031 // there
032
033 parent = focusNode;
034
035 // Check if the new node should go on
036 // the left side of the parent node
037
038 if (key < focusNode.key) {
039
040 // Switch focus to the left child
041
042 focusNode = focusNode.leftChild;
043
044 // If the left child has no children
045
046 if (focusNode == null) {
047
048 // then place the new node on the left of it
049
050 parent.leftChild = newNode;
051 return; // All Done
052
053 }
054
055 } else { // If we get here put the node on the right
056
057 focusNode = focusNode.rightChild;
058
059 // If the right child has no children
060
061 if (focusNode == null) {
062
063 // then place the new node on the right of it
064
065 parent.rightChild = newNode;
066 return; // All Done
067
068 }
069
070 }
071
072 }
073 }
074
075 }
076
077 // All nodes are visited in ascending order
078 // Recursion is used to go to one node and
079 // then go to its child nodes and so forth
080
081 public void inOrderTraverseTree(Node focusNode) {
082
083 if (focusNode != null) {
084
085 // Traverse the left node
086
087 inOrderTraverseTree(focusNode.leftChild);
088
089 // Visit the currently focused on node
090
091 System.out.println(focusNode);
092
093 // Traverse the right node
094
095 inOrderTraverseTree(focusNode.rightChild);
096
097 }
098
099 }
100
101 public void preorderTraverseTree(Node focusNode) {
102
103 if (focusNode != null) {
104
105 System.out.println(focusNode);
106
107 preorderTraverseTree(focusNode.leftChild);
108 preorderTraverseTree(focusNode.rightChild);
109
110 }
111
112 }
113
114 public void postOrderTraverseTree(Node focusNode) {
115
116 if (focusNode != null) {
117
118 postOrderTraverseTree(focusNode.leftChild);
119 postOrderTraverseTree(focusNode.rightChild);
120
121 System.out.println(focusNode);
122
123 }
124
125 }
126
127 public Node findNode(int key) {
128
129 // Start at the top of the tree
130
131 Node focusNode = root;
132
133 // While we haven't found the Node
134 // keep looking
135
136 while (focusNode.key != key) {
137
138 // If we should search to the left
139
140 if (key < focusNode.key) {
141
142 // Shift the focus Node to the left child
143
144 focusNode = focusNode.leftChild;
145
146 } else {
147
148 // Shift the focus Node to the right child
149
150 focusNode = focusNode.rightChild;
151
152 }
153
154 // The node wasn't found
155
156 if (focusNode == null)
157 return null;
158
159 }
160
161 return focusNode;
162
163 }
164
165 public static void main(String[] args) {
166
167 BinaryTree theTree = new BinaryTree();
168
169 theTree.addNode(50, "Boss");
170
171 theTree.addNode(25, "Vice President");
172
173 theTree.addNode(15, "Office Manager");
174
175 theTree.addNode(30, "Secretary");
176
177 theTree.addNode(75, "Sales Manager");
178
179 theTree.addNode(85, "Salesman 1");
180
181 // Different ways to traverse binary trees
182
183 // theTree.inOrderTraverseTree(theTree.root);
184
185 // theTree.preorderTraverseTree(theTree.root);
186
187 // theTree.postOrderTraverseTree(theTree.root);
188
189 // Find the node with key 75
190
191 System.out.println(" Node with the key 75");
192
193 System.out.println(theTree.findNode(75));
194
195 }
196 }
197
198 class Node {
199
200 int key;
201 String name;
202
203 Node leftChild;
204 Node rightChild;
205
206 Node(int key, String name) {
207
208 this.key = key;
209 this.name = name;
210
211 }
212
213 public String toString() {
214
215 return name + " has the key " + key;
216
217 /*
218 * return name + " has the key " + key + " Left Child: " + leftChild +
219 * " Right Child: " + rightChild + " ";
220 */
221
222 }
223
224 }
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.