# Nodes In A Tree Data Structure English Language Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Tree traversal refers to the process of visiting or examining or updating each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes of the tree are visited. This paper presents a new and innovative technique using which traversing in trees as well as in other linear data structure like array, linked list, etc becomes extremely easy and using this technique explanation & understanding of traversing in trees also becomes easy.

Keywords- Tree, Graph, Traversing algorithm, set construct, adjacency matrix

INTRODUCTION

TraversalÂ refers to the process of visiting (examining and/or updating) 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. traversing has been a great challenge for the students and research scholars in the field of computer science. Both are the perfect examples where recursion technique is deeply involved. Compared to linear data structures like linked list and one dimension assay, which have only one state of traversal, tree traversing can be done in various ways. Starting from the root 8 the binary tree there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps are performing an action on the current node, named as visiting the node, traversing to the left child node & then traversing to the right child node. Thus the process is most easily described through recursion.

The following techniques are the conventional methodologies for tree traversing. To traverse a non empty binary tree in preorder the following operations have to be recursively performed at each mode, starting with the root node. It is also known as depth first search.

1. Visit the node

2. Traverse the left sub tree.

3. Traverse the right sub tree.

To traverse a non empty binary tree in in order, perform the following operations recursively at each node. It is also called symmetric traversal.

1. Traverse the left sub tree

2. Visit the node.

3. Traverse the right sub tree.

To traverse a non empty binary tree in post order, perform the following operations recursively at each node. It is also called level order traversing, where we visit every node on a level before going to a lower level.

1. Traverse the left sub tree

2. Traverse the right sub tree.

3. Visit the root.

II. PROPOSED METHODOLOGY

The technique for traversal in case of binary trees are as follows:-

A. Tree

Tree is an ordered set of sub trees T(Xi) where Xi are the nodes of the tree defined by ordering them in almost complete binary tree manner of cardinality n as:

{T(X1), T(X2), T(X3) â€¦â€¦, T ( Xn)}

In almost complete binary tree manner, for a level tree of depth 'd' node X1 is at level 0 and node X2 is at level 1, which is the left most node. On traversing from left to right we reach node Xn of level/depth 'd'.

B. Sub tree

It is the set of three members N, L, R defined as {N, L, R} where

i) node : N - Parent/leaf/root

ii) left child : L - null/leaf/sub tree

iii) right child : R - null/leaf/sub tree

Traversal set: T(N) is an ordered sub tree for the node N according to one of the tree traversal methods. i.e.

(i) Pre order Traversal - {N, L, R}

(ii) Post order Traversal - {L, R, N}

(iii) In order Traversal - {L, N, R}

Result set R: It is an ordered set and its members are the nodes of the tree, after execution of the program members are in required path of traversal.

III. TRAVERSING IN ARRAYS

Traversing is a process of accessing the elements of an array exactly once. To traverse an array, we access the individual array elements in order using its index that varies from the lower bound to upper bound by incrementing the index by 1.

Let Abe a one dimensional array. In order to count the total number of elements of an array with some condition or calculate sum of all elements of an array A or to print the contents of each element of array A, we need to traverse the array A where we access and process the individual elements of array A exactly once so as to perform the desired operation. Processing an array means applying the same operation to each element in the array.

## Algorithm:

Traversing a linear array:

Here LA is a linear array with lower bound LB and upper bound UB. This algorithm traverses LA applying an operation PROCESS to each element of LA.

Step K= LB.

Repeat steps 3 and 4 while K<=UB.

Apply PROCESS to LA[K].

Set K=K+1.

Exit.

Caution: The operation PROCESS in the traversal algorithm may use certain variables which must be initialized before PROCESS is applied to any of the elements in the array. Accordingly, the algorithm may need to be preceded by such an initialization step.

## Coding:

Printing annual profit of array PROFIT for a company XYZ for the years 1950 to 2007.

#include<iostream.h>

#include<conio.h>

#include<iomanip.h>

void main( )

## {

void print1(long [ ] );

long profit [5]={5000,2000,4000,9000,6000};

clrscr( );

print1 (profit);

getch( );

## }

Void print1(long profit[])

## {

Int st_year=1989;

Cout<<"year"<<setw(15)<<"profit"<<endl;

Cout<<"- - - - - - - - - "<<endl;

For(int i=0;i<5;i++)

Cout<<st_year + i<<setw(15)<<profit[i]<<endl;

## }

IV. TRAVERSING IN LINKED LIST

Traversing involves processing each node of the linked list exactly once from the beginning to the end following the chain of references. Let us consider a linked list LIST stored in memory with pointer HEAD pointing to the first node and NULL indicating the end of the list.

While traversing, we need to process each node and for this, we use a pointer variable PTR that keeps track of the current node being processed. In order to process the next node, we need to update this pointer variable so that it points to the next node.

Algorithm:

Traversing a linked list:

Let List be a linked list in memory. This algorithm traverse LIST, applying an operation PROCESS to each element of LIST. The variable PTR points to the node currently being processed.

Set PTR=START.

Repeat steps 3 and 4 while PTR!= NULL.

Apply PROCESS to INFO[PTR].

Set PTR=LINK[PTR}.

Exit.

Caution: The operation PROCESS in algorithm may use certain variables which must be initialized before PROCESS is applied to any of the elements in LIST. Consequently, the algorithm may be preceded by such an initialization step.

Traversing a circular header list

Let list be a circular header list in memory. This algorithm traverses LIST, applying an operation PROCESS to each node of LIST.

Set PTR=LINK[START].

Repeat steps 3 and 4 while PTR!= START:

Apply PROCESS to INFO[PTR].

Set PTR=LINK[PTR].

Exit.

Coding:

Inserting and Traversing the elements of a singly linked lists.

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

struct node

## {

int info;

struct node *next;

## };

typedef struct node NODE;

NODE *start;

void createmptylist(NODE **start)

## {

*start=(NODE *)NULL;

## }

void traversinorder(NODE *start)

## {

while(start != (NODE *) NULL)

## {

printf("%d\n",start->info);

start=start->next;

## }

## }

void insertatbegin(int item)/*insert at beginning of list*/

## {

NODE *ptr;

ptr=(NODE *)malloc(sizeof(NODE));

ptr->info=item;

if(start==(NODE *)NULL)

ptr->next=(NODE *)NULL;

else

ptr->next=start;

start=ptr;

## }

void insert_at_end(int item) /*insert at end of the list*/

## {

NODE *ptr,*loc;

ptr=(NODE *)malloc(sizeof(NODE));

ptr->info=item;

ptr->next=(NODE *)NULL;

if(start==(NODE*)NULL)

start=ptr;

else

## {

loc=start;

while(loc->next!=(NODE *)NULL)

loc=loc->next;

loc->next=ptr;}}

void insert_spe(NODE *start,int item) /*insert at intermediate position*/

## {

NODE *ptr,*loc;

int temp,k;

for(k=0,loc=start;k<temp;k++)

## {

loc=loc->next;

if(loc==NULL)

## {

printf("node in the list at less than one\n");

return;

## }

## }

ptr=(NODE *)malloc(sizeof(NODE));

ptr->info=item;

ptr->next=loc->next;;

loc->next=ptr;

## }

void main()

## {

int choice,item,after;

char ch;

clrscr();

createmptylist(start);

do

## {

printf("1.Insert element at begin \n");

printf("2. insert element at end positon\n");

printf("3. insert specific the position\n");

printf("4.travers the list in order\n");

printf("5. exit\n");

printf("enter your choice\n");

scanf("%d",&choice);

switch(choice)

## {

case 1: printf("Enter the item\n");

scanf("%d",&item);

insertatbegin(item);

break;

case 2: printf("Enter the item\n");

scanf("%d",&item);

insert_at_end(item);

break;

case 3: printf("Enter the item\n");

scanf("%d",&item);

insert_spe(start,item);

break;

case 4: printf("\ntravers the list\n");

traversinorder(start);

break;

case 5: return;

## }

fflush(stdin);

printf("do your want continous\n");

scanf("%c",&ch);

}while((ch='y')||(ch='y'));

getch();

## }

V. TRAVERSING IN BINARY TREES

Traversal is one of the most commonly performed operation on a binary tree. Many other operations(such as insertion, deletion) performed on binary trees often make use of traversal operation.

Traversing is a process in which each node of the tree is processed exactly once in a predetermined sequence. Depending upon the nature of the application, the word process may have different meanings. For example:- when representing arithmetic expression using a tree, processing of a node representing arithmetic operation means executing the operation.

There are two different approaches to process all the nodes systematically: depth first traversal and breadth first traversal. In the depth first traversal, we process all the descendents of a child before processing the next child. However, in breadth first traversal, all the nodes are processed level by level i.e. first nodes at level 0are processed followed by nodes at level 1 and so on. At each level, nodes are processed from left to right.

The depth first traversal can be further classified into three common techniques: preorder traversal, in order traversal and post order traversal. This classification is done depending upon whether the root is processed first before going to left and right sub tree or root is processed after the left but before the right sub tree or root is processed after the left and right sub tree. Once the binary search tree has been created, its elements can be retrieved in-order by recursively traversing the left subtree of the root node, accessing the node itself, then recursively traversing the right subtree of the node, continuing this pattern with each node in the tree as it's recursively accessed. As with all binary trees, one may conduct a pre-order traversal or a post-order traversal, but neither are likely to be useful for binary search trees.

Coding:

def traverse_binary_tree(node, callback):

if node is None:

return

traverse_binary_tree(node.leftChild, callback)

callback(node.value)

traverse_binary_tree(node.rightChild, callback)

PREORDER TRAVERSAL

In the preorder traversal of a binary tree, each node is processed before any of its children i.e the root is processed first followed by the nodes in the sub tree in such a way that the left sub tree is processed before the right sub tree provided it is not empty. Each sub tree is also processed in the similar fashion. It can be remembered as Node-Left-Right(NLR).

During the traversal, it is often necessary to move downwards and subsequently upwards in a tree so that some information needs to be retained. Since in preorder traversal, the root node is processed first, then the left subtree followed by the right sub tree.

Therefore, while left sub tree is handled, the information in right sub tree must be stored somewhere in order to complete the traversal of right side of any sub tree.

Preorder traversal

A binary tree T is in memory. The algorithm doess a preorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the address of nodes.

Set TOP=1, STACK[1]=NULL and PTR=ROOT.

Repeat steps 3 to 5 while PTR!= NULL:

Apply PROCESS to INFO[ptr].

If right[ptr]!=null, then:

Set top=top+1, and stack[top]=right[ptr].

If left[ptr]!=null,then:

Set ptr=left[ptr].

Else:

Set ptr=stack[top] and top=top-1.

Exit.

IN ORDER TRAVERSAL

In the in order traversal of a binary tree, we begin by first processing the left sub tree of the root node followed by the root node itself and then the right sub tree of the root provided sub trees are not empty. Each sub tree is also processed in similar fashion. It can be remembered as Left-Node-Right(LNR).

Inorder traversal

A binary tree is in memory. This algorithm does an inorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addrersses of nodes.

Set TOP=1, STACK[1]=NULL and PTR=ROOT.

Repeat while PTR!=NULL:

Set TOP=TOP+1 and STACK[TOP]=PTR.

Set PTR=LEFT[PTR].

Set PTR=STACK[TOP] and TOP= TOP-1.

Repeat steps 5 to 7 while PTR!=NULL:

Apply PROCESS to INFO[PTR].

If RIGHT[PTR]!=NULL, then:

Set PTR=RIGHT[PTR].

Go to Step 3.

Set PTR=STACK[TOP] and TOP=TOP-1.

Exit.

C. POST ORDER TRAVERSAL

In the post order traversal of a binary tree, we begin by processing the left sub tree of root node followed by right sub tree of the root and finally the root provided each sub tree is non empty. Each sub tree is also processed in similar fashion. It can be remembered as Left- Right-Node.

Postorder traversal

A binary tree T is in memory. This algorithm does a postorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addrersses of nodes.

Set TOP=1, STACK[1]=NULL and PTR=ROOT.

Repeat steps 3 to 5 while PTR!=NULL:

Set TOP=TOP+1 and STACK[TOP]=PTR.

If RIGHT [PTR]!=NULL, then:

Set TOP=TOP+1 and STACK[TOP]=-RIGHT[PTR].

Set PTR=LEFT[PTR].

Set PTR=STACK[TOP] and TOP=TOP-1.

Repeat while PTR>0:

Apply PROCESS to INFO[PTR].

Set PTR=STACK[TOP] and TOP=TOP-1.

If PTR<0, then:

Set PTR=-PTR.

Go to step 2.

Exit.

Coading:

Perform to implement traversing on binary search tree.

#include<iostream.h>

#include<conio.h>

struct node

## {

int data

node *left, *right;

## };

void preorder(node *T)

## {

if(T!=NULL)

## {

cout<<Tïƒ data;

preorder(Tïƒ left);

preorder(Tïƒ right);

## }

## }

void inorder(node *T)

## {

if(T!=NULL)

## {

inorder(Tïƒ left);

cout<<Tïƒ data;

inorder(Tïƒ right);

## }

## }

void postorder(node *T)

## {

if(T!=NULL)

## {

postorder(Tïƒ left);

postorder(Tïƒ right);

cout<<Tïƒ data;

## }

## }

void main( )

## {

clrscr( );

node *p=newnode;

cin>>pïƒ data;

pïƒ left=NULL;

pïƒ right=NULL;

node *q=newnode;

qïƒ data=20;

qïƒ left=NULL;

qïƒ right=NULL;

pïƒ left=q;

node *r=newnode;

rïƒ data =30;

rïƒ left=NULL;

rïƒ right=NULL;

pïƒ right=r;

preorder (p);

cout<<endl;

inorder (p);

cout<<endl;

postorder (p);

cout<<endl;

getch( );

## };

VI. TRAVERSING IN GRAPHS

Traversing is the key operation performed on a graph. Traversing a graph involves visiting all the vertices exactly once.

When a vertex is visited, some action is performed. This action could be as simple as printing the contents of the vertex or it could be some complex action that updates the information stored at the vertex. There are several methods available for traversing a graph systematically. However out of these, two methods are accepted as a standard which are Breadth First Search(BFS) and Depth First Search. Using these traversal, starting from a given vertex, we can visit all the vertices which are reachable from that starting vertex.

A. BREADTH FIRST SEARCH(BFS)

In BFS, after visiting a vertex N, we visit all vertices which are adjacent (in the immediate neighborhood) to vertex N before N visiting any neighbours of neighbours of N. BFS approach is similar to Level Order Traversal of the tree in which entire level of the tree is explored before moving on to the next level. However, unlike tree where the traversal always starts from the root node, a graph traversal can start from any vertex. Let v be the starting vertex of the graph.

The BFS starts by visiting vertex v. After visiting vertex v, all its adjacent vertices says v1, v2â€¦â€¦â€¦â€¦.vm are visited in some defined order. After this, we must visit all the unvisited vertices that are adjacent to v1, v2,â€¦â€¦â€¦..vm. This process continues until all the vertices which are reachable form the starting vertex are visited.

Breadth first search

This algorithm executes a breadth first search on a graph G beginning at a starting node a.

Initialize all nodes to the ready state (STATUS=1).

Put the starting node A in QUEUE and chage its status to the waiting state (STATUS=2).

Repeat steps 4 & 5 until QUEUE is empty:

Remove the front node N of the QUEUE. Process N and change the status of N to the processed state (STATUS=3).

All to the rear of QUEUE all the neighbours of N that are in steady state (STATUS=1), and change their status to the waiting state (STATUS=2).

Exit.

DEPTH FIRST SEARCH(DFS) TRAVERSAL

Another technique for traversing a graph is depth first search (DFS) traversal which is similar to in order traversal of a binary tree.

The basic idea behind DFS is to traverse vertices of the graph as deep as possible before looking at any other adjacent vertices in a graph. Just like BFS traversal, we can also start traversing from any vertex.

Let v be starting vertex of the graph. The DFS traversal starts by first visiting all the vertices along a path which begins at v. The DFS traversal of a graph starts by first pushing the starting vertex onto the stack and changing its STATUS from "not visited" to "waiting".

Depth first search

This algorithm executes a depth first search on a graph G beginning at a starting node A.

Initialize all nodes to the ready state (STATUS=1).

Push the starting node A onto STACK and change its status to the waiting state(STATUS=2).

Repeat steps 4 & 5 until STACK is empty.

Pop the top node N of STACK. Process N and change its status to the processed state (STATUS=3).

Push onto stack all the neighbours of n that are still in the ready state (status=1),and change their status to the waiting state to the waiting state (status=2).

Exit.

VII. WHICH ONE IS BETTER?