felipera
BAN USERJava Version (using list just for convinience):
public static int search(List<Integer> i, int x, int start, int end) {
int c = 0;
for (Integer j : i.subList(start, end)) {
if ( j == x ) {
break;
}
c++;
}
return c;
}
static int index = 0;
public static TreeNode createTree(List<Integer> preOrder, List<Integer> inOrder, int start, int end) {
// Check Size
if ( index+1 > preOrder.size()-1 ) {
return null;
}
// Check Range
if ( end < start) {
return null;
}
// Find Root
index++;
Integer root = preOrder.get(index);
TreeNode n = new TreeNode(root);
// Check if work is done
if ( start == end ) {
return n;
}
// Find Median
int idx = search(inOrder, root, start, end);
// Build Child Trees
n.left = createTree( preOrder, inOrder, start, idx-1 );
n.right = createTree( preOrder, inOrder, idx+1, end );
// Return Tree
return n;
}
Some Java code I just wrote for a BST:
- felipera August 09, 2010public boolean hasSubTree(BinarySearchTree sub) {
// Try to find head of subtree
TreeNode subHead = this.findNode(sub.root);
if ( subHead == null ) {
System.out.println("Tree head: " + sub.root.data + " NOT found!");
return false;
}
// Ok we found the head let's step on node and see if it matches
return this.navigateAndCompare(subHead, sub.root);
}
private boolean navigateAndCompare(TreeNode n1, TreeNode n2) {
if ( n1 == null && n2 == null ) {
return true;
}
if ( n2 != null && n1 == null ) {
return false;
}
if ( n1 != null && n2 == null ) {
return false;
}
if ( n1.data.equals(n2.data) ) {
boolean left = this.navigateAndCompare(n1.left, n2.left);
boolean right = this.navigateAndCompare(n1.right, n2.right);
if ( left && right ) {
return true;
}
return false;
} else {
System.out.println(n1.data + " does NOT match " + n2.data);
return false;
}
}
private void l(Object o) {
System.out.println(o);
}
public TreeNode findNode(TreeNode node) {
return this.findNode(this.root, node);
}
public TreeNode findNode(TreeNode n, TreeNode node) {
if ( node == null ) {
return null;
}
while ( n != null ) {
if ( n.data.equals(node.data) ) {
return n;
}
if ( node.data.compareTo(n.data) < 0 ) {
return this.findNode(n.left, node);
} else if ( node.data.compareTo(n.data) > 0 ) {
return this.findNode(n.right, node);
}
throw new RuntimeException("It should never get here!");
}
return null;
}