Tree Structures in C: Traversing Binary Trees

In computer science, a tree is an important data structure. In particular, a binary tree is a tree structure where each node has at most two child nodes. Binary trees are widely used in various algorithms and data processing tasks, such as expression parsing and search algorithms.

This article will detail the basic concepts of binary trees and their traversal methods, including pre-order traversal, in-order traversal, and post-order traversal, along with corresponding C language code examples.

1. What is a Binary Tree?

A binary tree consists of the following components:

• Node: Each element is called a node.
• Root Node: A node without a parent is called the root node.
• Leaf Node: A node without child nodes is called a leaf node.
• Depth: The number of edges from the root to a specific node.
• Height: The number of edges from a specific node to the farthest leaf node.

2. Creating a Simple Binary Tree

First, we need to define a data structure that represents a binary tree node. In C, we can use a struct to achieve this:

#include <stdio.h>
#include <stdlib.h>
// Define binary tree node
struct Node {
    int data;               // Data stored in the node
    struct Node* left;     // Pointer to the left child
    struct Node* right;    // Pointer to the right child
};
// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

3. Traversing a Binary Tree

1. Pre-order Traversal

Pre-order traversal follows the following order:

1. Visit the current root node.
2. Traverse the left subtree.
3. Traverse the right subtree.

Below is the implementation code for pre-order traversal:

void preOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);  // Visit the current root node
    preOrder(root->left);        // Traverse the left subtree
    preOrder(root->right);       // Traverse the right subtree
}

2. In-order Traversal

In-order traversal follows the following order:

1. Traverse the left subtree.
2. Visit the current root node.
3. Traverse the right subtree.

Below is the implementation code for in-order traversal:

void inOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);         // Traverse the left subtree
    printf("%d ", root->data);   // Visit the current root node
    inOrder(root->right);        // Traverse the right subtree
}

3. Post-order Traversal

Post-order traversal follows the following order:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the current root node.

Below is the implementation code for post-order traversal:

void postOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);      // Traverse the left subtree
    postOrder(root->right);     // Traverse the right subtree
    printf("%d ", root->data);  // Visit the current root node
}

4. Complete Example Program

Combining all the above content, here is a complete example program that demonstrates how to create a simple binary tree and perform three different types of traversals:

#include <stdio.h>
#include <stdlib.h>
// Define binary tree node structure.
struct Node {
    int data;                  
    struct Node* left;        
    struct Node* right;    
};
// Function to create a new node.
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// Pre-order traversal function.
void preOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}
// In-order traversal function.
void inOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}
// Post-order traversal function.
void postOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}
// Main function.
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Pre-order traversal: ");
    preOrder(root);
    printf("\nIn-order traversal: ");
    inOrder(root);
    printf("\nPost-order traversal: ");
    postOrder(root);
    return 0;
}

5. Conclusion

Through this article, we learned what a binary tree is and how to implement it in C. We also learned three common methods to traverse it: pre-order traversal, in-order traversal, and post-order traversal. This foundational knowledge is crucial for understanding more complex data structures and algorithms, and we hope it helps you advance further in your programming journey.