post_traverse.c

#include <stdio.h>

typedef struct Tree {
  struct Tree* left;
  struct Tree* right;
  int value;
} Tree;

void PostTraverse(Tree* node) {
  if (node) {
    PostTraverse(node->left);
    PostTraverse(node->right);
    printf("%d\n", node->value);
  }
}

typedef struct Frame {
  Tree* node;
  int state;
} Frame;

void PostTraverseImpl(Frame* stack, int* top) {
  Frame* current_frame = &stack[(*top)-1];
  switch (current_frame->state++) {
  case 0:
    if (current_frame->node) {
      stack[*top].node = current_frame->node->left;
      stack[*top].state = 0;
      (*top)++;
      return;
  case 1:
      stack[*top].node = current_frame->node->right;
      stack[*top].state = 0;
      (*top)++;
      return;
  case 2:
      printf("%d\n", current_frame->node->value);
    }
    (*top)--;
  }
}

void PostTraverseNonRecursive(Tree* node) {
  Frame stack[100000];
  int top = 0;
  stack[top].node = node;
  stack[top].state = 0;
  top++;
  while (top > 0) {
    PostTraverseImpl(stack, &top);
  }
}

int main() {
  Tree nodes[5];
  nodes[0].left = &nodes[1];
  nodes[0].right = &nodes[2];
  nodes[1].left = NULL;
  nodes[1].right = &nodes[3];
  nodes[2].left = &nodes[4];
  nodes[2].right = NULL;
  nodes[3].left = NULL;
  nodes[3].right = NULL;
  nodes[4].left = NULL;
  nodes[4].right = NULL;

  nodes[0].value = 0;
  nodes[1].value = 1;
  nodes[2].value = 2;
  nodes[3].value = 3;
  nodes[4].value = 4;

  PostTraverseNonRecursive(&nodes[0]);

  return 0;
}