Traversing Tree in Preorder Sequence Using C++

What is Tree?

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

What is Tree Traversal?

In computer science, tree traversal is a form of graph traversal that refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.

Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

What is Preorder Traversal?

When the root node is visited first, then the left subtree and finally the right subtree then it is called Preorder Traversal. It is also called NLR traversal. NLR sequentially means Node, Left Subtree, Right Subtree. For each node the NLR sequence is followed in preorder traversal.

Steps of Preorder Traversal

1. Access the data part of the current node. (8th line on code)
2. Traverse the left subtree by recursively calling the pre-order function. (9th line on code)
3. Traverse the right subtree by recursively calling the pre-order function. (10th line on code)

Uses of Preorder Traversal

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree. Preorder traversal is the widely used process in compiler design.

Example

In the above tree the preorder (red bubble) sequence is: F, B, A, D, C, E, G, I, H

C++ Code

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

void PrintPreorder(int Nodes[],int start,int end){
    if(start>end)
        return;
    cout<<Nodes[start]<<" ";             //Printing present value
    PrintPreorder(Nodes,start*2+1,end);   //Executing the left subtree
    PrintPreorder(Nodes,start*2+2,end);   //Executing the right subtree
}

int main(){
    int Tree[] = {4, 2, 6, 1, 3, 5, 7};
    int n = sizeof(Tree)/sizeof(int);

    cout<<"The Preorder Traversal is:"<<endl;
    PrintPreorder(Tree,0,n-1);
    return 0;
}

Hope you like the tutorial. Please comment if you are satisfied. Follow the blog for getting update first.