binary tree traversal

This is a discussion on binary tree traversal within the C++ Programming forums, part of the General Programming Boards category; I want to traverse the binary tree breadth-first Code: void Tree::bf_traverse() { qu_node(root); } void Tree::qu_node( Tree::Node* node) { traverse_tree.push(node); ...

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455

    binary tree traversal

    I want to traverse the binary tree breadth-first
    Code:
    void Tree::bf_traverse()
    {
      qu_node(root);
    }
    
    void Tree::qu_node( Tree::Node* node)
    {
      traverse_tree.push(node);
      if(node->relate[1] != NULL)
        {
          
          qu_node(node->relate[1]);
        }
      if(node->relate[2] != NULL)
        qu_node(node->relate[2]);
    }
    where traverse_tree is a queue<Node*>. I thought this will give me breadth first traversal, but it turned out to be depth-first because of the way I recurse. Is there another way to organize this to obtain level-order?
    "All that we see or seem
    Is but a dream within a dream." - Poe

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you want bottom-to-top, wouldn't you want to push the root node on last?

  3. #3
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455
    Quote Originally Posted by tabstop View Post
    If you want bottom-to-top, wouldn't you want to push the root node on last?
    tabstop, actually, I want to push all the nodes in the same level in. What I have just push the in the left child and its children in first, before the right child and its children are pushed in.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Oh right.

    Tree traversal - Wikipedia, the free encyclopedia

    You'll need to process as you go, then.

  5. #5
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455
    gotcha, thanks.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  6. #6
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455
    Found the solution :-D
    Code:
    void Tree::bf_traverse()
    {
      qu_node(root);
    }
    
    // breadth-first tree traversal
    void Tree::qu_node( Tree::Node* node)
    {
      queue<Node*> temp; 
      temp.push(node);
      Tree::Node* p; 
      while( !temp.empty() )
        {
          p = temp.front();
          traverse_tree.push(p);
          
          if(p->relate[1] !=NULL)
    	temp.push(p->relate[1]);
          if(p->relate[2] != NULL)
    	temp.push(p->relate[2]);
          temp.pop(); 
        }
    }
    "All that we see or seem
    Is but a dream within a dream." - Poe

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21