public class BTreeVsArray {
private static int index = 0;
public static void main(String[] args) {
//assume tree size and array size is equal
//tree size can cost O(1) if node have a size field
//otherwise it can be calculated with cost O(N)
int[] ordered = {1, 5, 6, 9, 10, 11, 12};
int[] ordered1 = {1, 5, 6, 9, 10, 11, 12};
int[] preordered = {9, 1, 5, 6, 10, 11, 12};
int[] preordered1 = {9, 1, 5, 6, 10, 11, 12};
int[] postordered = {1, 5, 10, 11, 9};
int[] postordered1 = {1, 5, 10, 11, 9};
BTree root = arrayToTree(ordered, 0, ordered.length - 1);
printInOrder(root);
System.out.println();
printPreOrder(root);
System.out.println();
printPostOrder(root);
System.out.println();
System.out.println("isInorder: "
+ isInorder(ordered1));
System.out.println("inOrderCompare: "
+ inOrderCompare(root, ordered1));
System.out.println("inOrderCompare2: "
+ inOrderCompare2(root, ordered1, 0, ordered1.length - 1));
BTree root1 = arrayToTreePreOrder(preordered, 0, preordered.length - 1);
printPreOrder(root1);
System.out.println();
printInOrder(root1);
System.out.println();
System.out.println("isPreorder: "
+ isPreorder(preordered1, 0, preordered1.length - 1));
System.out.println("preOrderCompare: "
+ preOrderCompare(root1, preordered1, 0, preordered1.length - 1));
BTree root2 = arrayToTreePostOrder(postordered, 0, postordered.length - 1);
printPostOrder(root2);
System.out.println();
printInOrder(root2);
System.out.println();
System.out.println("isPostorder: "
+ isPostorder(postordered1, 0, postordered1.length - 1));
System.out.println("postOrderCompare: "
+ postOrderCompare(root2, postordered1, 0, postordered1.length - 1));
}
//test if an array is qualified as some tree's in order sequence
public static boolean isInorder(int[] ordered) {
if(ordered == null || ordered.length == 0) return false;
int pre = ordered[0];
for(int i = 0; i < ordered.length - 1; i ++) {
if(ordered[i] < pre) return false;
pre = ordered[i];
}
return true;
}
//test if an array is qualified as some tree's pre order sequence
public static boolean isPreorder(int[] preorder, int start, int end) {
if(preorder == null || preorder.length == 0) return false;
if(start > end || start < 0 || end > preorder.length - 1) return true;
int middle = preorder[start];
int i,j;
for(i = start + 1; i <= end; i++) {
if(preorder[i] > middle)
break;
}
for(j = i; j <= end; j++) {
if(middle > preorder[j])
return false;
}
return isPreorder(preorder, start + 1, i - 1) && isPreorder(preorder, i, end);
}
//test if an array is qualified as some tree's post order sequence
//{1, 5, 10, 11, 9}
public static boolean isPostorder(int[] postorder, int start, int end) {
if(postorder == null || postorder.length == 0) return false;
if(start > end || start < 0 || end > postorder.length - 1) return true;
int middle = postorder[end];
int i,j;
for(i = start; i < end; i++) {
if(postorder[i] > middle)
break;
}
for(j = i; j < end; j++) {
if(middle > postorder[j])
return false;
}
return isPostorder(postorder, start, i - 1) && isPostorder(postorder, i, end - 1);
}
//construct a tree from an ordered array
public static BTree arrayToTree(int[] ordered, int start, int end) {
if(ordered == null || ordered.length == 0) return null;
if(start > end || start < 0 || end > ordered.length - 1) {
return null;
}
int middle = (start + end)/2;
BTree root = new BTree(ordered[middle], null, null);
root.left = arrayToTree(ordered, start, middle - 1);
root.right = arrayToTree(ordered, middle + 1, end);
return root;
}
//test if a tree's in order sequence is the same as the array
public static boolean inOrderCompare2(BTree root, int[] inOrder, int start, int end) {
if(inOrder == null || inOrder.length == 0) return false;
if(root == null || start > end) return true;
int middle = (start + end) / 2;
//if(middle > inOrder.length - 1) return false;
boolean left = inOrderCompare2(root.left, inOrder, start, middle - 1);
boolean curr = (root.value == inOrder[middle]);
boolean right = inOrderCompare2(root.right, inOrder, middle + 1, end);
return left && curr && right;
}
//another way to test if a tree's in order sequence is the same as the array
public static boolean inOrderCompare(BTree root, int[] inOrder) {
if(inOrder == null || inOrder.length == 0) return false;
index = 0;
return treeVsArrayInOrder(root, inOrder)
&& index == inOrder.length; //tree and array same size
}
public static boolean treeVsArrayInOrder(BTree root, int[] inOrder) {
if(inOrder == null || inOrder.length == 0) return false;
if(root == null) return true;
boolean left = treeVsArrayInOrder(root.left, inOrder);
if(index > inOrder.length - 1) return false;
boolean middle = root.value == inOrder[index++];
boolean right = treeVsArrayInOrder(root.right, inOrder);
return left && middle && right;
}
//construct a tree from its pre order sequence array
public static BTree arrayToTreePreOrder(int[] preordered, int start, int end) {
if(preordered == null || preordered.length == 0) return null;
if(start > end || start < 0 || end > preordered.length - 1) {
return null;
}
BTree root = new BTree(preordered[start], null, null);
int i;
for(i = start + 1; i <= end; i++) {
if(preordered[i] > preordered[start]) {
break;
}
}
root.left = arrayToTreePreOrder(preordered, start + 1, i - 1);
root.right = arrayToTreePreOrder(preordered, i, end);
return root;
}
//test if a tree's pre order sequence is the same as the array
public static boolean preOrderCompare(BTree root, int[] preorder, int start, int end) {
if(preorder == null || preorder.length == 0) return false;
if(root == null || start > end) return true;
int i;
for(i = start + 1; i <= end; i++) {
if(preorder[i] > preorder[start]) {
break;
}
}
boolean curr = root.value == preorder[start];
boolean left = preOrderCompare(root.left, preorder, start + 1, i-1);
boolean right = preOrderCompare(root.right, preorder, i, end);
return left && curr && right;
}
//construct a tree from its post order sequence array
public static BTree arrayToTreePostOrder(int[] postordered, int start, int end) {
if(postordered == null || postordered.length == 0) return null;
if(start > end || start < 0 || end > postordered.length - 1) {
return null;
}
BTree root = new BTree(postordered[end], null, null);
if(start == end) return root;
int i;
for(i = start; i < end; i++) {
if(postordered[i] > postordered[end]) {
break;
}
}
root.left = arrayToTreePostOrder(postordered, start, i - 1);
root.right = arrayToTreePostOrder(postordered, i, end - 1);
return root;
}
//test if a tree's post order sequence is the same as the array
public static boolean postOrderCompare(BTree root, int[] postorder, int start, int end) {
if(postorder == null || postorder.length == 0) return false;
if(root == null || start > end) return true;
if(root.value != postorder[end]) return false;
int i;
for(i=start; i < end; i++) {
if(postorder[i] > postorder[end])
break;
}
boolean left = postOrderCompare(root.left, postorder, start, i - 1);
boolean curr = root.value == postorder[end];
boolean right = postOrderCompare(root.right, postorder, i, end - 1);
return left && curr && right;
}
//get the size of a tree
public static int count(BTree root) {
if(root == null) return 0;
return count(root.left) + 1 + count(root.right);
}
//record a tree's in order tranversal sequence into an array
public static int[] treeToArrayInorder(BTree root, int[] arr, int start, int end) {
if(root == null) return arr;
if(start > end || start < 0 || end > arr.length - 1) return arr;
int middle = count(root.left);
arr = treeToArrayInorder(root.left, arr, start, start + middle - 1);
arr[start + middle] = root.value;
arr = treeToArrayInorder(root.right, arr, start + middle + 1, end);
return arr;
}
//record a tree's pre order tranversal sequence into an array
public static int[] treeToArrayPreorder(BTree root, int[] arr, int start, int end) {
if(root == null) return arr;
if(start > end || start < 0 || end > arr.length - 1) return arr;
arr[start] = root.value;
int middle = count(root.left);
arr = treeToArrayPreorder(root.left, arr, start + 1, start + middle);
arr = treeToArrayPreorder(root.right, arr, start + middle + 1, end);
return arr;
}
//record a tree's post order tranversal sequence into an array
public static int[] treeToArrayPostorder(BTree root, int[] arr, int start, int end) {
if(root == null) return arr;
if(start > end || start < 0 || end > arr.length - 1) return arr;
arr[end] = root.value;
int middle = count(root.left);
arr = treeToArrayPostorder(root.left, arr, start, start + middle - 1);
arr = treeToArrayPostorder(root.right, arr, start + middle, end - 1);
return arr;
}
//tell if a tree is binary search tree
public static boolean isBinarySearchTree(BTree root) {
if(root == null) return true;
if(root.left != null && root.left.value >= root.value) return false;
if(root.right != null && root.right.value <= root.value) return false;
return isBinarySearchTree(root.left) && isBinarySearchTree(root.right);
}
//helping method
public static void printInOrder(BTree root) {
if(root == null) return;
printInOrder(root.left);
System.out.print(root.value + ", ");
printInOrder(root.right);
}
public static void printPreOrder(BTree root) {
if(root == null) return;
System.out.print(root.value + ", ");
printPreOrder(root.left);
printPreOrder(root.right);
}
public static void printPostOrder(BTree root) {
if(root == null) return;
printPostOrder(root.left);
printPostOrder(root.right);
System.out.print(root.value + ", ");
}
}
