Бинарное дерево поиска

@Andrey15year · Регистрация: 03.01.2020

Студворк — интернет-сервис помощи студентам

Здравствуйте! Сегодня я попытался самостоятельно изучить деревья и начал с бинарного дерева поиска. Нашёл статью с кодом на одном очень хорошем сайте. Очень долго пытался понять, что и зачем тут нужно (даже комментарии к коду мне не очень помогли). В общем, вот код, но компилятор ругается на строчку, которую я выделил. Помогите, пожалуйста, исправить.

#include <iostream>
#include <cstdlib>

using namespace std;

/*-----TREE-----*/
typedef struct tree {
int key;
struct tree *left;
struct tree *right;
struct tree *parent;
} node;

/*-----CREATE-----*/
node *create (node *root, int key) {
node *tmp = malloc (sizeof(node));
tmp -> key = key;
tmp -> parent = NULL;
tmp -> left = tmp -> right = NULL
root = tmp;
return root;
}

/*-----ADD_ELEMENT-----*/
node *add (node *root, int key) {
node *root2 = root, *root3 = NULL;
node *tmp = malloc(sizeof(node));
tmp -> key = key;
while (root2 != NULL) {
root3 = root2;
if (key < root2 -> key) {
root2 = root2 -> left;
} else {
root2 = root2 -> right;
}
}
tmp -> parent = root3;
tmp -> left = tmp -> right = NULL;
if (key < root3 -> key) {
root3 -> left = tmp;
} else {
root3 -> right = tmp;
}
}

/*-----SEARCH-----*/
node *search (node *root, int key) {
if ((root -> key == NULL) || (root -> key == key)) {
return root;
}
if (key < root -> key) {
return search(root -> left, key);
} else {
return search(root -> right, key);
}
}

int main () {

node *tree = new node;
int n;

cin >> n;
// тут я попытался инициализировать дерево, а дальше я не могу понять, что нужно указывать в аргументах, чтобы добавить ещё узлы
create(tree, n);

return 0;
}

@_stanislav · 03.01.2020, 10:14

Сообщение от Andrey15year

node *tmp = malloc (sizeof(node));

C++
1
node *tmp = static_cast<node*>(malloc(sizeof(node) ) );

malloc тип void* возвращает, привидение необходимо.

@Andrey15year · 03.01.2020, 10:26 **[ТС]**

теперь ругается на
root = tmp;

@_stanislav · 03.01.2020, 10:35

Сообщение от Andrey15year

теперь ругается на
root = tmp;

что пишет?

Добавлено через 2 минуты
что функция node *create (node *root, int key) должна делать?

@Andrey15year · 03.01.2020, 10:37 **[ТС]**

Всё, я нашёл ошибку, ";" не поставил XD, но всё равно спасибо)

@_stanislav · 03.01.2020, 10:38

Сообщение от Andrey15year

но всё равно спасибо

все равно пожалуйста.

@Andrey15year · 03.01.2020, 10:40 **[ТС]**

Создаёт корень дерева

@_stanislav · 03.01.2020, 10:41

Сообщение от Andrey15year

Создаёт корень дерева

C++
1
2
3
4
5
6
7
node *create (int key) {
node *tmp = new node;
tmp -> key = key;
tmp -> parent = nullptr;
tmp -> left = tmp -> right = nullptr;
return tmp;
}

@Andrey15year · 03.01.2020, 10:42 **[ТС]**

Сообщение от _stanislav

что функция node *create (node *root, int key) должна делать?

создаёт корень дерева

IGPIGP · 03.01.2020, 10:43

del

@_stanislav · 03.01.2020, 10:46

Сообщение от Andrey15year

создаёт корень дерева

как то не правильно она у тебя создает.

Добавлено через 2 минуты

Сообщение от IGPIGP

а node - имя объекта

имя синонима типа

@Andrey15year · 03.01.2020, 10:47 **[ТС]**

Сообщение от _stanislav

как то не правильно она у тебя создает

Я переписывал код с сайта

@_stanislav · 03.01.2020, 10:48

Сообщение от Andrey15year

Я переписывал код с сайта

сравни с этим:

C++
1
2
3
4
5
6
7
node *create (int key) {
node *tmp = new node;
tmp -> key = key;
tmp -> parent = nullptr;
tmp -> left = tmp -> right = nullptr;
return tmp;
}

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

@Andrey15year · 03.01.2020, 10:53 **[ТС]**

Сообщение от _stanislav

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

Можете ещё посмотреть функцию add?

@_stanislav · 03.01.2020, 11:23

Сообщение от Andrey15year

Можете ещё посмотреть функцию add?

я бы как то так реализовал:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
node *create (node *root, int key)
{
    while (true)
    {
        if (key < root->key)
        {
            if (root->left)
                root = root->left;
            else
            {
                 node *tmp = new node;
                 tmp->key = key;
                 tmp->parent = nullptr;
                 tmp->left = tmp->right = nullptr;
                 root->left = tmp;
 
                return tmp;
            }
        }
        else if(key > root->key)
       {
            if (root->right)
                root = root->right;
            else
            {
                node *tmp = new node;
                 tmp->key = key;
                 tmp->parent = nullptr;
                 tmp->left = tmp->right = nullptr;
 
                 root->right = tmp;
                 return tmp;
            }
        }
        else
            return root;
    }
}

скорее всего есть ошибки.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

Бинарное дерево поиска

Решение

Решение

@Andrey15year 0 / 0 / 0 Регистрация: 03.01.2020 Сообщений: 15

	Бинарное дерево поиска 03.01.2020, 10:07. Показов 4236. Ответов 14 Метки с++ бинарное дерево, С++ для начинающих (Все метки) Здравствуйте! Сегодня я попытался самостоятельно изучить деревья и начал с бинарного дерева поиска. Нашёл статью с кодом на одном очень хорошем сайте. Очень долго пытался понять, что и зачем тут нужно (даже комментарии к коду мне не очень помогли). В общем, вот код, но компилятор ругается на строчку, которую я выделил. Помогите, пожалуйста, исправить. #include <iostream> #include <cstdlib> using namespace std; /-----TREE-----/ typedef struct tree { int key; struct tree left; struct tree right; struct tree parent; } node; /-----CREATE-----/ node create (node root, int key) { node tmp = malloc (sizeof(node));** tmp -> key = key; tmp -> parent = NULL; tmp -> left = tmp -> right = NULL root = tmp; return root; } /-----ADD_ELEMENT-----/ node add (node root, int key) { node root2 = root, root3 = NULL; *node tmp = malloc(sizeof(node));** tmp -> key = key; while (root2 != NULL) { root3 = root2; if (key < root2 -> key) { root2 = root2 -> left; } else { root2 = root2 -> right; } } tmp -> parent = root3; tmp -> left = tmp -> right = NULL; if (key < root3 -> key) { root3 -> left = tmp; } else { root3 -> right = tmp; } } /-----SEARCH-----/ node search (node root, int key) { if ((root -> key == NULL) \|\| (root -> key == key)) { return root; } if (key < root -> key) { return search(root -> left, key); } else { return search(root -> right, key); } } int main () { node *tree = new node; int n; cin >> n; // тут я попытался инициализировать дерево, а дальше я не могу понять, что нужно указывать в аргументах, чтобы добавить ещё узлы create(tree, n); return 0; } 0

@Andrey15year 0 / 0 / 0 Регистрация: 03.01.2020 Сообщений: 15
	03.01.2020, 10:26 [ТС]
	теперь ругается на root = tmp; 0

@Andrey15year 0 / 0 / 0 Регистрация: 03.01.2020 Сообщений: 15
	03.01.2020, 10:37 [ТС]
	Всё, я нашёл ошибку, ";" не поставил XD, но всё равно спасибо) 0

@Andrey15year 0 / 0 / 0 Регистрация: 03.01.2020 Сообщений: 15
	03.01.2020, 10:40 [ТС]
	Создаёт корень дерева 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9007 / 4708 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	03.01.2020, 10:43
	del 0