preordine

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

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

#define NMAX 1000

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 visit(int node, FILE* f) {
  fprintf(f, "%d ", label[node]);
}

void preorder(int k, FILE* fout) {
  int q, foundNode, j;

  q = 0;
  while (q == 0) {       // cat timp nu s-a terminat parcurgerea
   // cat timp se poate coboram spre stanga
    while (stang[k] > 0) {
      visit(k, fout);
      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)) {
      foundNode = 0;     // ia valoarea 1 atunci cand urcam intr-un nod venind din stanga
      while ((q == 0) && (foundNode == 0)) {
        j = k;
        k = tata[k];
        if (k == 0) {
          q = 1;
        } else {
            if (drept[k] != j) {
              foundNode = 1;
            }
        }
      }
    }

    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("preordine.in", "r");
  fout = fopen("preordine.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;
    }
  }

  preorder(rad, fout);

  fclose(fin);
  fclose(fout);

  return 0;
}