How would anyone convert a array based tree into per-order? The array contains:
Cheers
public void preOrder(int index) {
if (index >= currSize) {
return;
}
System.out.println(items[index]);
preOrder(2 ^ index + 1); //left
preOrder((2 ^ index) + 2); //right
}
Should be like the following.
public void preOrder(int index) {
if (index >= currSize) {
return;
}
System.out.println(items[index]);
preOrder((2 * index)+1);
preOrder((2 * index)+2);
}
In pre-order traversal, you process the parent first, then you recursively process the left subtree and right subtree. The representation that you have is basically the same as that of a heap, so it is clear what the left and right children of any node is. This means we can traverse this in pre-order and print out the nodes in the order we visit them.
Pseudo code would be as follows:
print_pre_order(index):
if index is beyond the size of the array:
return
else:
print value at index
print_pre_order(left child of index)
print_pre_order(right child of index)
Since this is arranged as a heap, for each index n the left child is at 2*n and the right child is at 2*(n+1). Note that I am assuming indices of the array start from 1 (though most languages have them start at 0), but you can easily adapt that for 0 based arrays.
^ is the XOR operator in Java, not exponentiation. Replace 2^n with 1<<n (shifting 1 left by n is the same as 2**n).