Trees – Traversal In-order

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

/* Se pleaca de la cel mai de jos nod din stanga si se merge spre radacina 
apoi se viziteaza nodul din dreapta radacinii daca exista cat se poate
vizitandu-se mai intai nodul cel mai stang daca exista si apoi cel drept*/

#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 inord(int rad)
{
	int i,cap;
	int q;
	int stack[MAX];

	i = rad;
	q = 0;
	cap = -1;

	while(q == 0)
	{
		while(stang[i] > 0)
		{
			cap++;
			stack[cap] = i;
			i = stang[i];
		}
		vizit(i);
		while(drept[i] == 0 && q == 0)
		{
				if(cap < 0)
					q = 1;
				else
				{
					i = stack[cap];
					vizit(i);
					cap--;
				}
		}
		if(q == 0)
			i = drept[i];
	}
}

void main()
{
	cit_date();
	inord(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
 3 4 2 6 5 7 1 8 9  */

16,902 total views, 1 views today