how to walk a binary tree

Discussion in 'C++' started by pembed2003, Apr 19, 2004.

  1. pembed2003

    pembed2003 Guest

    Hi,
    I have a question about how to walk a binary tree. Suppose that I have
    this binary tree:

    8
    / \
    5 16
    / \ / \
    3 7 9 22
    / \ / \ / \
    1 4 6 10 17 34
    /
    0

    and I want to print out the binary tree like:

    8 5 16 3 7 9 22 1 4 6 10 17 34 0

    That's, print all the nodes out in level order. Currently, I have the
    following:

    void order(node* d,int level,int child){
    if(d){
    int w = level + child;
    printf("%d [%d]\n",d->data,w);
    order(d->left,level + 2,1); // one more level for a left child
    order(d->right,level + 2,2); // one more level for a right child
    }
    }

    My plan is that each node has a weight which is equal to the level the
    node is at and whether it's a left or right child. The idea is that
    the deeper the node, the "heavier" it's and left child is always
    heavier than the right child. Instead of a printf statement, I can put
    the nodes into an array, and then I can sort the array (using a stable
    sort) according to their weight and print out each nodes. Although
    this seems to work, the book that I am reading suggest using a queue
    to solve the problem, but I don't know how a queue can help. Can
    someone give me a little help? I am NOT looking for actual code, just
    some hints on how a queue can help me manage this level-order walk of
    the binary tree? Thanks!
    pembed2003, Apr 19, 2004
    #1
    1. Advertising

  2. pembed2003

    red floyd Guest

    pembed2003 wrote:
    > Hi,
    > I have a question about how to walk a binary tree. Suppose that I have
    > this binary tree:
    >
    > 8
    > / \
    > 5 16
    > / \ / \
    > 3 7 9 22
    > / \ / \ / \
    > 1 4 6 10 17 34
    > /
    > 0
    >
    > and I want to print out the binary tree like:
    >
    > 8 5 16 3 7 9 22 1 4 6 10 17 34 0
    >
    > That's, print all the nodes out in level order. Currently, I have the
    > following:
    >
    > void order(node* d,int level,int child){
    > if(d){
    > int w = level + child;
    > printf("%d [%d]\n",d->data,w);
    > order(d->left,level + 2,1); // one more level for a left child
    > order(d->right,level + 2,2); // one more level for a right child
    > }
    > }
    >
    > My plan is that each node has a weight which is equal to the level the
    > node is at and whether it's a left or right child. The idea is that
    > the deeper the node, the "heavier" it's and left child is always
    > heavier than the right child. Instead of a printf statement, I can put
    > the nodes into an array, and then I can sort the array (using a stable
    > sort) according to their weight and print out each nodes. Although
    > this seems to work, the book that I am reading suggest using a queue
    > to solve the problem, but I don't know how a queue can help. Can
    > someone give me a little help? I am NOT looking for actual code, just
    > some hints on how a queue can help me manage this level-order walk of
    > the binary tree? Thanks!


    What you want is actually OT for this group, you should look in an algorithms
    group. That said, you should also google for "Breadth First Search".
    Generally, the answer involves a queue.

    e.g.:

    [warning -- fragment, not full or tested code]

    class Node;

    void bfs(const Node* pNode)
    {
    std::queue<const Node*> q;

    q.push(pNode);
    while (!q.empty())
    {
    pNode = q.pop();
    if (pNode->left)
    q.push(pNode->left);
    if (pNode->right)
    q.push(pNode->right);
    // do something with pNode here
    }
    }
    red floyd, Apr 19, 2004
    #2
    1. Advertising

  3. pembed2003

    Siemel Naran Guest

    "pembed2003" <> wrote in message
    news:...

    > Hi,
    > I have a question about how to walk a binary tree. Suppose that I have
    > this binary tree:
    >
    > 8
    > / \
    > 5 16
    > / \ / \
    > 3 7 9 22
    > / \ / \ / \
    > 1 4 6 10 17 34
    > /
    > 0
    >
    > and I want to print out the binary tree like:
    >
    > 8 5 16 3 7 9 22 1 4 6 10 17 34 0


    Do you know the number of elements in the binary tree? If this is the case,
    you can pass the location recursively to the print function on the left and
    right child.

    void print(const node *, int slot); // prints node->value in array[slot]

    If the current node prints into slot, the left child prints into 2*slot+1,
    and the right child prints into 2*slot+2. This method can work even if the
    tree is not perfectly balanced; for example, if the node one 16 does not
    exist, then array[2] will be NULL. In the printed string we will ignore
    NULL values. The initial array size should be rounded up to the next 2^N-1
    (eg. 4,5,6,7 rounds up to 7).

    > That's, print all the nodes out in level order. Currently, I have the
    > following:
    >
    > void order(node* d,int level,int child){
    > if(d){
    > int w = level + child;
    > printf("%d [%d]\n",d->data,w);
    > order(d->left,level + 2,1); // one more level for a left child
    > order(d->right,level + 2,2); // one more level for a right child
    > }
    > }
    >
    > My plan is that each node has a weight which is equal to the level the
    > node is at and whether it's a left or right child. The idea is that
    > the deeper the node, the "heavier" it's and left child is always
    > heavier than the right child. Instead of a printf statement, I can put
    > the nodes into an array, and then I can sort the array (using a stable
    > sort) according to their weight and print out each nodes. Although
    > this seems to work, the book that I am reading suggest using a queue
    > to solve the problem, but I don't know how a queue can help. Can
    > someone give me a little help? I am NOT looking for actual code, just
    > some hints on how a queue can help me manage this level-order walk of
    > the binary tree? Thanks!


    For breadth first search, one can use a queue. Push the left and right
    child into the queue. As long as the queue has elements in it, pop the
    element and print the node value, and push the node's children. So you push
    level one 5, push level one 16, pop level one 5, print 5, push level two 3,
    push level two 7, pop level one 16, print 16, push level two 9, push level
    two 22. Use std::queue<const node *>.

    If you have to use depth first search for some reason, you can use priority
    queue. The depth level is the priority, and the lowest priority should be
    popped first. Call the print function recursively on the left then right
    node. You'll need std::priority_queue<struct> where struct contains the
    depth level and node value. You'll push level zero 8, level one 5, level
    two 3, ..., level one 16, etc. Popping, you'll get level zero 8, level one
    5, level one 16, etc. It's conceptually similar to your original algorithm,
    and the priority queue is like your sorted array.
    Siemel Naran, Apr 19, 2004
    #3
  4. pembed2003

    Siemel Naran Guest

    "red floyd" <> wrote in message news:iEJgc.24133

    > void bfs(const Node* pNode)
    > {
    > std::queue<const Node*> q;
    >
    > q.push(pNode);
    > while (!q.empty())
    > {
    > pNode = q.pop();


    In order to be strongly exception safe, the standard required pop to return
    void. Use front to get a reference to the top element, and after processing
    call pop.

    > if (pNode->left)
    > q.push(pNode->left);
    > if (pNode->right)
    > q.push(pNode->right);
    > // do something with pNode here
    > }


    Call pop here.

    > }
    Siemel Naran, Apr 19, 2004
    #4
  5. pembed2003

    red floyd Guest

    Siemel Naran wrote:
    > "red floyd" <> wrote in message news:iEJgc.24133
    > [Siemel's comments redacted]


    Note that I did say it was fragmentary and not tested. It was
    essentially an algorithmic description, not intended to be used as
    production code.
    red floyd, Apr 19, 2004
    #5
  6. pembed2003

    Anonymous Guest

    "red floyd" <> wrote in message
    news:iEJgc.24133$...
    > pembed2003 wrote:
    > > Hi,
    > > I have a question about how to walk a binary tree. Suppose that I have
    > > this binary tree:
    > >
    > > 8
    > > / \
    > > 5 16
    > > / \ / \
    > > 3 7 9 22
    > > / \ / \ / \
    > > 1 4 6 10 17 34
    > > /
    > > 0
    > >
    > > and I want to print out the binary tree like:
    > >
    > > 8 5 16 3 7 9 22 1 4 6 10 17 34 0
    > >
    > > That's, print all the nodes out in level order. Currently, I have the
    > > following:

    >
    > [warning -- fragment, not full or tested code]
    >
    > class Node;
    >
    > void bfs(const Node* pNode)
    > {
    > std::queue<const Node*> q;
    >
    > q.push(pNode);
    > while (!q.empty())
    > {
    > pNode = q.pop();
    > if (pNode->left)
    > q.push(pNode->left);
    > if (pNode->right)
    > q.push(pNode->right);
    > // do something with pNode here
    > }
    > }


    Maybe I'm being a bit thick here but can someone please point out to me
    where the recursion is, here? How does bfs() search through an entire tree,
    breadth first or otherwise?
    Anonymous, Apr 19, 2004
    #6
  7. pembed2003

    Siemel Naran Guest

    "Anonymous" <> wrote in message news:qtVgc.1547
    > "red floyd" <> wrote in message


    > > void bfs(const Node* pNode)
    > > {
    > > std::queue<const Node*> q;
    > >
    > > q.push(pNode);
    > > while (!q.empty())
    > > {
    > > pNode = q.pop();
    > > if (pNode->left)
    > > q.push(pNode->left);
    > > if (pNode->right)
    > > q.push(pNode->right);
    > > // do something with pNode here
    > > }
    > > }

    >
    > Maybe I'm being a bit thick here but can someone please point out to

    me
    > where the recursion is, here? How does bfs() search through an entire

    tree,
    > breadth first or otherwise?


    Pushing the node's children into the queue and repeating the while loop
    covers the entire tree. When processing each of those nodes, you'll repeat
    the body of the while loop which says to push that node's children into the
    queue.

    bfs() is not recursive. Any recursive algorithm would always proceed depth
    first.

    Also, many (if not all) recursive loops can be written as while.

    unsigned fibonacci(unsigned x) {
    if (x<=2u) return 1u;
    return fibonacci(x-1)+fibonacci(x-2);
    }

    unsigned fibonacci(unsigned x) {
    unsigned result = 1u;
    unsigned prevresult = 1u;
    for ( ; x>2u; --x) {
    unsigned newresult = result+prevresult;
    prevresult = result;
    result = newresult;
    }
    return result;
    }
    Siemel Naran, Apr 19, 2004
    #7
  8. pembed2003

    pembed2003 Guest

    red floyd <> wrote in message news:<iEJgc.24133$>...
    > pembed2003 wrote:
    > > Hi,
    > > I have a question about how to walk a binary tree. Suppose that I have
    > > this binary tree:
    > >
    > > 8
    > > / \
    > > 5 16
    > > / \ / \
    > > 3 7 9 22
    > > / \ / \ / \
    > > 1 4 6 10 17 34
    > > /
    > > 0
    > >
    > > and I want to print out the binary tree like:
    > >
    > > 8 5 16 3 7 9 22 1 4 6 10 17 34 0
    > >
    > > That's, print all the nodes out in level order.


    [snip]

    >
    > What you want is actually OT for this group, you should look in an algorithms
    > group. That said, you should also google for "Breadth First Search".
    > Generally, the answer involves a queue.
    >
    > e.g.:
    >
    > [warning -- fragment, not full or tested code]
    >
    > class Node;
    >
    > void bfs(const Node* pNode)
    > {
    > std::queue<const Node*> q;
    >
    > q.push(pNode);
    > while (!q.empty())
    > {
    > pNode = q.pop();
    > if (pNode->left)
    > q.push(pNode->left);
    > if (pNode->right)
    > q.push(pNode->right);
    > // do something with pNode here
    > }
    > }


    Hi,
    I tried your solution and it works fine. Thanks for the help!
    pembed2003, Apr 20, 2004
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,110
  2. sharan
    Replies:
    4
    Views:
    689
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    830
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    689
    CBFalconer
    Oct 30, 2007
  5. Marcus Alves Grando
    Replies:
    7
    Views:
    465
    Marcus Alves Grando
    Nov 14, 2007
Loading...

Share This Page