我有这个问题：给定两个非空二叉搜索树 T1 和 T2。T1 和 T2 存储相同的键。然而，这两种树的结构是不同的。实现一个算法，在 T1 上使用旋转使其与 T2 等价。也就是说，两棵树应该具有相同的结构。请注意，您只能在 T1 上使用旋转；您不得以任何其他方式修改树。
如果有人能帮助我朝着正确的方向推进，我将非常感激。这是到目前为止的代码。
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!
//Base Case
if(tree1 == null && tree2 == null){
return;
}
}
// ---------------------------------------------------------------------
// 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;
public int getRootKey()
{
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 Lab1
{
// ---------------------------------------------------------------------
// Do not change any of the code below!
private static final int LabNo = 4;
private static final String quarter = "Fall 2020";
private static final Random rng = new Random(190718);
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;
long start = System.currentTimeMillis();
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;
}
}
System.out.println((System.currentTimeMillis() - start) + " ms");
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 };
}
}