Trees – Traversal Pre-order

1. Check if the current node is empty / null
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function.

/* Se pleaca de la radacina si se merge spre stanga atat cat se poate
Daca nu se mai poate merge spre stanga se face un pas spre dreapta
daca se poate si se reia algoritmul.Daca nu se poate face un pas spre
dreapta,se va urca in arbore pana cand se ajunge in situatia de a se
veni din descendentul stang si se reia algoritmul trecand in descendentul
drept,daca exista.Atunci cand s-a ajuns la radacina venind din dreapta
algoritmul se incheie.Datorita faptului ca atunci cand se urca in arbore
trebuie sa stim din ce descendent venim vom utiliza si vectorul tata.
Ac. procedura poate fi utilizata si pt celelalte parcurgeri(inordine,
postordine),modificarea survenind la momentul cand trebuie vizitat
nodul curent.*/

#define _CRT_SECURE_NO_DEPRECATE	//disable scanf deprecate(?)
#include <stdio.h>


#define MAX 100

//stang[i] - descendentul stang al nodului i: 0 daca nu exista
char stang[MAX];

//drept[i] - descendentul drept al nodului i: 0 daca nu exista
char drept[MAX];

//tata[i] - parintele nodului i
char tata[MAX];

//nr de noduri din arbore
int n;

//nodul radacina din arbore
int rad;

void vizit(int nod)
{
	printf("%2d",nod);
}

void cit_date()
{
	int k;

	printf("Nr.noduri = ");
	scanf("%d",&n);
	printf("Radacina = ");
	scanf("%d",&rad);
	for (k=1;k<=n;k++)
	 {
		printf("stang[%d]= ",k);
		scanf("%d",&stang[k]);
	 }
	for (k=1;k<=n;k++)
	 {
		printf("drept[%d]= ",k);
		scanf("%d",&drept[k]);
	 }
	for (k=1;k<=n;k++)
	 {
		printf("tata[%d]= ",k);
		scanf("%d",&tata[k]);
	 }
}

void preord(int rad)
{
	int i,j;
	int q,q1;

	i = rad;
	q = 0;

	while(q == 0)
	{
		while(stang[i] != 0)
		{
			vizit(i);
			i = stang[i];
		}
		vizit(i);
		while(drept[i] == 0 && q == 0)
		{
			q1 = 0;
			while(q == 0 && q1 == 0)
			{
				j = i;
				i = tata[i];
				if(i == 0)
					q = 1;
				else
					if(j == stang[i])
						q1 = 1;
			}
		}
		if(q == 0)
			i = drept[i];
	}
}

void main()
{
	cit_date();
	preord(rad);
}

/* Nr.noduri = 9
Radacina = 1
stang[1]= 2
stang[2]= 3
stang[3]= 0
stang[4]= 0
stang[5]= 6
stang[6]= 0
stang[7]= 0
stang[8]= 0
stang[9]= 0
drept[1]= 8
drept[2]= 5
drept[3]= 4
drept[4]= 0
drept[5]= 7
drept[6]= 0
drept[7]= 0
drept[8]= 9
drept[9]= 0
tata[1]= 0
tata[2]= 1
tata[3]= 2
tata[4]= 3
tata[5]= 2
tata[6]= 5
tata[7]= 5
tata[8]= 1
tata[9]= 8
 1 2 3 4 5 6 7 8 9 */

41,818 total views, 1 views today