0 / 0 / 0
Регистрация: 05.05.2020
Сообщений: 224
1

Добавление узла в бинарное дерево с++

08.06.2020, 13:05. Показов 421. Ответов 1

Не понимаю чего я не понимаю...
Функция добавления узла в бинарное дерево работает неправильно. Сделал так же, как в нескольких источниках, но проблема в том, что у меня возвращается элемент, который создаётся, и я приравниваю его к tree. Таким образом у меня отсекается всё верхнее дерево. Почему у других работает, а у меня нет?

main.cpp

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <Windows.h>
#include "bstree.h"
#include "hashtab.h"
#define HASHTAB_MUL 31
#define HASHTAB_SIZE 100
using namespace std;
 
struct bstree {
    std::string key;
    int value;
 
    struct bstree* left, * right;
};
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
        struct bstree* tree = NULL;
        menu(tree);
    system("pause");
}
bstree.h

C++
1
2
3
4
5
6
7
#pragma once
void menu(struct bstree* tree);
struct bstree* bstree_create(const std::string &key, int value);
struct bstree* bstree_add(struct bstree *tree, const std::string &key, int value);
struct bstree* bstree_lookup(struct bstree* tree, const std::string &key);
struct bstree* bstree_min(struct bstree* tree);
struct bstree* bstree_max(struct bstree* tree);
bstree.cpp

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <chrono>
#include "bstree.h"
using namespace std;
 
struct bstree {
    std::string key;
    int value;
 
    struct bstree *left, *right;
};
 
struct bstree* bstree_create(const std::string &key, int value)
{
    struct bstree* node = new bstree;
    if (node != NULL) {
        node -> key = key;
        node -> value = value;
        node -> left = NULL;
        node -> right = NULL;
    }
    return node;
}
 
struct bstree* bstree_add(struct bstree *tree, const std::string &key, int value)
{
    if (tree == NULL) {
        tree = bstree_create(key, value);
        return tree;
    }
 
    else if (key < tree->key)
    {
        tree->left = bstree_add(tree->left, key, value);
    }
    else if (key > tree->key)
    {
        tree->right = bstree_add(tree->right, key, value);
    }
    else if (key == tree->key)
        return tree;
}
 
struct bstree* bstree_lookup(struct bstree* tree, const std::string &key)
{
    while (tree != NULL) {
        if (key == tree -> key) {
            return tree;
        }
        else if (key < tree -> key) {
            tree = tree -> left;
        }
        else {
            tree = tree -> right;
        }
    }
    return tree;
}
 
struct bstree* bstree_min(struct bstree* tree)
{
    if (tree == NULL)
        return NULL;
    while (tree -> left != NULL)
        tree = tree -> left;
    return tree;
}
 
struct bstree* bstree_max(struct bstree* tree)
{
    if (tree == NULL)
        return NULL;
    while (tree -> right != NULL)
        tree = tree -> right;
    return tree;
}
 
void menu(struct bstree* tree)
{
    int answer, value;
    std::string key;
    for (;;) {
        cout << "Выберите операцию:\n";
        cout << "1)Добавление элемента дерева\n";
        cout << "2)Поиск элемента дерева по ключу\n";
        cout << "3)Поиск минимума дерева\n";
        cout << "4)Поиск максимума дерева\n";
        cout << "5)Выход\n";
        cin >> answer;
        switch (answer) {
        case 1:
        {
            ifstream file1("File1.txt");
            ofstream file2("File2.txt", ios::trunc);
            for (unsigned long i = 1; i < 10001; i++) {
                file2 << i << " ";
            }
            file2.close();
            ifstream file3("File2.txt");
            chrono::steady_clock::time_point begin = chrono::steady_clock::now();
            for (unsigned long i = 0; i < 1000; i++) {
                file1 >> key;
                file3 >> value;
                tree = bstree_add(tree, key, value);
            }
            chrono::steady_clock::time_point end = chrono::steady_clock::now();
            __int64 microsecondsDuratin = chrono::duration_cast<chrono::microseconds> (end - begin).count();
            cout << "\nВремя выполнения алгоритма: " << microsecondsDuratin << " микросекунд\n\n";
        }
        break;
        case 2:
        {
            chrono::steady_clock::time_point begin = chrono::steady_clock::now();
            cout << "Введите ключ для поиска элемента дерева:\n";
            cin >> key;
            auto* p = bstree_lookup(tree, key);
            if (p != NULL) {
                cout << "Элемент:\n";
                cout << p->key << endl;
                cout << p->value << endl;
            }
            else
                cout << "Элемент не найден\n";
            chrono::steady_clock::time_point end = chrono::steady_clock::now();
            __int64 microsecondsDuratin = chrono::duration_cast<chrono::microseconds> (end - begin).count();
            cout << "\nВремя выполнения алгоритма: " << microsecondsDuratin << " микросекунд\n\n";
        }
        break;
        case 3:
            tree = bstree_min(tree);
            if (tree != NULL) {
                cout << "Элемент:\n";
                cout << tree->key << endl;
                cout << tree->value << endl;
            }
            else
                cout << "Дерева нет\n";
            break;
        case 4:
            tree = bstree_max(tree);
            if (tree != NULL) {
                cout << "Элемент:\n";
                cout << tree->key << endl;
                cout << tree->value << endl;
            }
            else
                cout << "Дерева нет\n";
            break;
        case 5:
            return;
            break;
        }
    }
}
Добавлено через 1 час 19 минут
У меня оказались неверны функции нахождения минимума и максимума. Запутал сам себя
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.06.2020, 13:05
Ответы с готовыми решениями:

Бинарное дерево из слов и удаление узла
Ребят нужно создать дерево где пользователь вводит слова, они записываются в дерево, а потом вводит...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при...

Добавление элемента в бинарное дерево
Добрый вечер, помогите написать метод добавления в бинарное дерево. Я написал вот такой код: class...

Добавление элементов бинарное дерево
Всем добрый день, не выручит кто нибудь алгоритмом который заполняет двоичное дерево поиска

1
6571 / 4556 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
08.06.2020, 14:19 2
Цитата Сообщение от KaffLime Посмотреть сообщение
Таким образом у меня отсекается всё верхнее дерево. Почему у других работает, а у меня нет?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct bstree* bstree_add(struct bstree *tree, const std::string &key, int value)
{
    if (tree == NULL) {
        tree = bstree_create(key, value);
        return tree;
    }
 
    else if (key < tree->key)
    {
        tree->left = bstree_add(tree->left, key, value);
    }
    else if (key > tree->key)
    {
        tree->right = bstree_add(tree->right, key, value);
    }
    ////////else if (key == tree->key)
        
return tree;
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.06.2020, 14:19
Помогаю со студенческими работами здесь

Бинарное дерево подклассов основного класса-узла. Доступ к подклассам по указателю - объекту класса-родителя
Короче, необходимо сделать бинарное дерево, решающее арифметическое выражение, предварительно туда...

Добавление элемента в обычное бинарное дерево
Доброго времени суток, форумчане! Начинаю реализовывать бинарное дерево (обычное, НЕ поиска) и...

Бинарное дерево поиска (удаление, добавление элемента)
Задачи В Бинарном дереве поиска 1)введено с клавиатуры значение, если существует узел с таким...

Шаблон класса «бинарное дерево», добавление элементов
Написал код: #include &lt;iostream&gt; using namespace std; class Aviobilet { public: char...

Добавление нового элемента в бинарное дерево поиска с вспомогательной функцией(без рекурсии)
с реализацией этой функции с рекурсией проблем нету.но без нее уже по-сложнее(.есть функция иbool...

Не работает вставка узла в бинарное дерево
Кто может скажите почему при вставке 2ого элемента происходит отладка Вот последовательность чисел...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru