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

Рейтинг: 0Ответов: 1Опубликовано: 30.11.2014

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

Ответы

▲ 2

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

struct tree_node {
  struct tree_node *left, // к поддереву с меньшими ключами
                   *right;
  int key;     // тип может быть и другим
  void *data;  // аналогично.
};

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

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

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

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

Обновление

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

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

нельзя.

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

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

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

Обновление 2

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

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

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

Обновление 3

@jfs, да, утро вечера мудренее...

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

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


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


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