mafulechka
mafulechkaMay 23, 2019, 12:49 p.m.

Tree data structure

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

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Do you like it? Share on social networks!

Comments

Only authorized users can post comments.
Please, Log in or Sign up
B

C++ - Test 002. Constants

  • Result:16points,
  • Rating points-10
B

C++ - Test 001. The first program and data types

  • Result:46points,
  • Rating points-6
FL

C++ - Test 006. Enumerations

  • Result:80points,
  • Rating points4
Last comments
k
kmssrFeb. 8, 2024, 3:43 p.m.
Qt Linux - Lesson 001. Autorun Qt application under Linux как сделать автозапуск для флэтпака, который не даёт создавать файлы в ~/.config - вот это вопрос ))
Qt WinAPI - Lesson 007. Working with ICMP Ping in Qt Без строки #include <QRegularExpressionValidator> в заголовочном файле не работает валидатор.
EVA
EVADec. 25, 2023, 7:30 a.m.
Boost - static linking in CMake project under Windows Ошибка LNK1104 часто возникает, когда компоновщик не может найти или открыть файл библиотеки. В вашем случае, это файл libboost_locale-vc142-mt-gd-x64-1_74.lib из библиотеки Boost для C+…
J
JonnyJoDec. 25, 2023, 5:38 a.m.
Boost - static linking in CMake project under Windows Сделал всё по-как у вас, но выдаёт ошибку [build] LINK : fatal error LNK1104: не удается открыть файл "libboost_locale-vc142-mt-gd-x64-1_74.lib" Хоть убей, не могу понять в чём дел…
G
GvozdikDec. 18, 2023, 6:01 p.m.
Qt/C++ - Lesson 056. Connecting the Boost library in Qt for MinGW and MSVC compilers Для решения твой проблемы добавь в файл .pro строчку "LIBS += -lws2_32" она решит проблему , лично мне помогло.
Now discuss on the forum
AC
Alexandru CodreanuJan. 19, 2024, 8:57 a.m.
QML Обнулить значения SpinBox Доброго времени суток, не могу разобраться с обнулением значение SpinBox находящего в делегате. import QtQuickimport QtQuick.ControlsWindow { width: 640 height: 480 visible: tr…
BlinCT
BlinCTDec. 27, 2023, 5:57 a.m.
Растягивать Image на парент по высоте Ну и само собою дял включения scrollbar надо чтобы был Flickable. Так что выходит как то так Flickable{ id: root anchors.fill: parent clip: true property url linkFile p…
Дмитрий
ДмитрийJan. 10, 2024, 1:18 a.m.
Qt Creator загружает всю оперативную память Проблема решена. Удалось разобраться с помощью утилиты strace. Запустил ее: strace ./qtcreator Начал выводиться весь лог работы креатора. В один момент он начал считывать фай…
Evgenii Legotckoi
Evgenii LegotckoiDec. 12, 2023, 3:48 a.m.
Побуквенное сравнение двух строк Добрый день. Там случайно не высылается этот сигнал textChanged ещё и при форматировани текста? Если решиать в лоб, то можно просто отключать сигнал/слотовое соединение внутри слота и …

Follow us in social networks