Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
SiniySentin
2 / 2 / 1
Регистрация: 09.07.2016
Сообщений: 40
Завершенные тесты: 1
1

Бинарное дерево из последовательности

17.06.2018, 18:13. Просмотров 220. Ответов 1
Метки нет (Все метки)

Имеется данный код. Здесь осуществлено (часть мной, часть любезно взято с нашего любимого форума) бинарное дерево (добавление узлов и отображение дерева), также нахождение его глубины (максимального уровня). Само дерево строится из некой последовательности, которая задается пользователям. В ней (последов.) могут содержаться одинаковые числа, которые нужно "сократить" (оставить одно). До начала чтения самой проблемы прошу ознакомиться с текстом задания, прикрепленного ниже, дабы понять о чем идет речь.
Проблема: во-первых, для первого дерева программа выдает неправильную глубину (4 вместо 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
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
 
struct node
{
    int info;                           //Информационное поле
    node *l, *r;                        //Левая и Правая часть дерева
};
 
node *tree = NULL;                      //Объявляем переменную, тип которой структура Дерево
node *tree1 = NULL;
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a, node **t)
{
    if ((*t) == NULL)                   //Если дерева не существует
    {
        (*t) = new node;                //Выделяем память
        (*t)->info = a;                 //Кладем в выделенное место аргумент a
        (*t)->r = (*t)->l = NULL;       //Очищаем память для следующего роста
        return;                         //Заложили семечко, выходим
    }
    //Дерево есть
    if (a > (*t)->info) 
        push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
    else 
        push(a, &(*t)->l);         //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print(node *t, int u)
{
    if (t == NULL) return;                  //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
        print(t->l, ++u);                   //С помощью рекурсивного посещаем левое поддерево
        for (int i = 0; i < u; ++i) {
            cout << "|";
        }   
        cout << t->info << endl;            //И показываем элемент
        u--;
    }
    print(t->r, ++u);                       //С помощью рекурсии посещаем правое поддерево
}
 
int getMaxDepth(node *t, int depth) {
    if (t == NULL)
        return depth;
    return max(getMaxDepth(t->l, depth + 1), getMaxDepth(t->r, depth + 1));
}
int main()
{
    bool flag = false;
    int n, n1;                              //Количество элементов
    int s;                              //Число, передаваемое в дерево
    
    cout << "Kol-vo elementov pervogo dereva:  ";
    cin >> n;                           //Вводим количество элементов
    int *arr = new int[n];
    cout << "Vvedite element:  ";
    cin >> arr[0];
    push(arr[0], &tree);
    for (int i = 1; i<n; ++i)
    {
        cout << "Vvedite element:  ";
        cin >> arr[i];
        for (int j = 0; j < i; j++)
            if (arr[j] == arr[i])
                flag = true;
        if(!flag)
            push(arr[i], &tree); 
        flag = false;
    }
    cout << "Vashe derevo nomer 1:\n";
    print(tree, 0);
    int level = getMaxDepth(tree, 0);
    cout << endl << "Uroven' dereva nomer 1: " << level << endl << endl;
 
 
    cout << "Kol-vo elementov vtorogo dereva:  ";
    cin >> n1;                           //Вводим количество элементов
    int *arr1 = new int[n1];
    cout << "Vvedite element:  ";
    cin >> arr1[0];
    push(arr1[0], &tree);
    for (int i = 1; i<n1; ++i)
    {
        cout << "Vvedite element:  ";
        cin >> arr1[i];
        for (int j = 0; j < i; j++)
            if (arr1[j] == arr1[i])
                flag = true;
        if (!flag)
            push(arr1[i], &tree1);
        flag = false;
    }
    cout << "Vashe derevo nomer 2:\n";
    print(tree1, 0);
    int level1 = getMaxDepth(tree1, 0);
    cout << endl << "Uroven' dereva nomer 2: " << level1 << endl << endl;
    int *arr2 = new int[n + n1];
    for (int i = 0; i < n; i++)
        arr2[i] = arr[i];
    for (int i = n; i < n + n1; i++)
        arr2[i] = arr1[i];
    int temp=0;
    for (int i = 0; i < n+n1 - 1; i++) {
        for (int j = 0; j < n+n1 - i - 1; j++) {
            if (arr2[j] > arr2[j + 1]) {
                temp = arr2[j];
                arr2[j] = arr2[j + 1];
                arr2[j + 1] = temp;
            }
        }
    }
    if (level > level1)
        for (int i = 0; i < n + n1; i++)
            cout << arr2[i] << " ";
    else for (int i = n + n1 - 1; i > -1; i--)
        cout << arr2[i] << " ";
    delete[] arr;
    delete[] arr1;
    delete[] arr2;
    return 0;
}
0
Миниатюры
Бинарное дерево из последовательности  
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2018, 18:13
Ответы с готовыми решениями:

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

Для каждого числа последовательности узнать, входит ли оно в бинарное дерево
Дана задача: даны две последовательности чисел. Построить бинарное дерево, содержащее числа...

На основе вводимой с клавиатуры последовательности чисел до первого нуля формируется бинарное дерево поиска
Страшно каюсь, не подумайте что я ленивый тюлень и мне не хочется вникать в тему, обычно я никогда...

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Бинарное дерево
Мой код: Patient.h // // Created by User on 26.04.2016. // #ifndef LABA_10_PATIENT_H...

1
SiniySentin
2 / 2 / 1
Регистрация: 09.07.2016
Сообщений: 40
Завершенные тесты: 1
17.06.2018, 22:46  [ТС] 2

Не по теме:

подниму вверх, вдруг кто увидит, чего не вижу я.



Добавлено через 32 минуты
Также заметил, что еще какие-то проблемы с динамическими массивами. А именно мусорится несколько элементов.

Добавлено через 34 минуты
Задание всё-таки доделал, оставлю достояние потомкам:
Кликните здесь для просмотра всего текста
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
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
 
struct node
{
    int info;                           //Информационное поле
    node *l, *r;                        //Левая и Правая часть дерева
};
 
node *tree = NULL;                      //Объявляем переменную, тип которой структура Дерево
node *tree1 = NULL;
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a, node **t)
{
    if ((*t) == NULL)                   //Если дерева не существует
    {
        (*t) = new node;                //Выделяем память
        (*t)->info = a;                 //Кладем в выделенное место аргумент a
        (*t)->r = (*t)->l = NULL;       //Очищаем память для следующего роста
        return;                         //Заложили семечко, выходим
    }
    //Дерево есть
    if (a > (*t)->info) 
        push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
    else 
        push(a, &(*t)->l);         //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print(node *t, int u)
{
    if (t == NULL) return;                  //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
        print(t->l, ++u);                   //С помощью рекурсивного посещаем левое поддерево
        for (int i = 0; i < u; ++i) {
            cout << "|";
        }   
        cout << t->info << endl;            //И показываем элемент
        u--;
    }
    print(t->r, ++u);                       //С помощью рекурсии посещаем правое поддерево
}
 
int getMaxDepth(node *t, int depth) {
    if (t == NULL)
        return depth;
    return max(getMaxDepth(t->l, depth + 1), getMaxDepth(t->r, depth + 1));
}
 
template<typename T>
void bubble_sort(T array[], std::size_t size)
{
    for (std::size_t idx_i = 0; idx_i < size - 1; idx_i++)
    {
        for (std::size_t idx_j = 0; idx_j < size - idx_i - 1; idx_j++)
        {
            if (array[idx_j + 1] < array[idx_j])
            {
                std::swap(array[idx_j], array[idx_j + 1]);
            }
        }
    }
}
 
int main()
{
    bool flag = false;
    int n, n1;                              //Количество элементов
    int s;                              //Число, передаваемое в дерево
    
    cout << "Kol-vo elementov pervogo dereva:  ";
    cin >> n;                           //Вводим количество элементов
    int *arr = new int[n]();
    cout << "Vvedite element:  ";
    cin >> arr[0];
    push(arr[0], &tree);
    for (int i = 1; i<n; i++)
    {
        cout << "Vvedite element:  ";
        cin >> arr[i];
        for (int j = 0; j < i; j++)
            if (arr[j] == arr[i])
                flag = true;
        if(!flag)
            push(arr[i], &tree); 
        flag = false;
    }
    cout << "Vashe derevo nomer 1:\n";
    print(tree, 0);
    int level = getMaxDepth(tree, -1);
    cout << endl << "Uroven' dereva nomer 1: " << level << endl << endl;
 
 
    cout << "Kol-vo elementov vtorogo dereva:  ";
    cin >> n1;                           //Вводим количество элементов
    int *arr1 = new int[n1];
    cout << "Vvedite element:  ";
    cin >> arr1[0];
    push(arr1[0], &tree1);
    for (int i = 1; i<n1; i++)
    {
        cout << "Vvedite element:  ";
        cin >> arr1[i];
        for (int j = 0; j < i; j++)
            if (arr1[j] == arr1[i])
                flag = true;
        if (!flag)
            push(arr1[i], &tree1);
        flag = false;
    }
    cout << "Vashe derevo nomer 2:\n";
    print(tree1, 0);
    int level1 = getMaxDepth(tree1, -1);
    cout << endl << "Uroven' dereva nomer 2: " << level1 << endl << endl;
    int *arr2 = new int[n + n1];
    for (int i = 0; i < n; i++)
        arr2[i] = arr[i];
    for (int i = 0; i < n + n1; i++)
        arr2[i+n] = arr1[i];
    bubble_sort(arr2, n + n1);
    cout << "Resultiruywa posledovatelnost':" << endl;
    if (level > level1)
        for (int i = 0; i < n + n1; i++)
            cout << arr2[i] << " ";
    else 
        for (int i = n + n1 - 1; i > -1; i--)
            cout << arr2[i] << " ";
        
    delete[] arr;
    delete[] arr1;
    delete[] arr2;
    return 0;
}
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2018, 22:46

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

Бинарное дерево
Подскажите алгоритм распечатки дерева на экран горизонтально, не вертикально, как обычно это...

Бинарное дерево
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; int last; void add(double volue)...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.