1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include <stdio.h>#include <stdlib.h>// Define the structure of a binary tree nodestruct Node { int data; struct Node* left; struct Node* right;};// Function to create a new nodestruct Node* createNode(int value) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode;}// Function for inorder traversalvoid inorderTraversal(struct Node* root) { if (root == NULL) { return; } // Recursively traverse the left subtree inorderTraversal(root->left); // Visit the root node printf("%d ", root->data); // Recursively traverse the right subtree inorderTraversal(root->right);}int main() { // Creating nodes of the binary tree struct Node* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); printf("Inorder traversal of the binary tree is: "); inorderTraversal(root); printf("\n"); return 0;} |
Explanation of the Code:
- Structure Definition:
- We define a structure
Nodeto represent a node of the binary tree. - Each node contains three elements:
data: Holds the value of the node.left: Pointer to the left child.right: Pointer to the right child.
- We define a structure
- createNode() Function:
- This function allocates memory for a new node, sets the
datafield, and initializes the left and right pointers toNULL. - It returns a pointer to the newly created node.
- This function allocates memory for a new node, sets the
- inorderTraversal() Function:
- This function takes the root node of a binary tree as input.
- It uses recursion to traverse the tree in the following order:
- First, it calls
inorderTraversal()for the left subtree. - Then, it prints the
dataof the current node. - Finally, it calls
inorderTraversal()for the right subtree.
- First, it calls
- If the
rootisNULL(base condition), it simply returns, ending that branch of recursion.
- main() Function:
- This function serves as the entry point of the program.
- We create a sample binary tree with 5 nodes.
- The tree looks like this:
1
/ \
2 3
/ \
4 5
Output:
When the program is run, the output will be:
Inorder traversal of the binary tree is: 4 2 5 1 3
Explanation of the Output:
For the given binary tree:
- Start at the root (1):
- Traverse the left subtree of
1(which is2).
- Traverse the left subtree of
- At node 2:
- Traverse the left subtree of
2(which is4). 4is a leaf node (no children), so we print4.
- Traverse the left subtree of
- Back to node 2:
- After visiting
4, we print2. - Then, we traverse the right subtree of
2(which is5).
- After visiting
- At node 5:
5is a leaf node, so we print5.
- Back to the root (1):
- After finishing the left subtree, we print
1. - Then, traverse the right subtree of
1(which is3).
- After finishing the left subtree, we print
- At node 3:
3is a leaf node, so we print3.
Thus, the output of the inorder traversal is 4 2 5 1 3.
