2叉树后序遍历非递归算法(C语言)

Node {Node * lchild;

Node * rchild;

Data_Type data;

};

 

Temp {Node * node;

int count;

};

 

void fun(Node * root) {

  Temp p = malloc;

  p->node = root;

  p->count = 0;

 

  while(p && s is not empty) {

    if(p->node) {

      p->count++;

      push(p, s);

      p = malloc;

      p->node = p->node->lchild;

      p->count = 0;

    } else {

      p = pop(s);

 

      if(p->count == 1) {

          p->count++;

          push(p, s);

          p = p->rchild;

      } else{

          visit(p->node);

          p->node = null;

       }

 

    }

  }

}

 

//语法不一定对，整体思路和前序中序无太大差别，只不过唯一区别在于，每个节点会进2次栈，Temp.count用来记录节点进栈次数，当第2次出来时候，就是后序访问该节点