Thread: post order iterative help

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    450

    post order iterative help

    I have been struggling with implementing a post order iterative traversal of a binary tree. One of the exercises from preludes post. I wracked my brain trying to do it without implementing this state structure, but am having problems debugging having given in to it's use. Here is the code
    Code:
    void post_order_traverse_iterative(tree_node* root, fptraction action)
    {
      
      struct state_node{
        tree_node * header;
        BOOL state;
        state_node(tree_node * hd, BOOL st):header(hd), state(st){};
      };
    
      state_node* temp_state_node=new state_node{0,FALSE};
      struct state_node *save[50];
      int top = 0;
       
        
      while (root != NULL){
        save[top++]=new state_node(root,FALSE);
        root=root->left;
      }
        
      temp_state_node=save[--top];// first error here type mismatch?
          
      if (!(temp_state_node->state)){
          temp_state_node->state=TRUE;
          save[top++]=temp_state_node;
      }
      else{
        temp_state_node=save[--top];
        action(temp_state_node.header);
        delete temp_state_node;
      }  
    }
    I am getting a number of errors, some help getting past the first one would be great. I don't know if the logic is sound but need to fix the syntax error to test it.

    Here are the errors
    binarytree.cc:79: error: invalid conversion from `state_node*' to `int'
    binarytree.cc:81: error: syntax error before `if'
    binarytree.cc:83: error: ISO C++ forbids declaration of `save' with no type
    binarytree.cc:83: error: variable-size type declared outside of any function
    binarytree.cc:83: error: conflicting types for `int save[2]'
    binarytree.cc:70: error: previous declaration as `state_node*save[50]'
    binarytree.cc:84: error: syntax error before `}' token
    binarytree.cc:87: error: request for member `header' in `temp_state_node',
    which is of non-class type `int'
    binarytree.cc:87: error: ISO C++ forbids declaration of `action' with no type
    binarytree.cc:88: error: syntax error before `delete'
    Last edited by curlious; 01-02-2004 at 09:31 PM.

  2. #2
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    First, temp_state_node. is probably not right. Maybe it should be temp_state_node-> in at least two places. Also, its hard to tell which lines refer to what based on your posted code.

    [EDIT] - Also, you used curly braces instead of parentheses when you created temp_state_node with new, and you don't need the struct part of your declaration of state.
    Last edited by jlou; 01-02-2004 at 09:32 PM.

  3. #3
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Fixed that and added comment pointing to the first error.

  4. #4
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    Originally posted by curlious
    Fixed that and added comment pointing to the first error.
    Also look at my edit for the big culprit (curly braces).

  5. #5
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Thanks a lot of little bugs that a more experienced C++ programmer wouldn't have made.
    Here is the fixed code which now compiles just about to test it.
    Code:
    void post_order_traverse_iterative(tree_node* root, fptraction action)
    {
      
      struct state_node{
        tree_node * header;
        bool state;
        state_node(tree_node * hd, bool st):header(hd), state(st){};
      };
    
      state_node* temp_state_node=new state_node(0,false);
      state_node *save[50];
      int top = 0;
       
        
      while (root != NULL){
        save[top++]=new state_node(root,false);
        root=root->left;
      }
        
      temp_state_node=save[--top];
          
      if (!(temp_state_node->state)){
          temp_state_node->state=true;
          save[top++]=temp_state_node;
      }
      else{
        temp_state_node=save[--top];
        action(temp_state_node->header);
        delete temp_state_node;
      }  
    }

  6. #6
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Help me fix the logic, I'm going to sleep on this and try again in the morning in the mean time any helpful hints would be appreciated
    Code:
    void post_order_traverse_iterative(tree_node* root, fptraction action)
    {
      
      struct state_node{
        tree_node * header;
        bool state;
        state_node(tree_node * hd, bool st):header(hd), state(st){};
      };
    
      state_node* temp_state_node=new state_node(root,false);
      state_node *save[50];
      int top = 0;
    
      save[top++]=temp_state_node;
    
      do{   
        while (root->left != NULL){
          save[top++]=new state_node(root->left,false);
          root=root->left;
        }
        if (top !=0)
          temp_state_node=save[--top];
        //cout << temp_state_node->header->word << temp_state_node->state<<endl;
    
        if (!(temp_state_node->state)){
          temp_state_node->state=true;
          save[top++]=temp_state_node;
          root=temp_state_node->header->right;
          if (root != NULL)
    	save[top++]=new state_node(root,0);
        }
        else{
          action(temp_state_node->header);
          delete temp_state_node;
          if (top !=0)
    	temp_state_node=save[--top];
          root=temp_state_node->header;
        }
      } while (top  != 0);
    }
    
    
    void level_order_traverse(tree_node* root, fptraction action )
    {
      struct tree_node *save[50];
      int front = 0;
      int back = 0;
    
      if ( root == NULL )
        return;
      save[front++] = root;
      while ( front != back ) {
        root = save[back++];
        action ( root );
        if ( root->left != NULL )
          save[front++] = root->left;
        if ( root->right != NULL )
          save[front++] = root->right;
      }
    }
    updated a couple of changes
    getting a segmentation fault
    Last edited by curlious; 01-02-2004 at 11:44 PM.

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >any helpful hints would be appreciated
    You're on the right track. Consider this logic:
    Code:
    if root == null
      return
    v = not_seen
    stack = root, not_seen
    root = root.left
    while stack != empty
      if root != null && v == not_seen
        stack = root, not_visited
        root = root.left
      else
        root, v = stack
        if v == not_visited
          stack = root, visited
          root = root.right
          v = not_seen
        else
          visit ( root )
    And since I've effectively given you the solution, here is the above pseudocode translated into C/C++ (don't look if you want to do it yourself ):
    Code:
    #define NOT_SEEN 0
    #define NOT_VISITED 1
    #define VISITED 2
    
    void pretree_postorder (
      struct pretree_node *header,
      void (*action) ( struct pretree_node *node ) )
    {
      struct save_stack {
        struct pretree_node *node;
        int visited;
      } save[50];
      int top = 0;
      int visited = NOT_SEEN;
    
      if ( header == NULL )
        return;
      save[top].node = header;
      save[top++].visited = NOT_VISITED;
      header = header->link[0];
      while ( top != 0 ) {
        if ( header != NULL && visited == NOT_SEEN ) {
          save[top].node = header;
          save[top++].visited = NOT_VISITED;
          header = header->link[0];
        }
        else {
          header = save[--top].node;
          visited = save[top].visited;
          if ( visited == NOT_VISITED ) {
            save[top].node = header;
            save[top++].visited = VISITED;
            header = header->link[1];
            visited = NOT_SEEN;
          }
          else
            action ( header );
        }
      }
    }
    My best code is written with the delete key.

  8. #8
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Found this implementation from a java source, had to do quite a bit of searching in some obscure places. It is rather simple
    Code:
    void post_order_traverse_iterative(tree_node* root, fptraction action)
    {
      
      tree_node *save[50];
      int top = 0;
      tree_node * preroot=root;
      
    
      while (root != NULL){
        for ( ;root->left != NULL;root=root->left){
          save[top++]=root;
        }
        while (root != NULL && (root->right == NULL || root->right == preroot))
          {
    	action(root);
    	preroot=root;
    	if (top == 0)
    	  return;
    	
    	root=save[--top];
          }
        save[top++]=root;
        root=root->right;
      }
    }
    Well sadly I couldn't get my algorithim to work but I think it was flawed fundamentally. PS if anyone wants to play with my algorithim and get it working I would really like to see what you did. I may work on it a bit after my mind has relaxed and digested what I have done.
    Last edited by curlious; 01-03-2004 at 10:31 AM.

  9. #9
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Here is the latest revision of my code which still isn't working properly. Any input would be appreciated I have to go to work for now so...
    Code:
    void post_order_traverse_iterative(tree_node* root, fptraction action)
    {
      
      struct state_node{
        tree_node * header;
        bool state;
        state_node(tree_node * hd, bool st):header(hd), state(st){};
      };
    
      state_node* temp_state_node=new state_node(root,false);
      state_node *save[50];
      int top = 0;
    
      save[top++]=temp_state_node;
    
      while (root != NULL){   
        while (root->left != NULL){
          save[top++]=new state_node(root->left,false);
          root=root->left;
        }
       
        temp_state_node=save[--top];
        cout << temp_state_node->header->word << temp_state_node->state<<endl;
    
        if (!(temp_state_node->state)){
          temp_state_node->state=true;
          save[top++]=temp_state_node;
          root=temp_state_node->header->right;
          if (root != NULL){
    	temp_state_node=new state_node(root,0);
    	save[top++]=temp_state_node;
          }
        }
        if(root==NULL || temp_state_node->state){
          action(temp_state_node->header);
          delete temp_state_node;
          temp_state_node=save[--top];
          root=temp_state_node->header;
          
        }
      } 
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help with HTTP POST
    By Anddos in forum Networking/Device Communication
    Replies: 5
    Last Post: 03-22-2009, 08:41 AM
  2. Post your Best Text Adventure
    By Joe100 in forum Game Programming
    Replies: 3
    Last Post: 08-15-2003, 05:47 PM
  3. Auto POST
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 06-07-2003, 10:42 AM