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'

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.

Fixed that and added comment pointing to the first error.

Quote:

---

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).

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;
  } 
}

---

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

>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 );
    }
  }
}

---

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.

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;
     
    }
  }
}

---