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

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

Комментарии

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

Внесите вклад в развитие сообщества EVILEG.

Узнайте, как стать автором сайта.

Изучить
Donate

Добрый день, Дорогие Пользователи !!!

Я Евгений Легоцкой, разработчик EVILEG. И это мой хобби-проект, который помогает учиться программированию другим программистам и разработчикам

Если сайт помог вам, и вы хотите также поддержать развитие сайта, то вы можете сделать пожертвование следующими способами

PayPalYandex.Money
Timeweb

Позвольте мне порекомендовать вам отличный хостинг, на котором расположен EVILEG.

В течение многих лет Timeweb доказывает свою стабильность.

Для проектов на Django рекомендую VDS хостинг

Посмотреть Хостинг Timeweb
g
29 мая 2020 г. 14:32
glushchenkoin

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

  • Результат:40баллов,
  • Очки рейтинга-8
АС
26 мая 2020 г. 11:29
Артём Сун-Дун-Чан

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

  • Результат:50баллов,
  • Очки рейтинга-4
МН
25 мая 2020 г. 11:33
Митя Нагибин

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

  • Результат:50баллов,
  • Очки рейтинга-4
Последние комментарии
29 мая 2020 г. 13:00
Евгений Легоцкой

Django - Урок 023. Like Dislike система с помощью GenericForeignKey

Думал так, но похоже что нет. {{ post.votes.likes.user.username }} Это же QuerySet будет, а не отдельный единственный объект {% for vote in post.votes %} {{ vote.user.username …
29 мая 2020 г. 11:43
Владислав Меленчук

Django - Урок 023. Like Dislike система с помощью GenericForeignKey

А как получить имя пользователя, который поставил лайк? Думал так, но похоже что нет. {{ post.votes.likes.user.username }}
29 мая 2020 г. 6:30
Евгений Легоцкой

Qt/C++ - Урок 039. Как закрасить строку в QSqlTableModel по значению в столбце

У меня работает. Исправлял в проекте, который приложен к статье. А что происходит в вашем коде, с учётом места вызова этого кода, я знать не могу ;) Дебажьте и добавляйте условия, кото…
МА
29 мая 2020 г. 6:27
Михаил А

Qt/C++ - Урок 039. Как закрасить строку в QSqlTableModel по значению в столбце

QModelIndexList rowIndexes = ui->tableView->selectionModel()->selectedRows(); model->removeRows(rowIndexes.first().row(), rowIndexes.size()); model-&…
29 мая 2020 г. 6:14
Евгений Легоцкой

Django - Урок 036. Как добавить аутентификацию через социальные сети. ВКонтакте

Неправильно прописали URL, на который возвращается ответ от OAuth ВКонтакте. Настраивайте ваше приложение в консоли разработчика ВКонтакте
Сейчас обсуждают на форуме
ДК
29 мая 2020 г. 13:27
Джон Кофи

QMap<> какой ключ лучше

это ясно. Вопрос в том, как быстро мапа будет отрабатывать, если ключом будет QModelIndex. Какой параметр индекса возьмет за ключ. И вот насколько это будет медленнее или быстрее, чем QString пр…
ДК
29 мая 2020 г. 11:10
Джон Кофи

QModelIndex становится не действительным, но валидный

Привет. Есть проблема с индексом и для меня это чистая магия: Сначала, что делаю: на вьюхе есть редактируемые ячейки. Пользователь редактирует одну, потом внезапно решает не сохраниться и ш…
29 мая 2020 г. 7:52
Vladimir Sergeevich

Масштабирование двумя пальцами на мобильных платформах

Я планировал описать этот момент на блоге, но никак руки не доходят (уже год). Летом дойдут. Тем не менее, у меня в репозитории лежит рабочий код игрушки "пазлы", где есть все это. …
29 мая 2020 г. 6:51
Евгений Легоцкой

Графическое ускорение

Зависит от платформы и поддерживаемых технологий. В QML в первую очередь используется OpenGL и отрисовка производится средствами GPU. Но может переключаться на использование CPU и прог…
ИП
29 мая 2020 г. 1:55
Игорь Порошин

QTablwView + QSqlQueryModel скрыть пустой столбец

Да, понятно. В данном случае лучше использовать серверную процедуру (если такие поддерживаются), в которой будет проверяться наличие всех пустых строк у нужного столбца и вызываться соответ…
О нас
Услуги
© EVILEG 2015-2020
Рекомендует хостинг TIMEWEB