ansaurus

Question

preorder an array based binary search tree

Answer 1

+1 A:

You should consider a recursive approach rather than an iterative one. Tree traversal (preorder, inorder, and postorder) is very easily done using recursion.

The Wikipedia article on tree traversal has a pseudocode recursive algorithm, but there's really not much to it. Since you're storing the tree in an array, you won't have node pointers, just indices.

As for how you know when you reach the leaf nodes, well, their indices will be beyond the end of the array.

James McNellis 2009-12-01 05:51:11

Yeah, i have looked that over before.To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node: 1. Visit the root. 2. Traverse the left subtree. 3. Traverse the right subtree.how do i know when im done traversing the left in an array?i need a better algorithm. This shouldnt be hard. =(

Corey 2009-12-01 05:57:10

The index is beyond the end of the array. You can pass the size of the array along with the index of the current root in your recursive function.

James McNellis 2009-12-01 06:03:04

Answer 2

+1 A:

Doing a tree traversal is usually done with recursive functions because that is the most natural way to express the traversal.

Doing a pre-order traversal is pretty easy. Ignoring the details, you have something like this:

void do_preorder(Tree t)
{
    // do something with the current tree node

    if (leftnode(t) not empty)
        do_preorder(leftnode(t));
    if (rightnode(t) not empty)
        do_preorder(rightnode(t))
}

If you want to be tricky, you can even create a generic traversal that allows you to choose the flavor (pre-order, in-order or post-order) at runtime:

void do_xorder(Tree t, Flavor f)
{
    if (f == PREORDER)
        handle_currentnode(t)

    if (leftnode(t) not empty)
        do_xorder(leftnode(t), f);

    if (f == INORDER)
        handle_currentnode(t)

    if (rightnode(t) not empty)
        do_xorder(rightnode(t), f)

    if (f == POSTORDER)
        handle_currentnode(t)

}

R Samuel Klatchko 2009-12-01 05:56:44

R Samuel Klatchko 2009-12-01 06:27:02

@R Samuel: If you add an overload that differs only on one argument that has a default value itself, all calls to the function method with a single argument will become ambiguous: the compiler cannot determine which overload to call.

David Rodríguez - dribeas 2009-12-01 07:22:58

@dribeas - my suggestion was not to add a new function but to change the existing one.

R Samuel Klatchko 2009-12-01 16:52:59

Answer 3

A:

As per you code you can use (2i + 1) for left and (2i + 2) for right child.

My suggestion that you should start storing elements from index 1 in the array because you can store left child at ( 2 * i) index and right child at (2*i + 1) index .

And end of the left child can be easily found by checking whether ( 2*i > currSize ) is true.

http://en.wikipedia.org/wiki/Tree_traversal

Check out this link for any traversal you want to perform on tree...

Ashish 2009-12-01 06:06:40

ansaurus

tags:

views:

answers:

preorder an array based binary search tree

related questions