In-order Traversal of a Tree.
In-order traversal is very commonly used on binary search trees(BST).Tt returns values from the underlying set in order, according to the comparator set up of the binary search tree. Array, Linked List, Queues, Stacks, etc. are linear traversal where have only one logical way to traverse them. Though trees can be traversed in different ways. That Traversals:
In-order:
For In-order traverse need to traverse left, then root, then right.
tree
Following figure In-order traverse 7,2,9.
Algorithm for In-order traverse.
Input tree, root.
Step 1: Traverse left sub tree like call In-order (tree, root. left).
Step 2: visit root node.
Step 3: Traverse right sub tree like call In-order(tree, root. right).
Now, Traverse the following tree by following program.
tree
Traverse : 1,7,5,6,10,2,9,3,8,4.
Recent Articles on Binary Tree in the blog Topic :
- Introduction Of Binary Tree
- Traversals such as
- In-order traversal tree with C implementation
- Post-order traversal tree with C implementation
- Pre-order traversal tree with C implementation
Implementation Process:
1st need to create node struct where data, *left , *right declared;
2nd need to create new node function which take an item and return new node, where firstly need i) memory allocation same as datatype size. If failed to memory allocation show error or assign data into new node, if left or right child no value then put them as NULL.
3rd to add child left and right need two function both take two input one for node pointer another for left or right child assigned.
4th create create_tree() function by create_node ,add_left_child() and right_child() function. This function return root.
5th Now use in_order() recursion function, if left child not null call in_order() recursively for left node. root print , then Again if right child not null call in_order()recursively for right node.
6th main() function receive root data or value will print.
Program:
#include <stdio.h>
typedef struct node Node;
/* A binary tree node has data, pointer to left child and a pointer to right child */
struct node
{
int data;
Node *left;
Node *right;
};
Node *create_node (int item)
{
Node *new_node = (Node *) malloc(sizeof(Node)); /* create storage*/
if(new_node == NULL) { printf(“Error ! Could not create an Error\n”);
exit(1);
}
new_node -> data = item;
new_node -> left= NULL;
new_node ->right =NULL;
return (new_node);
}
void add_left_child( Node *node, Node *child )
{
node->left =child;
}
void add_right_child( Node *nodee, Node *child )
{
nodee->right =child;
}
Node *create_tree()
{
Node *two = create_node(2);
Node *seven=create_node(7);
Node *nine=create_node(9);
add_left_child(two,seven);
add_right_child(two,nine);
Node *one = create_node(1);
Node *six = create_node(6);
add_left_child(seven,one);
add_right_child(seven,six);
Node *five=create_node(5) ;
Node *ten = create_node(10);
add_left_child(six,five);
add_right_child(six,ten);
Node *eight = create_node(8);
add_right_child(nine,eight);
Node *three=create_node(3);
Node *four=create_node(4);
add_left_child(eight,three);
add_right_child(eight,four);
return two;
}
/* print tree nodes according to the in order traversal. */
void in_order(Node *node)
{
if(node->left != NULL)
{
in_order(node->left);
}
printf(“%d\n”,node->data);
if(node->right != NULL)
{
in_order(node->right);
}
}
//struct Node node; int main()
{
/* Given a binary tree, to print its nodes according to the in order traversal. */
Node *root =create_tree();
in_order(root);
printf(“\n”);
return 0;
}
Data Structure more articles
- PostOrder traverse C Program For Pre_Order traversal in a Tree.
- In-order traverse C program In_order Traversal of a Tree.
- Post order traversal
Post-order traverse of a Tree with C program.