Here is the code for the questions please do all the implementations inside the BST class and inside the problem(BST tree1, BST tree2) function. Don’t change any other code. Thank you!
The lab4 class is just for tests don’t worry about it.
import java.io.*;
import java.util.*;
public class BST
{
/**
* Problem: Perform rotations on tree1 to make it equivalent to tree2.
*/
public static void problem(BST tree1, BST tree2)
{
// Implement me!
}
// ———————————————————————
// Do not change any of the code below!
private class Node
{
public Node left = null;
public Node right = null;
public Node parent = null;
public int key;
public Node(int key)
{
this.key = key;
}
}
private Node root = null;
{
return root.key;
}
private Node find(int key)
{
for (Node cur = root; cur != null;)
{
if (key < cur.key)
{
cur = cur.left;
}
else if (key == cur.key)
{
return cur;
}
else // key > cur.key
{
cur = cur.right;
}
}
return null;
}
// x y
// / /
// a y => x c
// / /
// b c a b
private void rotateL(Node xNode)
{
Node xPar = xNode.parent;
boolean isRoot = xPar == null;
boolean isLChild = !isRoot && xPar.left == xNode;
Node yNode = xNode.right;
Node beta = yNode.left;
if (isRoot) root = yNode;
else if (isLChild) xPar.left = yNode;
else xPar.right = yNode;
yNode.parent = xPar;
yNode.left = xNode;
xNode.parent = yNode;
xNode.right = beta;
if (beta != null) beta.parent = xNode;
}
// y x
// / /
// x c => a y
// / /
// a b b c
private void rotateR(Node yNode)
{
Node yPar = yNode.parent;
boolean isRoot = yPar == null;
boolean isLChild = !isRoot && yPar.left == yNode;
Node xNode = yNode.left;
Node beta = xNode.right;
if (isRoot) root = xNode;
else if (isLChild) yPar.left = xNode;
else yPar.right = xNode;
xNode.parent = yPar;
xNode.right = yNode;
yNode.parent = xNode;
yNode.left = beta;
if (beta != null) beta.parent = yNode;
}
public void insert(int key)
{
if (root == null)
{
root = new Node(key);
return;
}
Node par = null;
for (Node node = root; node != null;)
{
par = node;
if (key < node.key)
{
node = node.left;
}
else if (key > node.key)
{
node = node.right;
}
else // key == node.key
{
// Nothing to do, because no value to update.
return;
}
}
// Create node and set pointers.
Node newNode = new Node(key);
newNode.parent = par;
if (key < par.key) par.left = newNode;
else par.right = newNode;
}
public int[] getInOrder()
{
if (root == null) return new int[] { };
Stack<Node> stack = new Stack<Node>();
ArrayList<Integer> orderList = new ArrayList<Integer>();
for (Node node = root;;)
{
if (node == null)
{
if (stack.empty()) break;
node = stack.pop();
orderList.add(node.key);
node = node.right;
}
else
{
stack.push(node);
node = node.left;
}
}
int[] order = new int[orderList.size()];
for (int i = 0; i < order.length; i++)
{
order[i] = orderList.get(i);
}
return order;
}
public int[] getPreOrder()
{
if (root == null) return new int[] { };
Stack<Node> stack = new Stack<Node>();
ArrayList<Integer> orderList = new ArrayList<Integer>();
for (Node node = root;;)
{
if (node == null)
{
if (stack.empty()) break;
node = stack.pop();
node = node.right;
}
else
{
orderList.add(node.key);
stack.push(node);
node = node.left;
}
}
int[] order = new int[orderList.size()];
for (int i = 0; i < order.length; i++)
{
order[i] = orderList.get(i);
}
return order;
}
}
import java.io.*;
import java.util.*;
public class Lab4
{
// ———————————————————————
// Do not change any of the code below!
private static final int LabNo = 4;
private static final String quarter = “Spring 2020”;
private static final Random rng = new Random(190817);
private static boolean testProblem(int[][] testCase)
{
int[] arr1 = testCase[0];
int[] arr2 = testCase[1];
// — Build tree —
BST tree1 = new BST();
BST tree2 = new BST();
for (int i = 0; i < arr1.length; i++)
{
tree1.insert(arr1[i]);
tree2.insert(arr2[i]);
}
int[] pre2 = tree2.getPreOrder();
BST.problem(tree1, tree2);
// — Verify tree. —
int[] pre1 = tree1.getPreOrder();
int[] in1 = tree1.getInOrder();
if (in1.length != arr1.length) return false;
for (int i = 0; i < in1.length; i++)
{
if (in1[i] != i) return false;
if (pre1[i] != pre2[i]) return false;
}
return true;
}
public static void main(String args[])
{
System.out.println(“CS 302 — ” + quarter + ” — Lab ” + LabNo);
testProblems(1);
}
private static void testProblems(int prob)
{
int noOfLines = 100000;
System.out.println(“– — — — –“);
System.out.println(noOfLines + ” test cases for problem ” + prob + “.”);
boolean passedAll = true;
for (int i = 1; i <= noOfLines; i++)
{
boolean passed = false;
boolean exce = false;
try
{
int[][] testCase = createProblem(i);
passed = testProblem(testCase);
}
catch (Exception ex)
{
passed = false;
exce = true;
}
if (!passed)
{
System.out.println(“Test ” + i + ” failed!” + (exce ? ” (Exception)” : “”));
passedAll = false;
break;
}
}
if (passedAll)
{
System.out.println(“All test passed.”);
}
}
private static void shuffle(int[] arr)
{
for (int i = 0; i < arr.length – 1; i++)
{
int rndInd = rng.nextInt(arr.length – i) + i;
int tmp = arr[i];
arr[i] = arr[rndInd];
arr[rndInd] = tmp;
}
}
private static int[][] createProblem(int testNo)
{
int size = rng.nextInt(Math.min(200, testNo)) + 1;
int[] numbers1 = new int[size];
int[] numbers2 = new int[size];
for (int i = 0; i < size; i++)
{
numbers1[i] = i;
numbers2[i] = i;
}
shuffle(numbers1);
shuffle(numbers2);
return new int[][] { numbers1, numbers2 };
}
}
0 comments