Advanced Data Structures: Binary Trees in C

Hello there, fellow coder! Today, we’re going to dive deep into the world of advanced data structures, specifically focusing on binary trees. If you’ve ever wondered how search algorithms can find information so quickly or how databases store and retrieve data efficiently, you’re in the right place. So, let’s get started!

What is a Binary Tree?

A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent. Every node in a binary tree has a left and right reference along with the data element. The node at the top of the hierarchy of a tree is called the root node. The nodes that hold other sub-nodes are the parent nodes.

Types of Binary Trees

There are several types of binary trees, each with its unique properties and uses. Here are a few:

1. Full Binary Tree: A full binary tree is a binary tree type where every node has either 0 or 2 child nodes.
2. Complete Binary Tree: In a complete binary tree, all levels are completely filled except possibly the last level, which is filled from left to right.
3. Perfect Binary Tree: A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.
4. Balanced Binary Tree: A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
5. Degenerate (or pathological) Tree: A degenerate tree is a tree where every internal node has one child. Such trees are performance-wise same as linked list.

Code Example

Let’s look at some code examples of binary trees. Here’s a simple implementation of a binary tree in C:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node* left;
    struct node* right;
};

// New node creation
struct node* newNode(int data) {
    struct node* node = (struct node*)malloc(sizeof(struct node));

    node->data = data;
    node->left = NULL;
    node->right = NULL;

    printf("Created node with data: %d\n", data);  // Print the data of the newly created node

    return(node);
}

void printTree(struct node* root, int space) {
    int i;

    // Base case
    if (root == NULL) return;

    // Increase distance between levels
    space += 10;

    // Process right child first
    printTree(root->right, space);

    // Print current node after space count
    printf("\n");
    for (i = 10; i < space; i++) {
        printf(" ");
    }
    printf("%d\n", root->data);

    // Process left child
    printTree(root->left, space);
}

int main() {
    struct node *root = newNode(1);  
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5); 

    printf("\nStructure of the tree:\n");
    printTree(root, 0);

    return 0;
}

Code Explanation in Brief

In this code, we first define the structure of a node. Each node contains an integer data and pointers to its left and right child nodes. We then create a newNode function that allocates memory for a new node and sets its data and child nodes. In the main function, we create a root node and add child nodes to it.

Code Explanation in Details

In this code, we first define a structure node that has an integer data and two pointers left and right to the left and right child nodes.

The newNode function creates a new node with a given data. It allocates memory for the new node using the malloc function, assigns the data to the data field of the node, and sets the left and right pointers to NULL, indicating that this node has no children yet.

In the main function, we create a new node with data 1 and assign it to the root pointer. We then create two more nodes with data 2 and 3 and assign them to the left and right children of the root. Finally, we create two more nodes with data 4 and 5 and assign them to the left and right children of the node with data 2.

Wrapping up

Binary trees are a fundamental part of computer science and are used in many areas, including search algorithms, sorting algorithms, and database algorithms. Understanding how they work and how to implement them is crucial for any serious programmer.

Frequently Asked Questions (FAQ)

• Introduction to Data Structures in C
• Trees in C
• Advanced Data Structures: Segment Trees in C
• Advanced Data Structures: graphs in C
• Advanced Data Structures: Heaps in C