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

Алгоритм, 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

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Donate

Здравствуйте, уважаемые пользователи EVILEG !!!

Если сайт вам помог, то поддержите разработку сайта финансово, пожалуйста.

Вы можете сделать это следующими способами:

Спасибо, Евгений Легоцкой

n
16 ноября 2019 г. 1:28
nick

C++ - Тест 001. Первая программа и типы данных

  • Результат:80баллов,
  • Очки рейтинга4
D
15 ноября 2019 г. 10:16
Daulet

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:40баллов,
  • Очки рейтинга-8
ЛП
12 ноября 2019 г. 19:22
Лев Пархимович

C++ - Тест 006. Перечисления

  • Результат:50баллов,
  • Очки рейтинга-4
Последние комментарии
b
9 ноября 2019 г. 19:28
bastonc

спасибо ещё раз. огромное, за уделённое время
b
9 ноября 2019 г. 19:24
bastonc

Спасибо Вам большое. Буду изучать.
9 ноября 2019 г. 16:58
Евгений Легоцкой

Добрый день. По первым двум вопросам вы найдёте ответ в этой статье - PyQt5 - Урок 008. Работа с QTableWidget (Обновление урока 006) Что касается последнего вопроса, то я вам…
9 ноября 2019 г. 13:50
Евгений Легоцкой

Как и обещал, вы можете посмотреть новую статью QML - Урок 037. Кастомизация кнопок в QML (Обновление урока 002) . Там же найдёте ссылку на Git репозиторий. Не забудьте поставить звёз…
b
8 ноября 2019 г. 18:40
bastonc

Приветствую. Подскажите пожалуйста пару моментов. 1. Как сделать столбец не редактируемый, а остальные ячейки остаются редактируемыми 2. Как оталвливать события двойного клика для реда…
Сейчас обсуждают на форуме
s
15 ноября 2019 г. 22:06
sladkoewka

За пример буду очень благодарен, т.к. я новичок и с подобным пока не работал.
15 ноября 2019 г. 18:37
Intruder

Евгений, почитав про эту проблему пришел к выводу, что либо нужно говорить очередь, либо все вернуть из библиотеки (dll в моем случае) в приложение, потому что в приложении все работает просто з…
15 ноября 2019 г. 17:06
Евгений Легоцкой

Ну тогда не знаю )) Я большую часть времени на C++ с Qt работаю, а PyQt5 у меня боком. Так что, чем можем помочь ))
H
15 ноября 2019 г. 16:18
Hyperfish

Да, пробовал, с преобразованием int array[]={1,2,3,4,5,6,7} в jintArray(array). Если так, то программа компилируется без ошибок и предупреждений, но вываливается с ошибкой времени выполнени…
15 ноября 2019 г. 14:48
Евгений Легоцкой

Ну собственно поэтому я и сказал, что бесполезное это занятие.
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB