In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.
This is a complete Tree Traversal program which I wrote as requirement for my Discrete Mathematics subject in college. This program is written in in C/C++.
See the source codes below:
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <ctype.h>
#include <graphics.h>
#include <conio.h>
#include <string.h>
struct list
{
char num[3];
}
node[35];
void pre_order();
void in_order();
void post_order();
void enter_node();
void initialize();
char ch;
int x,X,stack[15],top,ptr;
void main()
{
while(1==1)
{
textattr(15+(0<<4)); clrscr();
window(3,2,78,24); textattr(15+(1<<4)); clrscr();
textattr(14+(1<<4));
gotoxy(25,4); cprintf("???<> TRAVERSAL PROGRAM <>???");
gotoxy(2,23); cprintf("<Enter a letter to choose>");
gotoxy(26,5); printf("Developed by JOEL BADINAS");
gotoxy(20,6); printf("As a requirement for Discrete Mathematics");
textattr(10+(1<<4));
gotoxy(32,12); cprintf("<*> MENU <*>");
textattr(7+(1<<4));
gotoxy(29,13); printf("???????????????????");
gotoxy(29,21); printf("???????????????????");
gotoxy(30,14); cprintf("[ ] - Preorder");
gotoxy(30,16); cprintf("[ ] - Inorder");
gotoxy(30,18); cprintf("[ ] - Postorder");
gotoxy(30,20); cprintf("[ ] - Quit");
textattr(14+(4<<4)+128);
gotoxy(31,14); cprintf(" P ");
gotoxy(31,16); cprintf(" I ");
gotoxy(31,18); cprintf(" O ");
gotoxy(31,20); cprintf(" Q ");
ch=0;
while(ch != 'P' && ch != 'I'&& ch != 'O'&& ch != 'Q')
{
ch=toupper(getch());
}
switch(ch)
{
case 'P': pre_order(); break;
case 'I': in_order(); break;
case 'O': post_order(); break;
case 'Q': exit(0);
default : printf("%c",7); exit(0);/*break;*/
}
}
}
void pre_order() /***********PRE_ORDER***********/
{
window(3,2,78,24); textattr(14+(1<<4)); clrscr();
textattr(10+(1<<4));
gotoxy(14,1); cprintf("?????????????<> PREORDER TRAVERSAL <>?????????????");
initialize(); enter_node();
gotoxy(1,15); cprintf("PREORDER : ");
ptr=1; top=1; stack[top]='\0';
while(ptr!='\0')
{
printf("%s ",node[ptr].num);
if(strcmp(node[ptr*2+1].num,"X")!=0)
{
top++; stack[top]=ptr*2+1;
}
if(strcmp(node[ptr*2].num,"X")!=0)
{
ptr=ptr*2;
}
else
{
ptr=stack[top]; top--;
}
}
getch();
}
void in_order() /**********IN_ORDER**********/
{
window(3,2,78,24); textattr(14+(1<<4)); clrscr();
textattr(10+(1<<4));
gotoxy(15,1); cprintf("?????????????<> INORDER TRAVERSAL <>?????????????");
initialize(); enter_node();
gotoxy(1,16); cprintf("INORDER : ");
ptr=1; top=1; stack[top]='\0';
IN_ORDER:
while(strcmp(node[ptr].num,"X")!=0)
{
top++;
stack[top]=ptr;
ptr=ptr*2;
}
ptr=stack[top]; top--;
while(ptr!='\0')
{
printf("%s ",node[ptr].num);
if(strcmp(node[ptr*2+1].num,"X")!=0)
{
ptr=ptr*2+1;
goto IN_ORDER;
}
ptr=stack[top]; top--;
}
getch();
}
void post_order() /**********POST_ORDER**********/
{
window(3,2,78,24); textattr(14+(1<<4)); clrscr();
textattr(10+(1<<4));
gotoxy(13,1); cprintf("?????????????<> POSTORDER TRAVERSAL <>?????????????");
initialize(); enter_node();
gotoxy(1,17); cprintf("POSTORDER : ");
ptr=1; top=1; stack[top]='\0';
POST_ORDER:
while(strcmp(node[ptr].num,"X")!=0)
{
top++;
stack[top]=ptr;
if(strcmp(node[ptr*2+1].num,"X")!=0)
{
top++;
stack[top]= -1*(ptr*2+1);
}
ptr=ptr*2;
}
ptr=stack[top]; top--;
while(ptr!='\0'&&ptr>0)
{
printf("%s ",node[ptr].num);
ptr=stack[top]; top--;
}
if(ptr<0)
{
ptr=ptr*-1;
goto POST_ORDER;
}
getch();
}
void enter_node()
{
window(3,2,78,24); textattr(7+(1<<4)); /*textattr(7+(1<<4));*/
gotoxy(2,23);
printf("Enter 'X' to indicate that a node has no LEFT/RIGHT child!");
gotoxy(2,5); cprintf("Enter root node : ");
gotoxy(45,5); scanf("%s",&node[1].num);
if(strcmp(node[1].num,"X")!=0)
{
gotoxy(2,6); cprintf("Enter children of %s : ",node[1].num);
gotoxy(35,6);scanf("%s",&node[1*2].num);
gotoxy(55,6);scanf("%s",&node[1*2+1].num);
}
if(strcmp(node[2].num,"X")!=0)
{
gotoxy(2,7); cprintf("Enter children of %s : ",node[2].num);
gotoxy(30,7);scanf("%s",&node[2*2].num);
gotoxy(40,7);scanf("%s",&node[2*2+1].num);
}
if(strcmp(node[3].num,"X")!=0)
{
gotoxy(2,7); cprintf("Enter children of %s : ",node[3].num);
gotoxy(50,7);scanf("%s",&node[3*2].num);
gotoxy(60,7);scanf("%s",&node[3*2+1].num);
}
if(strcmp(node[4].num,"X")!=0)
{
gotoxy(2,8); cprintf("Enter children of %s : ",node[4].num);
gotoxy(27,8);scanf("%s",&node[4*2].num);
gotoxy(33,8);scanf("%s",&node[4*2+1].num);
}
if(strcmp(node[5].num,"X")!=0)
{
gotoxy(2,8); cprintf("Enter children of %s : ",node[5].num);
gotoxy(37,8);scanf("%s",&node[5*2].num);
gotoxy(43,8);scanf("%s",&node[5*2+1].num);
}
if(strcmp(node[6].num,"X")!=0)
{
gotoxy(2,8); cprintf("Enter children of %s : ",node[6].num);
gotoxy(47,8);scanf("%s",&node[6*2].num);
gotoxy(53,8);scanf("%s",&node[6*2+1].num);
}
if(strcmp(node[7].num,"X")!=0)
{
gotoxy(2,8); cprintf("Enter children of %s : ",node[7].num);
gotoxy(57,8);scanf("%s",&node[7*2].num);
gotoxy(63,8);scanf("%s",&node[7*2+1].num);
}
}
void initialize()
{
int x;
for(x=1; x < 36; x++)
{
strcpy(node[x].num,"X");
}
}
Labels: C/C++
You can download, use and modify any source codes posted here in just one condition, that you give credit to this blog.