inordine

// Vizitare in inordine, varianta iterativa. Arborele este reprezentat prin vectorii stang, drept, tata si label.

#include <stdio.h>
#include <stdlib.h>

#define NMAX 1000

typedef struct stack {
          int top;
          int a[NMAX];
        } STACK;

int label[NMAX + 1];  // label[k] - eticheta nodului k
int tata[NMAX + 1];   // tata[k] - parintele nodului k, sau 0 daca k este radacina
int stang[NMAX + 1];  // stang[k] - descendentul stang al nodului k, sau 0 daca nu exista
int drept[NMAX + 1];  // drept[k] - descendentul drept al nodului k, sau 0 daca nu exista


void init(STACK* s) {
  s->top = -1;
}

int empty(STACK* s) {
  return (s->top == -1);
}

void push(STACK* s, int x) {
  s->top++;
  s->a[s->top] = x;
}

int peek(STACK* s) {
  return s->a[s->top];
}

void pop(STACK* s) {
  s->top--;
}

void visit(int node, FILE* f) {
  fprintf(f, "%d ", label[node]);
}

void inorder(int k, FILE* fout) {
  int q, j;
  STACK stk;

  init(&stk);
  q = 0;
  while (q == 0) {       // cat timp nu s-a terminat parcurgerea
    // cat timp se poate coboram spre stanga
    while (stang[k] > 0) {
      push(&stk, k);     // salvam pe stiva nodurile din care
                         // coboram spre stanga
      k = stang[k];
    }

    visit(k, fout);

    // incercam sa determinam un nod k ce poseda un descendent drept,
    // descendent drept ce nu a mai fost vizitat
    while ((q == 0) && (drept[k] == 0)) {
      if (empty(&stk)) {
        q = 1;
      } else {
          k = peek(&stk);
          pop(&stk);
          visit(k, fout);
      }
    }

    if (q == 0) {       // daca nu s-a terminat vizitarea
      k = drept[k];     // facem un pas spre dreapta
    }
  }
}


int main() {
  FILE *fin, *fout;
  int n, i, rad;

  fin = fopen("inordine.in", "r");
  fout = fopen("inordine.out", "w");

  fscanf(fin, "%d", &n);
  for (i = 1; i <= n; i++) {
    fscanf(fin, "%d %d %d", &label[i], &stang[i], &drept[i]);

    // pastram tatal fiecarui nod din arbore
    if (stang[i] != 0) {
      tata[stang[i]] = i;
    }

    if (drept[i] != 0) {
      tata[drept[i]] = i;
    }
  }

  // determinam radacina arborelui
  for (i = 1, rad = 0; (i <= n) && (rad == 0); i++) {
    if (tata[i] == 0) {
      rad = i;
    }
  }

  inorder(rad, fout);

  fclose(fin);
  fclose(fout);

  return 0;
}