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

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

Виртуальный хостинг со скидкой 10 процентов
Виртуальный хостинг со скидкой 10 процентов
EVILEG предлагает надёжный хостинг со скидкой 10% на виртуальный хостинг и 5% на VPS
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
TT
13 июня 2019 г. 19:01
Taimoor Tanweer

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

  • Результат:66баллов,
  • Очки рейтинга-1
TT
13 июня 2019 г. 18:51
Taimoor Tanweer

C++ - Тест 002. Константы

  • Результат:75баллов,
  • Очки рейтинга2
ВМ
13 июня 2019 г. 12:30
Ваня Мороз

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

  • Результат:100баллов,
  • Очки рейтинга10
Последние комментарии
i
17 июня 2019 г. 6:10
ingenfly

Только по осям xAxis2, уAxis2 значения начинаются с 0. Почему-то xAxis2 и xAxis не синхронизированы по данным. Ну и QCustomPlot последний.
16 июня 2019 г. 20:21
Евгений Легоцкой

Добрый день. Ну точно также добавляете ту же самую информацию на ось xAxis2, только добавляете другое форматирование customPlot->xAxis2->setDateTimeFormat("hh:mm"); если я ...
EF
14 июня 2019 г. 13:56
Egor Fomin

Спасибо за ваш ответ, у меня получилось реализовать это. Тем не менее появилась другая проблема, поэтому опять надеюсь на вашу помощь. Скажем, я уже выставил точки и они соеденены. Когда я нач...
d
13 июня 2019 г. 14:47
damix

Можно классу, который описывает точку, добавить сигнал, который подавать (emit), когда точка перемещается (переопределить mouseMoveEvent или mouseReleaseEvent). Так вот эти сигналы у каждой из...
i
13 июня 2019 г. 14:09
ingenfly

Здравствайте! Подскажите, пожалуйста: customPlot->xAxis2->setTickLabels(true); //Здесь включается отображение данных на оси xAxis2. а можно как-то продублировать информацию cus...
Сейчас обсуждают на форуме
I
19 июня 2019 г. 13:41
Intruder

Всем добрый день. При разборе XML файла наткнулся на тег вот такого плана: <TagName attribute1="value1" attribute2="value2" /> При попытке проверить на наличие такого элеме...
19 июня 2019 г. 12:55
Михаиллл

Скажите пожалуйста, как его в таком случае перемещать и удалять?
18 июня 2019 г. 19:50
Дмитрий

Большое спасибо! SDK заработал.К сожалению удалось продвинутся только на один шаг. При сборке чистого проекта NDK выдаёт следующие ошибки C:\Android\ndk-bundle/toolchains/arm-linux-andr...
18 июня 2019 г. 16:59
Михаиллл

Добрый день.В этом учебнике представлен код INSTALLED_APPS = ( ... 'rest_framework', 'snippets.apps.SnippetsConfig',) На строчке 'snippets.apps.SnippetsConf...
18 июня 2019 г. 14:24
Михаиллл

Спасибо, работает.Послушаю вашего совета.
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

EVILEG
О нас
Услуги
Присоединяйтесь к нам
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB