Please wait a little bit, we are fetching the blogs from the database ....
Please wait a little bit, we are fetching the blogs from the database ....
Summary for the blog ⌨️⌨️ Trees are a type of non linear data structure. it has nodes which contain data and pointer to next node. In this blog we will see about trees and their traversal.
The representation of a tree is as shown below. it has different nodes and they are connected together to form a tree.
the above picture is a binary tree where each node has less than or equal to 2 child. similarly we have n-array tree where a node has n child.
Here is a list of some common terminologies used in trees:
node
: A node is a single element in tree which contains data and the pointer to next nodeschild
: A child is the direct lower nodes corresponding to a node.ancestors
: All the nodes above a node is called ancestors.parent
: Parent is the direct above node of a given node.leaf node
: is the node which dos not have any child .we can create a tree from two methods -
Basic recursion :
#include<iostream>
#include<queue>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int data) {
this->data= data;
this->left=NULL;
this->right=NULL;
}
};
Node* createTree() {
cout << "Enter the data" << endl;
int data;
cin >> data;
if(data == -1) {
return NULL;
}
Node* root = new Node(data);
cout << "Enter the data left of " << data << endl;
root->left = createTree();
cout << "Enter the data right of " << data << endl;
root->right = createTree();
return root;
}
int main() {
Node* root = createTree();
return 0;
}
Level order traversal :
void levelOrderTraversal()
{
cout<<"enter the root data"<<endl;
int data;
cin>>data;
Node* root = new Node(data);
queue<Node*> q;
q.push(root);
while(!q.empty()){
Node* temp = q.front();
q.pop();
cout<<"Enter the left data of "<<temp->data<<endl;
int leftd ;
cin>>leftd;
if(leftd!=-1){
temp->left=new Node(leftd);
q.push(temp->left);
}
cout<<"Enter the right data of "<<temp->data<<endl;
int rightd ;
cin>>rightd;
if(rightd!=-1){
temp->right=new Node(rightd);
q.push(temp->right);
}
}
}
We have looked into various ways of creating a tree. now we will jump into the traversal part of trees. we have mainly 3 ways of traversing a tree, namely -
Now we will see the codes of the above traversals.
void inorderTraversal(Node *root)
{
queue<Node *> q;
q.push(root);
q.push(NULL);
while (!q.empty())
{
Node *temp = q.front();
q.pop();
if (temp == NULL)
{
cout << endl;
if (!q.empty())
{
q.push(NULL);
}
}
else
{
cout << temp->data << " ";
if (temp->left)
{
q.push(temp->left);
}
if (temp->right)
{
q.push(temp->right);
}
}
}
}
void preOrderTraversal(Node *root)
{
if (root == NULL)
{
return;
}
cout << root->data;
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
void postOrderTraversal(Node *root)
{
if (root == NULL)
{
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->data;
}