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

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

27.04.2020, 16:33. Показов 1095. Ответов 3

Author24 — интернет-сервис помощи студентам
Доброго времени суток.
Задание:
создать бинарное дерево поиска с входной последовательностью целых чисел.
Найти в бинарном дереве количество листков(через рекурсию).

Всё готово, есть дерево, почти готова рекурсивная функция. Не могу понять какое условие сделать,чтоб в определённые момент функция была остановлена и вернула число.

P.S.Рекурсивная функция сразу перед main.
Большое спасибо.

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
#include <iostream>
using namespace std;
 
struct Node
{
    int data;
    Node* left;
    Node* right;
};
Node* root = NULL;
void InsertNode(int x, Node* leaf)
{
    Node* new_node = new Node;
    new_node->data = x;
    new_node->left = NULL; new_node->right = NULL;
    if (leaf == NULL) root = new_node;
    else
        if (x < leaf->data) //якщо число менше значення вузла (потрібно перейти на
 
            ////ліве дерево)
 
            if (leaf->left != NULL)//якщо ліве піддерево існує,
                InsertNode(x, leaf->left);//викликаємо вставку від лівого
 
    //піддерева
 
            else //якщо лівого піддерева немає
                leaf->left = new_node;//приєднуємо новий елемент як листок
 
        else//аналогічно якщо число більше або дорівнює значенню вузла
            if (leaf->right != NULL)//переходимо на праве піддерево
                InsertNode(x, leaf->right);
            else
                leaf->right = new_node;
 
}
 
void InorderPrint(Node* leaf)
 
{
    if (leaf != NULL)
    {
        InorderPrint(leaf->left);//виклик для лівого піддерева
        cout << leaf->data << ", ";//виведення елемента
        InorderPrint(leaf->right);//виклик для правого піддерева
    }
}
 
void PrintTree(Node* leaf, int& n)
{
    if (leaf != NULL) {
        n++;//збільшуємо рівень елемента - потрібний для відступів
        PrintTree(leaf->left, n);//викликаємо для лівого піддерева
        for (int i = 1; i <= n; i++)//робимо необхідну кількість відступів
            cout << " ";
        cout << leaf->data << endl;//виводимо елемент
        PrintTree(leaf->right, n);//викликаємо для правого піддерева
        n--;//зменшуємо рівень елемента
    }
}
 
Node* SearchKey(Node* node, int key)
{
    // The given key is not found in BST
    if (node == NULL) return NULL;
    // The given key is found
    else
        if (node->data == key)
            return node;
 
    // The given is greater than current node's key
        else
            if (node->data < key)
                return SearchKey(node->right, key);
    // The given is smaller than current node's key
 
            else
                return SearchKey(node->left, key);
 
}
void Delete(Node*& node, int key); // прототип (реалізація нижче)
//Функція пошуку значення попереднього елемента
void GetPredecessor(Node* node, int& key)
{
    while (node->right != NULL)
        node = node->right;
    key = node->data;
}
void DeleteNode(Node*& node) //Функція видалення елемента
{
    int key;
    Node* ptr = node; // Встаємо на вузол, який треба видалити
    if (node->left == NULL) { // Якщо у вузла лівого піддерева немає
        node = node->right; // переходимо на праве піддерево
        delete ptr; // видаляємо вузол
    }
    else // Інакше (тобто ліве піддерево вузла існує)
        if (node->right == NULL) { // Якщо правого піддерева вузла не існує
            node = node->left; // перходимо на ліве піддерево
            delete ptr; // видаляємо вузол
        }
        else { // Інакше (якщо існують обидва піддерева - ліве і праве)
            GetPredecessor(node->left, key); // Визначаємо попередній вузол,
            // який має стати на місце вузла, що видаляється
            // це останній правий вузол в лівому піддереві
            // key - значення попереднього вузла
 
            node->data = key; // присвоїти key замість значення вузла, що
 
            //видаляється
 
                Delete(node->left, key); // видалити знайдений раніше попередній вузол
                // Таким чином, фактично вузол, який треба видалити, замінюється на
 
            //попередній за значенням
 
                // І попередній видаляється, а він є листком, тобто його видалення
 
                //тривіальне
        }
}
void Delete(Node*& node, int key) // реалізація оголошеної вище функції
{ // параметри функції - вказівник на вузол (спочатку це корінь) та значення, що
    //потрібно видалити
        // функція рекурсивно шукає вузол, який треба видалити,
        // і коли знаходить, викликає безпосередньо видалення цього вузла
        if (key < node->data)
            Delete(node->left, key);
        else
            if (key > node->data)
                Delete(node->right, key);
            else
                DeleteNode(node);
 
}
 
int Kol_Leaf(Node* node,int kol)
{
    if (root == NULL)
    {
        cout << "Tree is empty" << endl;
        return 0;
    }
 
    //if()
    
    if (node->left->data == NULL && node->right->data==NULL) { kol++; }
    
    return Kol_Leaf(node->left, kol) + Kol_Leaf(node->right, kol);
}
int main()
{
    /*10. Побудувати бінарне дерево пошуку з вхідної послідовності цілих чисел.
Визначити кількість листків дерева.*/
    int x;
    int n = 10, kol = 0;
    cout << "Input 10 numbers(int): " << endl;
    for (int i = 1; i <= 10; i++)
    {
        cin >> x;
        InsertNode(x, root);
    }
 
    cout << "Tree is created." << endl;
    InorderPrint(root);
    cout << "\n==========" << endl;
    PrintTree(root, n);
 
    //cout << "Quantity of leafs: " << Kol_Leaf(root, kol) << endl;
    cout << "SUM=" << Kol_Leaf(root,0);
 
    system("pause");
    return 0;
 
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.04.2020, 16:33
Ответы с готовыми решениями:

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

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

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

Бинарное дерево поиска
Помогите пожалуйста.. Нужна программа &quot;бинарные деревья поиска&quot;.. и если можно объяснение.. ...

3
4063 / 3317 / 924
Регистрация: 25.03.2012
Сообщений: 12,483
Записей в блоге: 1
27.04.2020, 17:21 2
C++
1
2
3
4
5
6
7
int Kol_Leaf(Node* node)
{
    int kol = (node==NULL?0:1);
    kol+=Kol_leaf(node->left);
    kol+=Kol_leaf(node->right);
    return kol;
}
0
0 / 0 / 0
Регистрация: 27.04.2020
Сообщений: 10
27.04.2020, 19:00  [ТС] 3
К сожалению не работает.
Нарушение доступа чтения.
node было nullptr

;(
0
4063 / 3317 / 924
Регистрация: 25.03.2012
Сообщений: 12,483
Записей в блоге: 1
27.04.2020, 21:17 4
Лучший ответ Сообщение было отмечено estdetey как решение

Решение

C++
1
2
3
4
5
6
7
8
int Kol_Leaf(Node* node)
{
    if (node==NULL) return 0;
    int kol = 1;
    kol+=Kol_leaf(node->left);
    kol+=Kol_leaf(node->right);
    return kol;
}
1
27.04.2020, 21:17
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.04.2020, 21:17
Помогаю со студенческими работами здесь

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

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

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

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

Бинарное дерево поиска
Давайте рассмотрим некоторый пример Допустим есть числа от 0 до 99 которые добавляются в бинарное...

Бинарное дерево поиска:
Всем добрый вечер) Подскажите пж новичку из-за чего вылетает программа? Я как понял косяк в методе...


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

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

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