Бинарное дерево поменять местами

Как поменять местами самый большой элемент с самым маленьким

В общем ситуация такая, имеется бинарное дерево, нужно поменять местами самый большой элемент с самым маленьким? Как это сделать?

В вопросе не хватает исполняемого С++ кода, который пытается поменять местами крайние элементы в специфичном бинарном дереве, выбранном для примера, и описанием успешной работы программы и что происходит вместо этого, например, «программа должна напечатать -1, 10 , а вместо этого в выводе segfault». Не нужно весь код, который есть, в вопрос добавлять; лучше добавить минимальный пример (возможно написанный специально для вопроса), который можно скомпилировать и запустить, чтобы увидеть, в чём проблема.

@greeedylol, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

1 ответ 1

Предположим, что узлы дерева описаны так:

Поскольку самый большой ключ в двоичном дереве будет крайним правым, а самый маленький, наоборот, то алгоритм очевиден —

идите по дереву от корня влево и найдите родителя самого маленького. Запомните указатель на него.

Затем идите вправо и найдите родителя самого большого.

Остается поменять два указателя в этих элементах.

@jfs, конечно, однозначно понять, что имел в виду автор, говоря:

 нужно поменять местами самый большой элемент с самым маленьким 

Я имел в виду ( pmin — указатель на родителя маленького и pmax на родителя самого большого)

 typeof(pmin) t = pmin->left; pmin->left = pmax->right; pmax->right = t; 

Что же касается C++ вообще, то я поддерживаю т.з. Линуса , хотя и признаю, что это уже неизбежное зло.

Обновление 2

@dzhioev, и в самом деле, это же не из чего не следует.

Для произвольного дерева находим адреса указателей на сами минимальный и максимальный элементы за один рекурсивный обход, а потом меняем их значения (это будут указатели на поля в узлах родителей),

а второй комментарий (с текстом «перестанет быть правильным») считаем не относящимся к делу.

Обновление 3

Согласен, все мои комментарии неправильные. Если надо переставлять поддеревья, то все не просто.

Например, представьте вырожденное дерево поиска. Учтем даже, что можно поменять указатель на корень (теперь это будет max). Все равно остается вопрос к какому из линков цеплять min и как корректировать линки в max (и др. тоже).

Однако, у Вас совершенно тривиальный подход. Вы же меняете только содержимое узлов, оставляя структуру дерева нетронутой.

Комментарии у меня закончились (один уже удалил), так что, видимо, оставим задачку с Вашим решением.

Источник

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

Всем привет. Вот мое условие лабораторной работы: Дано целочисленное бинарное дерево(БД). Поменять местами корень и одну из вершин(любую) с наибольшим уровнем. Я вроде написал функции нахождения максимального значения БД(не знаю точно на правильность) и нахождения максимального уровня БД(работает правильно). Мне вот необходимо обменять эти значения, я пока не имею представления как это сделать, этот обмен значений надо организовать в процедуре 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):

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 #include #include #include #include // библиотека для 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; }

Источник

Для каждой вершины бинарного дерева, поменять местами дочерние элементы

Дано бинарное дерево.(заполняется с клавиатуры). Для каждой вершины, имеющей дочернюю, поменять местами дочерние. Меняем только значения.
Нужна помощь. Не очень понятен смысл «дочерние».
Ну и как их менять.

Для каждой вершины бинарного дерева, поменять местами дочерние элементы
Дано бинарное дерево.(заполняется с клавиатуры). Для каждой вершины, имеющей дочернюю, поменять.

Определить функцию, выполняющую для каждой вершины следу- ющее: поменять местами значения детей
Дано S-ражение, представляющее дерево вида «(Родитель РебенокЛевый Ре- бенокПравый)». Определить.

Поменять местами минимальный и максимальный элемент непустого бинарного дерева
помогите пожалуйста! простая задача — написать процедуру или функцию которая меняет местами.

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

/////////////////////////////////////////////////////////////////////////////// //1. /////////////////////////////////////////////////////////////////////////////// //Дано бинарное дерево.(заполняется с клавиатуры). Для каждой вершины, //имеющей дочернюю, поменять местами дочерние. Меняем только значения. /////////////////////////////////////////////////////////////////////////////// #include #include #include /////////////////////////////////////////////////////////////////////////////// struct T_node; /////////////////////////////////////////////////////////////////////////////// typedef std::string T_str; typedef std::shared_ptr  T_node > T_tree; /////////////////////////////////////////////////////////////////////////////// struct T_node { //------------------------------------------------------------------------- int val_; T_tree left_; T_tree right_; //------------------------------------------------------------------------- T_node( int val ) : val_( val ) {} //------------------------------------------------------------------------- }; /////////////////////////////////////////////////////////////////////////////// void insert_in_tree ( T_tree & tree, int val ) { if( !tree ) { tree.reset ( new T_node( val ) ); } else { insert_in_tree ( val  tree->val_ ? tree->left_ : tree->right_, val ); }//else } /////////////////////////////////////////////////////////////////////////////// void show_tree ( T_tree tree, T_str s = {} ) { if ( !tree ) { return; } std::cout  ->val_  ::endl; if( tree->left_ )  std::cout   <"//if if( tree->right_ )  std::cout   <"//if } /////////////////////////////////////////////////////////////////////////////// void swap_subtrees_values( T_tree tree ) { if( tree ) { swap_subtrees_values( tree->left_ ); swap_subtrees_values( tree->right_ ); if ( tree->left_ && tree->right_ ) { std::swap ( tree->left_ ->val_, tree->right_ ->val_ ); }//if }//if } /////////////////////////////////////////////////////////////////////////////// int main() { int n{}; std::cout  <"n = "; std::cin >> n; std::cout  <"\nInput "   <" integer values:"  ::endl; T_tree tree; for( int i{}; i  n; ++i ) { std::cout  <"\t# "  + 1  <"\t: "; int val{}; std::cin >> val; insert_in_tree ( tree, val ); }//for std::cout  ::endl; show_tree ( tree ); swap_subtrees_values ( tree ); std::cout  ::endl; show_tree ( tree ); }

Источник

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

Как это можно сделать? Вроде простой заменой ключей не обойтись, т.к тогда нарушится упорядоченность дерева.
С уважением.

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

Найти в бинарном дереве min и max элементы и переставить их местами
Подскажите , пожалуйста , как можно выполнить следующее задание: Бинарное дерево содержит целые.

Поменять элементы местами в бинарном файле местами прямым доступом
Дан бинарный файл, 2*n в котором записаны числа (1 2 3 4 5 6), где n=3. Отсортировать так чтобы.

Проблема: создаются лишние элементы в бинарном дереве
Вот такой код: #include <iostream> using namespace std; class Node < public:

Найти максимальный и минимальный элементы в заданном бинарном дереве
Максимальный и минимальный элементы бинарного дерева Разработайте подпрограммы, которые находят.

Как поменять первый и последний элементы в бинарном файле?
К примеру, у нас есть три числа a,b,c. На выходе необходимо получить c,d,a. Как это сделать с.

Как в одномерном массиве поменять местами четные и нечетные элементы местами
Как в обычном одномерном массиве поменять местами четные и нечетные элементы местами, без array

В бинарном слове поменять местами символы (машина Тьюринга)
Машины Тьюринга В бинарном слове поменять местами каждый первый символ с каждым вторым. Помогите.

Источник

Читайте также:  Вытынанки деревьев шаблоны распечатать