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

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

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

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

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

Подсчет вершин в бинарном дереве - C++
Здравствуйте,помогите написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного дерева T(корень считать вершиной 0-го...

Совершить в бинарном дереве обход Правый - Корень - Левый - C++
Нужно совершить обход Правый корень левый в бинарном дереве. #include &quot;stdafx.h&quot; #include &quot;stdlib.h&quot; #include &quot;conio.h&quot; #include...

В бинарном дереве определить число узлов у которых есть указатель только на одну ветвь. - C++
Помогите плз. Нужен код на определение числа узлов у которых есть указатель только на одну ветвь. код дерева #include&lt;iostream.h&gt; ...

Как поменять местами максимальный и минимальный элементы в дереве? - C++
как поменять местами максимальный и минимальный елемент в дереве?

Поменять местами строку с наибольшим и наименьшими элементами - C++
Дана целочисленная матрица размера 6x9. Поменять местами строку с наибольшим и наименьшими элементами

Строки в бинарном дереве - C++
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в соответствующий объект этого класса на...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.01.2016, 18:21
Привет! Вот еще темы с ответами:

Разобраться в бинарном дереве - C++
Нашел вот такой вариант построения бинарного дерева. Просьба прокомментировать строки кода которые выделил ниже: #include...

Предок в бинарном дереве - C++
Помогите пожалуйста! Необходимо написать программу, которая для двух вершин дерева определяет, является ли одна из них предком другой. ...

Поиск в Бинарном Дереве! - C++
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести на экран все одинаковые элементы в...

Удалить узел в бинарном дереве - C++
Добрый вечер. В задании нужно найти узел дерева с наибольшим показателем счетчика, после чего удалить найденный узел из дерева. В структуре...


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

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

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