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

Бинарное дерево, поиск номера узла по элементу

05.01.2021, 13:22. Показов 834. Ответов 2

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#include <fstream>
#include <Windows.h>
#include <conio.h>
#include <cmath>
 
 
 
using namespace std;
/*Derevokolok*/
 
 
 
using namespace std;
struct BinTree {
    int value; //содержит значение
    BinTree* left;//адрес левого поддерева
    BinTree* right;//адрес правого поддерева
};
//Функция для создания дерева
//Вход: значение будущего узла,узел бинарного дерева
//Выход: упорядоченое бинарное деревоб,заполеное значениями
void newBinTree(int val, BinTree** Tree) {
    if ((*Tree) == NULL)
    {
        (*Tree) = new BinTree; //Выделить память
        (*Tree)->value = val;  //Поместить в выделенное место аргумент
        (*Tree)->left = (*Tree)->right = NULL;
        return;
    }
    if (val > (*Tree)->value) newBinTree(val, &(*Tree)->right);//Если аргумент больше чем текущий элемент, поместить его вправо
    else newBinTree(val, &(*Tree)->left);//Иначе поместить его влево
}
//Для печати дерева
void Print(BinTree** Tree, int l)
{
    int i;
 
    if (*Tree != NULL)
    {
        Print(&((**Tree).right), l + 1);
        for (i = 1; i <= l; i++) cout << "   ";
        cout << (**Tree).value << endl;
        Print(&((**Tree).left), l + 1);
    }
}
 
void TreeTraversalAndPrint(BinTree* Root) {
    if (Root != NULL) {
        cout << Root->value << endl;
        TreeTraversalAndPrint(Root->left);
        TreeTraversalAndPrint(Root->right);
 
    }
}
 
void TreeTraversalAndPrint2(BinTree* Root) {
    if (Root != NULL) {
        TreeTraversalAndPrint2(Root->left);
        TreeTraversalAndPrint2(Root->right);
        cout << Root->value << endl;
    }
}
void TreeTraversalAndPrint3(BinTree* Root) {
    if (Root != NULL) {
        TreeTraversalAndPrint2(Root->left);
        cout << Root->value << endl;
        TreeTraversalAndPrint2(Root->right);
    }
}
//Так как в бинарном дереве поиска для каждого узла справедливо, что left < right, 
//то соответственно для нахождения наименьшенго элемента 
//надо топать от корня по левым веткам до упора - там и будет наименьший.
BinTree* MinValue(BinTree* Tree)
{
    if (Tree->left != NULL) {
        return MinValue(Tree->left);
    }
    else {
        return Tree;
    }
}
//Так как в бинарном дереве поиска для каждого узла справедливо, что left < right, 
//то соответственно для нахождения наибольшего элемента 
//надо топать от корня по правым веткам до упора - там и будет наибольший.
BinTree* MaxValue(BinTree* Tree)
{
    if (Tree->right != NULL) {
        return  MaxValue(Tree->right);
    }
    else {
        return Tree;
    }
}
int NumberOfNodes(BinTree* Tree) {
    if (Tree == NULL) return 0;
    return NumberOfNodes(Tree->left) + 1 + NumberOfNodes(Tree->right);
}
 
int ListCount(BinTree* node)
{
    if (!node)
        return 0;
    if (!node->left && !node->right)
        return 1;
    return  ListCount(node->left) + ListCount(node->right);
}
 
//Высота(максимальная глубина) дерева определяется количеством уровней, 
//на которых располагаются его вершины.
//Высота пустого дерева равна нулю, высота дерева из одного корня – единице.
//На первом уровне дерева может быть только одна вершина – корень дерева, 
//на втором – потомки корня дерева, на третьем – потомки потомков корня дерева и т.д.
 
int HeightBTree(BinTree* Tree) {
    int x = 0, y = 0;
    if (Tree == NULL) return 0;     //пустое дерево или дошли до листа
    if (Tree->left) x = HeightBTree(Tree->left); //высота левого поддерева
    if (Tree->right) y = HeightBTree(Tree->right);  //высота правого поддерева
    if (x > y) return x + 1;    //+1 от корня к левому поддереву
    else return y + 1;   //+1 от корня к правому поддереву
}
//поиск элемента в бинарном дереве поиска
BinTree* Search(BinTree* Tree, int key) {
    if (Tree == NULL) return NULL;
    if (Tree->value == key)
    {
        return Tree;
    }
 
    if (key < Tree->value) return Search(Tree->left, key);
    else
        return Search(Tree->right, key);
}
 
 
void DestroyBTree(BinTree* Tree) {
    if (Tree != NULL) {
        DestroyBTree(Tree->left);
        DestroyBTree(Tree->right);
        delete(Tree);
    }
}
void MenuProc() {
    BinTree* Tree = NULL;
    char variant;
    int val;
    cout << "Для проверки дерева его необходимо создать" << endl;
    while (_getch() != 27) {
        cout << "ведите значение (для завершения ввода нажмите ESC) ";
        cin >> val;
        newBinTree(val, &Tree);
    }
    Print(&Tree, 0);
    cout << "Прямой обход дерева" << endl;
    TreeTraversalAndPrint(Tree);
    cout << "Обратный обход дерева" << endl;
    TreeTraversalAndPrint2(Tree);
    cout << "Cимметричный обход дерева" << endl;
    TreeTraversalAndPrint3(Tree);
    cout << "Минимальный элемент дерева-> ";
    BinTree* min = MinValue(Tree);
    cout << min->value;
    cout << endl << "Максимальный элемент дерева-> ";
    BinTree* max = MaxValue(Tree);
    cout << max->value;
    cout << endl;
    cout << "Высота дерева-> ";
    int Heigh = HeightBTree(Tree);
    cout << Heigh;
    cout << endl;
    cout << "Количество элементов в дереве-> ";
    int a = NumberOfNodes(Tree);
    cout << a << endl;
    cout << "Количество листов в дереве-> ";
    int b = ListCount(Tree);
    cout << b << endl;
    cout << "Поиск элемента" << endl;
    int key;
    cout << "Введите значение элемента для поиска-> ";
    cin >> key;
    BinTree* Tree1 = Search(Tree, key);
    if (Tree1 == NULL)
        cout << "Элемент не найден";
    else
        cout << "Ваш элемент->" << Tree1->value;
    cout << endl;
    DestroyBTree(Tree);
}
 
int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    MenuProc();
    system("pause");
    return 0;
}
Есть такое вот дерево, никак не додумаю, как выводить номер узла, в котором находиться элемент, указанный с клавиатуры. Буду очень благодарен, если допишите таковую функцию или подскажите , как же ее сделать.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.01.2021, 13:22
Ответы с готовыми решениями:

Добавление узла в бинарное дерево с++
Не понимаю чего я не понимаю... Функция добавления узла в бинарное дерево работает неправильно....

Добавление в бинарное дерево узла
Имеется узел бинарного дерева: struct Node { char name; //имя узла Node *...

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

Бинарное дерево, номер узла указанного элемента
#include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;string&gt; #include &lt;map&gt; #include &lt;iomanip&gt;...

2
6571 / 4556 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
05.01.2021, 13:48 2
Цитата Сообщение от painzavr Посмотреть сообщение
Есть такое вот дерево, никак не додумаю, как выводить номер узла, в котором находиться элемент, указанный с клавиатуры.
Что такое "номер узла"?
0
0 / 0 / 0
Регистрация: 02.11.2020
Сообщений: 15
05.01.2021, 18:26  [ТС] 3
Дерево расходится на правую и левую ветвь от корня, соответственно в левую сторону начинается счет элементов - узлов и в правую, они ведутся независимо на ветвях, так нужно найти номер элемента, который я укажу после указания дерева
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.01.2021, 18:26
Помогаю со студенческими работами здесь

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

Удаление и поиск узла. Бинарное дерево. Код прилагается
Помогите исправить ошибки в удаление узла и поиск элемента. И объясните как сделать возврат самой...

Добавление узла в бинарное дерево
Имеется узел бинарного дерева: struct Node { char name; //имя узла Node *...

Вставка нового узла в бинарное дерево
Подскажите можно ли как-то реализовать, чтобы в консоле можно было вставлять новый узел, нахождение...

Бинарное дерево поиска, удаление узла
Есть вот такой код Бинарного дерева. Никак не могу себе представить как работает функция deleting...

Функция поиска с включением узла в бинарное дерево
Здравствуйте! Помогите, пожалуйста, написать функцию поиска с включением узла в бинарное дерево....


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

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

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