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

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

12.01.2021, 01:12. Показов 525. Ответов 3

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
12.01.2021, 01:12
Ответы с готовыми решениями:

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

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

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

Бинарное дерево. Найти среднее арифметическое указанного уровня
Доброго времени суток. Необходимо найти среднее арифметическое указанного уровня ( к примеру 2) ...

3
Модератор
Эксперт функциональных языков программированияЭксперт Python
33175 / 18500 / 3901
Регистрация: 12.02.2012
Сообщений: 31,073
Записей в блоге: 12
12.01.2021, 08:23 2
Цитата Сообщение от painzavr Посмотреть сообщение
к сожалению времени на нормальное освоение темы
- и на использование тэгов языка...
0
0 / 0 / 0
Регистрация: 02.11.2020
Сообщений: 15
12.01.2021, 17:01  [ТС] 3
Спасибо за очень информативный ответ.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
33175 / 18500 / 3901
Регистрация: 12.02.2012
Сообщений: 31,073
Записей в блоге: 12
12.01.2021, 17:25 4
painzavr, не за что... После того, как модератор вставил тэги языка, я пригляделся к твоему (твоему ли?) коду.
Вот, к примеру, один из обходов дерева:

C++
1
2
3
4
5
6
7
8
9
void TreeTraversalAndPrint3(BinTree* Root) 
{
     if (Root != NULL) 
     {
            TreeTraversalAndPrint2(Root->left);
            cout << Root->value << endl;
            TreeTraversalAndPrint2(Root->right);
     }
}
ты его нарочно сделал взаимно-рекурсивным с TreeTraversalAndPrint2?

Ну, это к делу не относится. А вот что такое номер узла в дереве поиска, поясни. Просто найти число (есть/нет) - это нетрудно. А вот номер узла... что это?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2021, 17:25
Помогаю со студенческими работами здесь

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

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

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

Добавления элемента в бинарное дерево
Уже создавал подобную тему , но так и не получилось разобраться до конца . Есть такая задача :...

Бинарное дерево, удаление элемента
Задание: создать класс для хранения целых чисел в виде бинарного дерева. Обеспечить поиск,...

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


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

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

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