Tree data structure

Алгоритм, Tree, Дерево

A Linked List is a chain of nodes connected via "next" pointers. A tree is similar to a linked list, but each node can be linked to multiple nodes.

When we talk about a tree, we basically mean a binary tree, that is, a structure that has two children, left and right.

Binary tree representation

A binary tree node is represented by a structure containing a piece of data and two pointers to other structures of the same type.

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

A special pointer called ROOT points to the node that is the parent of all other nodes.

Also, nodes that have no children have their left and right pointers pointing to NULL .

A basic binary tree with three nodes can be created like this:

/* Initialize nodes */
struct node *root;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
 
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
 
/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;
 
/* Connect nodes */
one->left = two;
one->right = three;
two->left = NULL;
two->right = NULL;
three->left = NULL;
three->right = NULL;
 
/* Save address of first node in root */
root = one;

In just a few steps, we have created a binary tree with three nodes.

Trees can be much deeper and more complex than this. The data stored in each node can be more complex, and have many more children than just two.

Applying trees

Trees and their variants are an extremely useful data structure with many practical uses.

• Binary search trees (BST) are used to quickly check if an element is in a set.
• Heap (Set) is a type of tree that is used to sort multiple elements.
• A modified version of the tree called Tries is used in modern routers to store routing information.
• The most popular databases use B-Trees (B-trees) and T-Trees (T-trees), which are variants of the tree structure we learned above to store their data.
• Compilers use a syntax tree to check (validate) the syntax of every program you write.

Complete C program to implement Tree

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
 
    return newNode;
}
 
struct node* insertLeft(struct node *root, int value) {
    root->left = createNode(value);
    return root->left;
} 
 
 
struct node* insertRight(struct node *root, int value){
    root->right = createNode(value);
    return root->right;
}
 
int main(){
    struct node *root = createNode(1);
    insertLeft(root, 2);
    insertRight(root, 3);
 
    printf("The elements of tree are %d %d %d", root->data, root->left->data, root->right->data);
}

Program output

1 2 3