public class BTreeCopy {
public static void main(String... args) {
int[] ordered = {1, 2, 3, 4, 5, 6, 7, 8, 9};
BTree root = arrayToTree(ordered, 0, ordered.length - 1);
System.out.println("original tree");
printLevelOrder(root);
BTree root2 = copyTree(root);
System.out.println("copied tree");
printLevelOrder(root2);
BTree root4 = copyTreeMirror(root);
System.out.println("copied mirror tree");
printLevelOrder(root4);
BTree root5 = makeMirrorInPlace(root);
System.out.println("make mirror tree in place");
printLevelOrder(root5);
BTree root1 = arrayToTree(ordered, 0, ordered.length - 1);
System.out.println("root1 and root2 should be the same." + compareTree(root1, root2));
System.out.println("root1 and root4 should not be the same." + compareTree(root1, root4));
System.out.println("root4 and root5 should be the same." + compareTree(root4, root5));
System.out.println("root and root4 should be the same." + compareTree(root, root4));
}
//create a binary search from an ordered array
public static BTree arrayToTree(int[] ordered, int start, int end) {
BTree root = null;
if(start > end)
return null;
int middle = (start + end)/2;
root = new BTree(ordered[middle], null, null);
root.left = arrayToTree(ordered, start, middle - 1);
root.right = arrayToTree(ordered, middle + 1, end);
return root;
}
//copy a tree to another tree
public static BTree copyTree(BTree root) {
if(root == null) {
return null;
}
BTree root2 = new BTree(root.value, null, null);
root2.left = copyTree(root.left);
root2.right = copyTree(root.right);
return root2;
}
//copy a tree's mirror image to another tree
public static BTree copyTreeMirror(BTree root) {
if(root == null) {
return null;
}
BTree root2 = new BTree(root.value, null, null);
root2.left = copyTreeMirror(root.right);
root2.right = copyTreeMirror(root.left);
return root2;
}
//convert a tree to its mirror image in place
public static BTree makeMirrorInPlace(BTree root) {
if(root == null) {
return null;
}
BTree tmp = root.left;
root.left = root.right;
root.right = tmp;
makeMirrorInPlace(root.left);
makeMirrorInPlace(root.right);
return root;
}
//compare 2 binary search trees
public static boolean compareTree(BTree root1, BTree root2) {
if(root1 == null && root2 == null) return true;
if(root1 == null && root2 != null) return false;
if(root1 != null && root2 == null) return false;
if(root1.value != root2.value) return false;
return compareTree(root1.right, root2.right) && compareTree(root1.left, root2.left);
}
//get the height of a tree
public static int height(BTree root) {
if(root == null) return 0;
int lheight = height(root.left);
int rheight = height(root.right);
return lheight >= rheight ? lheight + 1 : rheight + 1;
}
//print a tree with the level order
public static void printLevelOrder(BTree root) {
int level = height(root);
for(int i = 1; i <= level; i++) {
printOneLevel(root, i);
System.out.println();
}
}
public static void printOneLevel(BTree root, int level) {
if(level <= 0 || root == null) return;
if(level == 1) {
System.out.print(root.value + " ");
return;
}
printOneLevel(root.left, level - 1);
printOneLevel(root.right, level - 1);
}
}
