java - BST 旋转使一棵树与另一棵树相等
问题描述
我有这个问题:给定两个非空二叉搜索树 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 };
}
}
解决方案
//I understand this is quite late but this is more for people who look now for this help
public static void problem(BST tree1, BST tree2)
{
//if root is null then we've reached the end of a branch (base case)
if(tree1.root == null || tree2.root == null)
{
return;
}
//finding the node we need to rotate to tree1's root to match 2nd tree
Node match = tree1.find(tree2.getRootKey());
//loop to rotate matched node until it becomes tree1's new root or parent of the root
while(match != tree1.root && match != tree1.root.parent)
{
//parent node of matched node we need to get to new position
Node matchParent = match.parent;
//move matched node we want up the levels of tree1
//if matched node key is more than its parent then rotate parent left (which moves matched node up a level)
//otherwise rotate the parent right (still moves matched node up a level)
if(match.key > matchParent.key)
{
tree1.rotateL(matchParent);
}
else
{
tree1.rotateR(matchParent);
}
}
//if the matched node becomes the parent of tree1's root, in the loop above, then we need to
//change it so that the matched node is the root to line up with tree2
if(match == tree1.root.parent)
{
tree1.root = match;
}
// recursively go through left tree
// new BSTs to signify left subtrees
BST leftTree1 = new BST();
BST leftTree2 = new BST();
leftTree1.root = tree1.root.left;
leftTree2.root = tree2.root.left;
problem(leftTree1, leftTree2);
// recursively go through right tree
// new BSTs to signify right subtrees
BST rightTree1 = new BST();
BST rightTree2 = new BST();
rightTree1.root = tree1.root.right;
rightTree2.root = tree2.root.right;
problem(rightTree1, rightTree2);
}
推荐阅读
- javascript - 将 ArcGIS v 3.2 WMS 图层转换为 4.7
- python - Pyparsing:在 parseaction 中访问外部 ParseResults
- javascript - 为什么我在点击我的 div 元素后被重定向?
- ios - 如何将 NSString 值转换为 NSMutableData?货币字符
- python - Python 3.6:'elif' 语句破坏了单词交换功能
- ios - 自定义表格视图单元格中的 UITextField。点击单元格/文本字段时显示选择器视图
- struct - 如何在具有 cfquery 列的结构中设置动态键名?
- css - 如何使用 mini-css-extract-plugin 将导入的 css 和从 scss 生成的 css 合并到一个文件中?
- redux - redux-api-middleware RSA SUCCESS 动作元属性丢失
- javascript - JS下载多个文件