There are 2 types of data structures. 1. Linear and 2.Non linear data structures. Arrays, Stack, Queues and linked lists. Trees belong to non linear data structures. Trees are a type of data structure where a node that contains one or more data values also have an address value to the next node. Trees are really important as they make searching for data easy, efficient and fast when many data values are present. There are many types of trees Binary tree, Binary search tree, AVL tree, Red-Black Tree, B-Tree, Heap, Prefix Tree, Segment Tree, Suffix tree and N-ary Tree. Here are some terms that need to be known before going any deeper into Trees.
Root node-The initial or first node it is also called as the parent node.
Child node(non leaf node)- It is the next node after the parent node.
Leaf node(external node)- It is the last node which do not have any child node.
Degree of a tree- It is maximum number of children a node can have in that specific tree.
Sibling node- Is the nodes with the same parent.
Degree of node-Number of children a node has.
Height of a node- No of edges in the longest path from that node to a leaf.
Level of node- Number of edges to reach from the parent node to the leaf node.
Edges- The number of straight line in a tree.
Binary tree
Binary tree is a tree where a degree of the tree is two. The maximum number of nodes possible is 2^i. Example- at height 3 it is 2^3=8.
Q1. Explanation- In this program the left child and the right child values are taken. When the left child nodes data is taken it asks for the child's left child node up to the leaf node is reached where the values of the left and right child node value is zero. Then again it moves one level up and repeats the process of asking the value for the right child node values. Here function recursion is used to get the value of the binary tree. When the leaf node is reached the user can enter -1 and NULL will be entered into the left and right side of the leaf node.
#include<stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *temp;
struct node *newnode;
struct node *create(){//It gives pointer to node
struct node *newnode;
int x;
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter value and -1 for no node:");
scanf("%d",&x);
if(x==-1){
return 0;
}
newnode->data=x;
printf("Enter left child of %d",x);
newnode->left=create();//Keeps on repeating until all the left child,
//right child of each node is created
printf("Enter right child of %d:",&x);
newnode->right=create();
return newnode;
}
int main(){
struct node *root;
root=0;
root=create();
return 0;
}
Array Representation of Binary Tree
When a binary tree is represented in the normal format it is really hard to know which is the parent node and which is the child node.
Here is a way to find child-
Case 1- If a node is at i'th index, left child would be at [(2*i)+1], right child would be at [(2*i)+2]., to find the parent (i-1)/2.
Case 2-left child (2*i), right child at [(2*i)+1], its parent will be at [i/2]
Traversing Binary tree
Inorder-left root right
Preorder-Root left right
Postorder-Left right root
Inorder would be- B D A G E C H F I
Prints the left side of the node, then the node data and the right of the node.
void inorder(struct node *root) {
if(root != NULL){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}
Preorder would be- A B D C E G F H I
Prints the node data, then the left side of the node and then the right side of the node.
void preorder(struct node *root){
if(root != NULL){
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}
Postorder would be- D B G E H I F C
Prints the left side of the node, then the right side of the node and then it prints the node data.
void postorder(struct node *root){
if(root != NULL){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}
Here is the whole code which accepts data and prints it in the form of inorder, preorder and postorder.
#include<stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *temp;
struct node *newnode;
struct node *create(){//It gives pointer to node
struct node *newnode;
int x;
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter value and 00 for no node:");
scanf("%d",&x);
if(x==00){
return 0;
}
newnode->data=x;
printf("Enter left child of %d,",x);
newnode->left=create();//Keeps on repeating until all the left child,
//right child of each node is created
printf("Enter right child of %d,",x);
newnode->right=create();
return newnode;
}
void inorder(struct node *root) {
if(root != NULL){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}
void preorder(struct node *root){
if(root != NULL){
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct node *root){
if(root != NULL){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}
int main(){
struct node *root=NULL;
root=0;
root=create();
inorder(root);
printf("\t");
preorder(root);
printf("\t");
postorder(root);
return 0;
}
Construction of a binary tree from Preorder or Postorder and Inorder Traversal
In this any 2 of the preorder, Inorder or postorder is given. Using the given data you must draw the binary tree.
Eg-Preorder- 1 2 4 8 9 10 11 5 3 6 7 Inorder- 8 4 10 9 11 2 5 1 6 3 7
In this using preorder we get to know that 1 is the root node, 2 and 3 are the children of the preorder. But we can figure out the children of 3 is 6 and 7 as inorder prints the left, root and right using the data given in the inorder list.
The tree would look like this
If only preorder and postorder is given without inorder the order of the tree could be wrong. Because the root node is in the extriem's. And it would be hard to know the order because the parent element does not separatethe child elements.
Insertion of elements in a Binary tree
To insert an element we have to give the address of the new element into the leaf node. To remove we need to delete the address of the leaf node from the parent node and then free the space occupied by the child node.
Hope you learnt something new after reading this blog. I will be making more blogs about different types of trees and their code.
Happy Coding…