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

@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;
    }
}

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

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

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

Решение

Решение

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

	Бинарное дерево поиска 03.01.2020, 10:07. Показов 4155. Ответов 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 Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4706 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	03.01.2020, 10:43
	del 0