Binary Trees in C: A Complete Beginner's Guide

Informatec Digital » Algorithms » Binary Trees in C: A Complete Beginner's Guide

Welcome to this comprehensive guide on binary trees in C. In this article, we will explore the basics of binary trees and how to implement them in the C programming language. If you are a beginner in programming or just want to improve your C skills, this guide is for you.

Binary trees are fundamental data structures in computer science and are used in a wide range of applications. Understanding how they work and how to implement them will help you solve complex problems more efficiently and elegantly.

Throughout this article, we'll explore the fundamentals of binary trees, including their structure, node insertion and deletion, traversal, and element search. We'll also provide practical examples in the C programming language so you can see how these concepts are applied in practice.

So let's start!

What are binary trees?

Binary trees are hierarchical data structures composed of interconnected nodes. Each node can have up to two child nodes: one on the left and one on the right. This two-branch structure is what distinguishes binary trees from other data structures.

In a binary tree, the first node is called the root node. Child nodes are called child nodes, and nodes without children are called leaf nodes. Nodes at the same level are called sibling nodes.

Benefits of Binary Trees

Binary trees offer several advantages in terms of efficient data storage and searching. Some of the key benefits include:

1. efficient searchBinary trees allow for faster lookup of elements at runtime than other data structures such as linked lists. This is due to the hierarchical structure of the tree and its ability to quickly partition the data set.
2. Flexible insertion and removalBinary trees are highly adaptable to node insertion and deletion operations. Unlike static data structures such as arrays, binary trees can grow and change their structure dynamically.
3. Representation of hierarchical relationships: Binary trees are especially useful for representing hierarchical relationships between elements. For example, in a file directory structure, each directory can be represented as a node in the tree, with subdirectories and files as its child nodes.

Structure of a binary tree

Before we dive into the implementation of binary trees in C, it is important to understand their basic structure. Each node in a binary tree contains a value and references to its left and right child nodes, if any.

The following table shows the structure of a node in a binary tree:

Binary node
Price
Left node
Right node

Each node can store any type of data, such as integers, characters, or more complex structures. The root node is the starting point of the tree, and from there we can access all the other nodes.

Implementing binary trees in C

Now that we have a basic understanding of binary trees, it's time to implement them in the C programming language . Next, we'll see how to declare and use a binary tree structure in C.

Declaring the binary tree structure

In C, we can declare the structure of a binary tree using a structure and pointers. Here is the basic declaration of the structure:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

In this structure, valor represents the value stored in the node, and izquierdo y derecho are pointers to the left and right child nodes, respectively.

Creating a new node

To create a new node in the binary tree, we need to allocate memory for the node and set its values. Here is a C function that creates a new node:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

The function malloc is used to allocate dynamic memory to the node. Then we set the node values ​​and return the created node.

Inserting nodes

Node insertion is a fundamental process in binary trees. It allows adding new elements to the tree at the correct position based on the value of the node. Below is a C function to insert a node into a binary tree:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

This function receives a pointer to the root of the tree and the value of the node to insert. If root is null, it means that the tree is empty and we create a new node at the root. Otherwise, we compare the value of the node with the value of the root and decide whether we should insert the node to the left or right.

Deleting nodes

Deleting nodes in a binary tree can be a bit more complex. It depends on several cases, such as whether the node to be deleted has children or not. Below is a C function to delete a node in a binary tree:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

In this function, we check if the node value is less than, greater than, or equal to the current root value. Depending on the case, we perform the following actions:

• If the value is smaller, we go to the left of the tree.
• If the value is greater, we go to the right of the tree.
• If the value is equal, we find the node's closest successor (the smallest node in the right subtree) and replace it with the current node. Then, we remove the successor from the right subtree.

Traversals in binary trees

Traversals are operations that allow us to visit all nodes of a binary tree in a certain order. There are three common types of traversals:

In-order traversal : Visits the left subtree first, then the current node, and finally the right subtree. Here is a C function that performs an in-order traversal of a binary tree:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Pre-order traversal : Visits the current node first, then the left subtree, and finally the right subtree. Here is a C function that performs a pre-order traversal of a binary tree:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Post-order traversal : Visits the left subtree first, then the right subtree, and finally the current node. Here is a C function that performs a post-order traversal of a binary tree:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Search for elements

Searching for elements in a binary tree allows us to quickly find a specific value within the data structure. Here is a C function to search for an element in a binary tree:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

This function performs a recursive search in the binary tree. If the value of the current node is equal to the searched value, the node is returned. Otherwise, the left or right subtree is searched based on the value and the process is repeated until the value is found or a null node is reached.

Examples of implementing binary trees in C

Now that we have covered the basics of binary trees and how to implement them in C, let's look at some practical examples.

Example 1: Creating a binary tree

Suppose we want to create a binary tree with the following values: 10, 5, 15, 3, 7, 13, 18. Here is how we can do it in C:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

In this example, we create a pointer to the root of the tree and then use the function insertarNodo to add the values ​​to the tree.

Example 2: In-order traversal of the binary tree

To print the values ​​of the binary tree in order, we can call the function inOrden As follows:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

This example will print the values ​​in the tree in ascending order.

FAQ

1. What is the difference between a binary tree and a binary search tree?

A binary search tree (BST) is a special type of binary tree in which elements are arranged so that smaller values ​​are on the left and larger values ​​are on the right. This allows for more efficient searching of elements compared to a regular binary tree.

2. Can I have nodes with duplicate values ​​in a binary tree?

Yes, it is possible to have nodes with duplicate values ​​in a binary tree. However, depending on the implementation and the specific rules of the binary tree, there may be different ways to deal with duplicate nodes. Some implementations may allow duplicates and store them in any order, while others may require that duplicate values ​​be handled specially or discarded.

3. How can I remove a specific node from a binary tree?

To remove a specific node from a binary tree, you need to follow these steps:

1. Find the node you want to delete using a tree search.
2. Consider the different cases of elimination:
   • If the node has no children, you can simply delete it and free its memory.
   • If the node has only one child, you can replace the node with its child.
   • If the node has two children, you must find the nearest successor (the smallest node in the right subtree) and replace the value of the node to be deleted with the value of the successor. Then, remove the successor from the tree.
3. Adjusts links and pointers as needed to maintain the correct tree structure.

4. What is a full binary tree?

A complete binary tree is a special type of binary tree in which all levels, except possibly the last, are completely filled, and the nodes in the last level are located as far to the left as possible. This means that all nodes have two children, except possibly the nodes in the last level, which may have one or no children.

5. What is the height of a binary tree?

The height of a binary tree is the length of the longest path from the root to a leaf. In other words, it is the maximum number of edges between the root and any leaf in the tree. Height is measured in terms of the number of levels, so a tree with only one node has a height of 0, and an empty tree has no height.

6. When should I use a binary tree in my programs?

Binary trees are useful in a variety of situations. Some common cases where you might use binary trees include:

• Efficient element lookup: If you need to quickly look up elements in a data structure, a binary tree can provide efficient access to the data.
• Representing hierarchical relationships: Binary trees are ideal for representing hierarchical relationships, such as the directory structure in a File System.
• Data Sorting: You can use binary search trees to efficiently sort data and perform searches, insertions, and deletions in logarithmic time.

Remember to evaluate your requirements and consider the complexity of operations on binary trees before deciding to use them in your programs.

Conclusion

In this comprehensive guide, we have explored the fundamental concepts of binary trees in C. We have learned about their structure, how to insert and remove nodes, perform traversals, and search for elements in a binary tree.

We hope this guide has given you a solid understanding of binary trees and how to implement them in C. Binary trees are versatile and powerful data structures that can help you solve a wide range of problems in programming.

Remember to practice and experiment with the provided examples to strengthen your understanding of binary trees in C. Good luck on your software learning and development journey!