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

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

13.06.2017, 15:19. Показов 53948. Ответов 2
Метки нет (Все метки)

Помогите пожалуйста..
Нужна программа "бинарные деревья поиска"..
и если можно объяснение..
спасибо заранее...
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2017, 15:19
Ответы с готовыми решениями:

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

Бинарное дерево поиска
Здравствуйте! Сегодня я попытался самостоятельно изучить деревья и начал с бинарного дерева поиска....

Бинарное дерево поиска
Имею такой код. Помогите реализовать метод поиска и печати всех узлов дерева, которые имеют только...

Бинарное дерево поиска
Вот задали лабораторною работу. Сделал бинарное дерево поиска. Выдает ошибку "Что послан сигнал от...

2
2 / 2 / 1
Регистрация: 03.03.2017
Сообщений: 1
16.06.2017, 00:20 2
Лучший ответ Сообщение было отмечено jeminn как решение

Решение

Дерево должно быть упорядоченным, то есть элементы левого поддерева некоторого узла должны быть меньше, чем элемент этого узла, а элементы правого поддерева должны быть больше, чем элемент текущего узла
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
#include "stdafx.h"
#include <iostream>
#include <Windows.h>
#include <conio.h>
#include <cmath>
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;
}
2
1 / 1 / 0
Регистрация: 25.04.2017
Сообщений: 25
15.06.2019, 14:38 3
Это простое дерево, не бинарное дерево поиска !
В дереве поиска вывод строго упорядочен, если вытянуть получившееся дерево в прямую то значения всегда будут в порядке от наименьшего в наибольшему. Ваш код так не работает.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.06.2019, 14:38
Помогаю со студенческими работами здесь

Бинарное дерево поиска C++
+Доброго времени суток! У меня есть задание:создать картотеку,в ней указать тип магазина,номер...

Бинарное дерево поиска
#include &lt;iostream&gt; using namespace std; struct node { int key; node *left; ...

Бинарное дерево поиска
Дали такую задачу: Дан набор попарно не равных целых чисел, по ним строится бинарное дерево...

Бинарное дерево поиска
Решил написать бинарное дерево поиска, но что-то пошло не так, дерево не выводиться не понимаю...


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

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

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