Binary Trees Write a Java application that implements a \"treeMerge\" method for
ID: 3706673 • Letter: B
Question
Binary Trees Write a Java application that implements a "treeMerge" method for binary trees. You may use your own version of a BinaryTree class or you may use the Java Collections BinaryTree version. The new treeMerge method should be added to your BinaryTree class and take one binary tree as a parameter. The contents of the parameter tree must be merged into the tree containing the called method. All of the data in both trees is integer type and must be maintained in ascending order (add lower or equal values on left side and greater values on the right side). The treeMerge method must perform a pre-order search to retrieve each node value from the parameter tree (e.g., tree t2). MyBinaryTree t1 = new MyBinaryTree(); MyBinaryTree t2 = new MyBinaryTree(); // Add data to both trees here.Keep data in ascending order Example of how data should be added to each tree. Input stream for tree 1 --> 4, 7, 2, 1, 10, 5 4 4 4 4 4 4 / / / / 7 2 7 2 7 2 7 2 7 / / / / 1 1 10 1 5 10 // Perform tree merge // Use pre-order search to access t2 node values t3 = t1.treeMerge( t2 ); // This is the call from your test program Example of treeMerge 4 9 4 / / / 2 7 7 12 2 7 / / / / 1 5 8 1 7 9 / / 5 8 12
Explanation / Answer
Program Code-BinaryTree.java
import java.io.*;
import java.util.*;
//The node of the binary tree
class Nodevalue {
int data;
Nodevalue left, right;
Nodevalue(int z) {
data = z;
left = right = null;
}
}
class BinaryTree
{
Nodevalue root;
BinaryTree() {
root = null;
}
void order()
{
ordered(this.root);
}
// Utility function for inorder traversal of the tree
void ordered(Nodevalue node)
{
if(node==null)
return;
ordered(node.left);
System.out.print(node.data + " ");
ordered(node.right);
}
public ArrayList<Integer> storeordered(Nodevalue node, ArrayList<Integer> al)
{
if(node == null)
return al;
storeordered(node.left, al);
al.add(node.data);
storeordered(node.right, al);
return al;
}
ArrayList<Integer> storeorder(Nodevalue node)
{
ArrayList<Integer> al1 = new ArrayList<>();
ArrayList<Integer> al2 = storeordered(node,al1);
return al2;
}
// The method two perform the tree merge operation
ArrayList<Integer> merge(ArrayList<Integer>al1, ArrayList<Integer>al2, int k, int l)
{
ArrayList<Integer> al3 = new ArrayList<>();
int i=0;
int j=0;
while( i<k && j<l)
{
if(al1.get(i)<al2.get(j))
{
al3.add(al1.get(i));
i++;
}
else
{
al3.add(al2.get(j));
j++;
}
}
while(i<k)
{
al3.add(al1.get(i));
i++;
}
while(j<l)
{
al3.add(al2.get(j));
j++;
}
return al3;
}
//convert the arraylist to binary tree
Nodevalue Conversion(ArrayList<Integer>al, int s, int e)
{
if(s>e)
return null;
// make the root asthe middle element
int m = (s+e)/2;
Nodevalue node = new Nodevalue(al.get(m));
node.left = Conversion(al, s, m-1);
node.right = Conversion(al, m+1, e);
return node;
}
// Method that merges two trees into a single one.
Nodevalue treeMerge(Nodevalue node1, Nodevalue node2)
{
//Stores Inorder of tree1 to list1
ArrayList<Integer>al1 = storeorder(node1);
//Stores Inorder of tree2 to list2
ArrayList<Integer>al2 = storeorder(node2);
// Merges both list1 and list2 into list3
ArrayList<Integer>al3 = merge(al1, al2, al1.size(), al2.size());
//Eventually converts the merged list into resultant BST
Nodevalue node = Conversion(al3, 0, al3.size()-1);
return node;
}
// Driver function
public static void main (String[] args)
{
BinaryTree t1 = new BinaryTree();
t1.root = new Nodevalue(10);
t1.root.left = new Nodevalue(5);
t1.root.right = new Nodevalue(45);
t1.root.left.left = new Nodevalue(19);
t1.root.left.right = new Nodevalue(65);
BinaryTree t2 = new BinaryTree();
t2.root = new Nodevalue(8);
t2.root.left = new Nodevalue(2);
t2.root.right = new Nodevalue(11);
BinaryTree t3 = new BinaryTree();
t3.root = t3.treeMerge(t1.root, t2.root);
System.out.println("The merged sorted tree: ");
t3.order();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.