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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
FIDES
2 / 2 / 0
Регистрация: 21.12.2014
Сообщений: 88
#1

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

31.01.2016, 18:21. Просмотров 180. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.01.2016, 18:21     Поменять местами корень и одну из вершин(любую) с наибольшим уровнем в бинарном дереве
Посмотрите здесь:

Поиск в Бинарном Дереве! C++
Сумма чисел в бинарном дереве C++
Строки в бинарном дереве C++
Поменять местами строку с наибольшим и наименьшими элементами C++
В бинарном дереве определить число узлов у которых есть указатель только на одну ветвь. C++
Поиск дубликатов в бинарном дереве C++
C++ Совершить в бинарном дереве обход Правый - Корень - Левый
C++ Разобраться в бинарном дереве
Как поменять местами максимальный и минимальный элементы в дереве? C++
C++ Оператор присвоения в бинарном дереве
Предок в бинарном дереве C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 03:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru