Representation of Binary Tree
A binary tree can be represented either through an array or a linked list.
Binary Tree Array Representation
A binary tree can be stored sequentially in an array. This type of representation is static as the array of a required size has to be taken before going storing the tree elements into it.
In array representation, the elements are stored level by level, at first, the element at level 0 is stored, and then the elements at level 1, from left to right are stored, and so on. The root node is the first element stored in an array.
Given below is an example of an array representation of a binary tree –
Binary Tree Linked Representation
A linked representation of a binary tree in data structures is as follows –
Each node of a binary tree has three fields – A data field to store information, and two address fields to store the addresses of the possible left and right child. The representation that we have commonly seen in the examples above is the linked representation.
A linked representation is dynamic and therefore enhancement of a tree is possible and no memory is wasted. Here, insertion and deletion operations involve to data movement. The drawback of this representation is that pointer fields are involved in each node in addition to the data fields hence more memory is occupied.
The structure of a node is defined as below –
struct node{
char data;
struct node* lchild;
struct node *rchild;
}
Here, the first field will store the information, the second field will point to the left child of a node and the third field will point to the right child of a node. If the node has no left child then the left address field will have null value. If the node has no right child then the right address field will have a null value stored in it.
Traversal techniques of Binary Trees
Now, we are going to learn about the traversal techniques of Binary Trees in the data structures.
In linear data structures such as arrays, linked lists, queues, stacks, etc. we have only one logical way to traverse the data elements from the first node. Unlike this, trees can be traversed in different ways. A binary tree can be traversed in various ways such as pre-order, post-order, and inorder traversal.
Now, we will learn about each of these traversals one by one –
Pre-order Traversal
The steps for pre-order traversal are –
- Visit the root node
- Traverse the left subtree of the root in preorder
- Traverse the right subtree of the root in preorder
The function for pre-order traversal is given below –
void preorder(struct node * root)
{
if(ptr!=NULL){
printf("%c",root->data);
preorder(root->left);
preorder(root->right);
}
Inorder Traversal
- Traverse the left subtree of the root in inorder
- Visit the root node
- Traverse the right subtree of the root in inorder
The function for the inorder traversal is given below –
void inorder(struct node * root)
{
if(ptr!=NULL){
inorder(root->left);
printf("%c",root->data);
inorder(root->right);
}
{
Postorder Traversal
- Traverse the left subtree of the root in postorder
- Traverse the right subtree of the root in postorder
- Visit the root node
The function for the post-order traversal is given below –
void postorder(struct node * root)
{
if(ptr!=NULL){
postorder(root->left);
postorder(root->right);
printf("%c",root->data);
}
{
Level Order Traversal
This is a special kind of traversal in a binary tree where first, all the nodes at height 1 are processed, then all the nodes at height 2, and this is done till the last level.
The function for level order traversal is given below –
int height(struct node * node) {
if (node == NULL)
return 0;
else {
int lheight = height(node -> left);
int rheight = height(node -> right);
if (lheight > rheight)
return (lheight + 1);
else return (rheight + 1);
}
}
void CurrentLevel(struct node * root, int level) {
if (root == NULL)
return;
if (level == 1)
printf("%d ", root -> data);
else if (level > 1) {
CurrentLevel(root -> left, level - 1);
CurrentLevel(root -> right, level - 1);
}
}
void LevelOrder(struct node * root) {
int h = height(root);
int i;
for (i = 1; i <= h; i++)
CurrentLevel(root, i);
}
So, in this tutorial, we learned about the traversal techniques in binary trees and representation forms of binary trees.
