Древовидная структура данных

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

Связанный список - это цепочка узлов, соединенных через «next» указатели. Дерево похоже на связанный список, но каждый узел может быть связан с несколькими узлами.

Когда мы говорим о дереве, в основном мы имеем в виду двоичное дерево, то есть структуру, которая имеет два дочерних элемента, слева и справа.

Представление двоичного дерева

Узел двоичного дерева представлен структурой, содержащей часть данных и два указателя на другие структуры того же типа.

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

Специальный указатель, называемый ROOT указывает на узел, который является родителем всех других узлов.

Кроме того, узлы, у которых нет дочерних элементов, имеют свои левый и правый указатели, указывающие на NULL .

Базовое двоичное дерево с тремя узлами может быть создано так:

/* 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;

Всего за несколько шагов мы создали двоичное дерево с тремя узлами.

Деревья могут быть намного более глубокими и сложными, чем это. Данные, хранящиеся в каждом узле, могут быть более сложными, и иметь гораздо больше дочерних элементов, нежели два.

Применение деревьев

Деревья и их варианты представляют собой чрезвычайно полезную структуру данных со множеством практических применений.

  • Деревья двоичного поиска (BST) используются для быстрой проверки наличия элемента в наборе.
  • Heap (Множество) - это вид дерева, который используется для сортировки множества элементов.
  • Модифицированная версия дерева под названием Tries используется в современных маршрутизаторах для хранения информации о маршрутизации.
  • Самые популярные базы данных используют B-Trees (B-деревья) и T-Trees (T-деревья), которые являются вариантами древовидной структуры, которую мы изучили выше для хранения своих данных.
  • Компиляторы используют синтаксическое дерево для проверки (подтверждения) синтаксиса каждой написанной вами программы.

Полная программа C для реализации 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);
}

Вывод программы

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.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
D
Aug. 16, 2019, 12:58 p.m.
Damir

C++ - Тест 003. Условия и циклы

  • Result:92points,
  • Rating points8
D
Aug. 16, 2019, 12:46 p.m.
Damir

C++ - Test 005. Structures and Classes

  • Result:75points,
  • Rating points2
u
Aug. 14, 2019, 2:55 p.m.
unrealproro

C++ - Test 005. Structures and Classes

  • Result:83points,
  • Rating points4
Last comments
D
Aug. 17, 2019, 9:04 a.m.
Damir

github ChekableTView Правой групповая смена значения при перетаскивании левой как обычно.
Aug. 16, 2019, 1:03 p.m.
Evgenij Legotskoj

Потому, что в минуте 60 секунд
Aug. 16, 2019, 12:16 p.m.
Dmitrij

а почему делитель 60000, а не 1000?
g
Aug. 14, 2019, 1:27 a.m.
grig_p

Спасибо большое. Получилось
Aug. 13, 2019, 10:43 a.m.
Evgenij Legotskoj

Самая главная проблема в том, что у вас это константные переменные, и инициализируется они один единственный раз при запуске программы. Поэтому делать динамический перевод в таком случае у …
Now discuss on the forum
Aug. 17, 2019, 1:53 p.m.
Ruslan Polupan

Не очень понятен вопрос. База одна или их несколько?
Aug. 15, 2019, 3:19 a.m.
Mihailll

Плюсы и qml отличаются, с++ логичней
Aug. 14, 2019, 8:20 a.m.
Evgenij Legotskoj

Да это не столько баги QML, сколько поведение JavaScript, который используется в нём. Из-за отсутствия строгой типизации получаем некоторые проблемы с преобразованием типов. в итоге, на первый в…
Aug. 14, 2019, 2:33 a.m.
BlinCT

Ошибка найдена) недосмотрел.
Aug. 13, 2019, 3:52 a.m.
Evgenij Legotskoj

Бери остаток от деления #include <QCoreApplication>#include <QTime>#include <QDebug>int main(int argc, char *argv[]){ QCoreApplication a(argc, argv); QTime time…
Looking for a Job?
14,000.00 руб. - 40,000.00 руб.
Разработчик Qt
Annino, Moscow Oblast, Russia
5,000.00 руб. - 15,000.00 руб.
Дизайнер
Moskovskiy, Moscow, Russia
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
Join us
© EVILEG 2015-2019
Recommend hosting TIMEWEB