Форум программистов, компьютерный форум CyberForum.ru

Поменять местами корень и одну из вершин(любую) с наибольшим уровнем в бинарном дереве - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не могу корректно прочитать код http://www.cyberforum.ru/cpp-beginners/thread1652086.html
vector<string> numbers; // representation of numbers as strings // numbers is the string representation for i // for numbers to numbers void initialize_numbers() { numbers.push_back("zero"); numbers.push_back("one"); numbers.push_back("two"); numbers.push_back("three");
C++ Что такое "нейронная сеть" и как она работает? Здравствуйте, объясните что такое нейронная сеть, как работает. Если можете дайте какой-нибудь простенький исходник, чтобы понять. Спасибо. http://www.cyberforum.ru/cpp-beginners/thread1652071.html
C++ Нюансы терминологии и синтаксиса: объявление и определение
Приветствую всех! Ребята, подскажите, что есть объявление структуры, а что есть определение структуры? Читал сайты, но на одном пишут, что определение, а на втором - объявление. Например, что есть это: struct example{ int intNumber; float floatNumber; };
C++ Двумерный массив необходимо заполнить по столбцам (С++)
Есть последовательность случайных букв.Необходимо создать двумерный динамический массив и заполнить его этими буквами по столбцам.Поможете?
C++ Преобразовать for в goto http://www.cyberforum.ru/cpp-beginners/thread1652006.html
люди помогите, задали написать функцию с помощью goto вот весь код #include <cmath> #include <iostream> #include <conio.h> using namespace std; int main() { double e = 2.71828182846; setlocale(LC_ALL, "rus");
C++ Инициализация указателя в функции не понимаю... main.cpp somestruct *v = 0; int main() { init(v); подробнее

Показать сообщение отдельно
FIDES
2 / 2 / 0
Регистрация: 21.12.2014
Сообщений: 89

Поменять местами корень и одну из вершин(любую) с наибольшим уровнем в бинарном дереве - C++

31.01.2016, 18:21. Просмотров 193. Ответов 0
Метки (Все метки)

Всем привет. Вот мое условие лабораторной работы: Дано целочисленное бинарное дерево(БД). Поменять местами корень и одну из вершин(любую) с наибольшим уровнем. Я вроде написал функции нахождения максимального значения БД(не знаю точно на правильность) и нахождения максимального уровня БД(работает правильно). Мне вот необходимо обменять эти значения, я пока не имею представления как это сделать, этот обмен значений надо организовать в процедуре SwapTree. Но тест составил примерно такой:
а) 9 3 2 0 0 8 1 0 0 0 5 0 2 0 3 0 0 (здесь 9 с 3 надо местами обменять)
б) 5 2 1 0 0 4 3 0 0 0 8 6 0 7 0 0 1 0 0 (вот тут, как я понял или 5 с 7 или 5 с 3 надо обменять).
(P.S БД выводится у меня слева направо, а не сверху вниз)
Вот мои наработки(версия VS 2013):
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>
#include <iomanip>
#include <locale.h>
#include <fstream>
#include <algorithm> // библиотека для max
using namespace std;
 
struct tree
{
    int info;
    tree *left, *right;
};
 
//Прототипы
tree * MakeTree(int level);                          //Создает бинарное дерево
tree * MakeTreeAuto(int level, ifstream & in);       //Создает бинарное дерево из файла
void PrintTree(tree * root, int level);              //Выводит бинарное дерево на экран
void SwapTree(tree * root);                          //Обменивает значение элементов
tree* MaxTree(tree * root);                          //Максимальное значение в дереве
int MaxLevel(tree * root, int level);                //Вычисляет максимальный уровень бинарного дерева
 
 
 
void main()
{
    setlocale(LC_ALL, "Russian");
    tree * root;    //Инициализируем дерево
 
    cout << "1.Ввести новое дерево" << endl;
    cout << "2.Загрузить дерево A" << endl;
    cout << "3.Загрузить дерево B" << endl;
    cout << "4.Загрузить дерево C" << endl;
    cout << endl;
    int Select;
    cout << "Выберите цифру от 1 до 4:" <<  endl;
    cin >> Select;  
 
    switch (Select)
    {
    case 1:
    {
        root = MakeTree(0); //Создаем и заполняем бинарное дерево
        break;
    }
    case 2:
    {
        ifstream in;        //Поток in будем использовать для чтения
        in.open("1.txt");   //Открываем файл для чтения
        root = MakeTreeAuto(0, in);
        break;
    }
    case 3:
    {
        ifstream in;        //Поток in будем использовать для чтения
        in.open("2.txt");   //Открываем файл для чтения
        root = MakeTreeAuto(0, in);
        break;
    }
    case 4:
    {
        ifstream in;        //Поток in будем использовать для чтения
        in.open("3.txt");   //Открываем файл для чтения
        root = MakeTreeAuto(0, in);
        break;
    }
    default: return;    //Если выбор неверный - завершаем программу
    }
 
    cout << endl;
    cout << "Исходное дерево:" << endl;
    PrintTree(root, 0);
 
    cout << endl;
    cout << "Обменяли местами корень и одну из вершин(любую) с наибольшим уровнем:" << endl;
    SwapTree(root);
    PrintTree(root, 0);
 
    system("pause");
    return;
}
 
//Создает бинарное дерево(из файла)
tree * MakeTreeAuto(int level, ifstream & in)
{
    int c;      //Переменная для хранения текущего значения
    in >> c;    //Считываем из файла число(или переходим на следующее через пробел)
    if (c)      //Если это число не ноль то создаем ветвь
    {
        tree * p = new tree;
        p->info = c;            //Присваиваем это значение ветви
 
        p->left = MakeTreeAuto(level + 1, in);  //Создаем правое поддерево
 
        p->right = MakeTreeAuto(level + 1, in); //Создаем левое поддерево
 
        return p;
    }
    else
        return NULL;
}
 
//Создает бинарное дерево
tree * MakeTree(int level)
{
    char c;
    cout << setw(4 * level) << "" << "Создать вершину? (y/n)" << endl;
    cin >> c;
 
    if (c == 'y')
    {
        tree * p = new tree;
        cout << setw(4 * level) << "" << "Введите значение вершины" << endl;
        cin >> p->info;
 
        cout << setw(4 * level) << "" << "Левое поддерево вершины " << p->info << endl;
        p->left = MakeTree(level + 1);
 
        cout << setw(4 * level) << "" << "Правое поддерево вершины " << p->info << endl;
        p->right = MakeTree(level + 1);
 
        return p;
    }
    else
        return NULL;
}
 
//Выводит бинарное дерево на экран
void PrintTree(tree * root, int level)
{
    if (root)
    {
        PrintTree(root->left, level + 1);
        cout << setw(4 * level) << root->info << endl;
        PrintTree(root->right, level + 1);
    }
    return;
}
 
// Максимальное значение в дереве
tree* MaxTree(tree * root)
{
    while (root->right)
    {
        root = root->right;
    }
    return root;
}
 
//Вычисляет максимальный уровень бинарного дерева 
int MaxLevel(tree * root, int level)
{
    if (root)
    {
        int left = MaxLevel(root->left, level + 1);   //Просматриваем левое поддерево 
        int right = MaxLevel(root->right, level + 1); //Просматриваем правое поддерево 
        return max(left, right);                      //Возвращаем наибольшее значение уровня 
    }
    else
        return level - 1;
}
 
// Обменивает местами корень и одну из вершин(любую) с наибольшим уровнем
void SwapTree(tree * root)
{
    if (root)
    {
        if (root->right != NULL) 
            SwapTree();
        if (root->left != NULL) /
        {           
            
        }
    }
    return;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru