Слияние бинарных деревьев

@grigandal1580 · Регистрация: 16.01.2016

Студворк — интернет-сервис помощи студентам

Слияние - это функция выбора элемента из двух
Берем два дерева; функцию, которая выбирает один элемент из двух T fun(T x1, Tx2);
Обходом берем элементы из первого и второго дерева, подставляем в эту функцию

Составляем новое дерево из результатов функции

если какое-то из первых двух деревьев закончилось, то в результат идут оставшиеся элементы не закончившегося дерева

@grigandal1580 · 29.06.2017, 12:23 **[ТС]**

Как реализовать слияние деревьев?

Слияние имеется в виду такое:

Берем два дерева; функцию, которая выбирает один элемент из двух T fun(T x1, Tx2);
Обходом берем элементы из первого и второго дерева, подставляем в эту функцию

Составляем новое дерево из результатов функции

если какое-то из первых двух деревьев закончилось, то в результат идут оставшиеся элементы не закончившегося дерева

@Kastaneda · 29.06.2017, 12:27

В чем сложность?

@vndtta · 29.06.2017, 12:37

Сообщение от grigandal1580

Обходом берем элементы из первого и второго дерева, подставляем в эту функцию

это слишком долго, там же можно целыми ветками оперировать, зачем сравнивать каждый элемент с каждым
вот пример деревья T1 и T2, если корень R2 больше корня R1, то T1L<R1<R2<T2R, где T1L -левое поддеревоT1, T2R- правое поддерево - уже отсекли половину элементов, которые не надо сравнивать друг с другом

@grigandal1580 · 29.06.2017, 13:48 **[ТС]**

Kastaneda, у меня пока только мысль есть вложенный if
Но тогда когда обход одного поддерева закончится, будет прерываться другой

Добавлено через 22 минуты

Сообщение от grigandal1580

у меня пока только мысль есть вложенный if
Но тогда когда обход одного поддерева закончится, будет прерываться другой

Kastaneda, c этим разобрался, но как оставшиеся элементы проверить - не знаю

@grigandal1580 · 29.06.2017, 13:52 **[ТС]**

vndtta, В том и дело, что каждый элемент
Сравниваемые деревья совершенно рандомные

Добавлено через 1 минуту

Сообщение от vndtta

каждый элемент с каждым

И не каждый элемент с каждым
А у нас одновременный обход двух деревьев

Новые блоги и статьи Все статьи Все блоги /
Мастер-класс по микросервисам на Node.js Reangularity 21.06.2025 Node. js стал одной из самых популярных платформ для микросервисной архитектуры не случайно. Его неблокирующая однопоточная модель и событийно-ориентированный подход делают его идеальным для. . .	Управление Arduino из WPF приложения Wired 21.06.2025 Зачем вообще связывать Arduino с WPF-приложением? Казалось бы, у Arduino есть собственная среда разработки, своя экосистема, свои способы управления. Однако при создании серьезных проектов. . .	Звёздная пыль kumehtar 20.06.2025 Я просто это себе представляю: как создавался этот мир. Как энергия слипалась в маленькие частички. Как они собирались в первые звёзды, как во вселенной впервые появился Свет. Как эти звёзды. . .	Создание нейросети с PyTorch AI_Generated 19.06.2025 Ключевое преимущество PyTorch — его питоновская натура. В отличие от TensorFlow, который изначально был построен как статический вычислительный граф, PyTorch предлагает динамический подход. Это. . .	JWT аутентификация в ASP.NET Core UnmanagedCoder 18.06.2025 Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .
Краткий курс по С# aaLeXAA 18.06.2025 Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .	50 самых полезных примеров кода Python для частых задач py-thonny 17.06.2025 Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .	C# и продвинутые приемы работы с БД stackOverflow 17.06.2025 Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .	Angular: Вопросы и ответы на собеседовании Reangularity 15.06.2025 Готовишься к техническому интервью по Angular? Я собрал самые распространенные вопросы, с которыми сталкиваются разработчики на собеседованиях в этом году. От базовых концепций до продвинутых. . .	Архитектура Onion в ASP.NET Core MVC stackOverflow 15.06.2025 Что такое эта "луковая" архитектура? Термин предложил Джеффри Палермо (Jeffrey Palermo) в 2008 году, и с тех пор подход только набирал обороты. Суть проста - представьте себе лук с его. . .

@grigandal1580 6 / 5 / 3 Регистрация: 16.01.2016 Сообщений: 255

	Слияние бинарных деревьев 29.06.2017, 12:13. Показов 2682. Ответов 5 Метки нет (Все метки) Слияние - это функция выбора элемента из двух Берем два дерева; функцию, которая выбирает один элемент из двух T fun(T x1, Tx2); Обходом берем элементы из первого и второго дерева, подставляем в эту функцию Составляем новое дерево из результатов функции если какое-то из первых двух деревьев закончилось, то в результат идут оставшиеся элементы не закончившегося дерева 0

@grigandal1580 6 / 5 / 3 Регистрация: 16.01.2016 Сообщений: 255
	29.06.2017, 12:23 [ТС]
	Как реализовать слияние деревьев? Слияние имеется в виду такое: Берем два дерева; функцию, которая выбирает один элемент из двух T fun(T x1, Tx2); Обходом берем элементы из первого и второго дерева, подставляем в эту функцию Составляем новое дерево из результатов функции если какое-то из первых двух деревьев закончилось, то в результат идут оставшиеся элементы не закончившегося дерева 0

@Kastaneda 5232 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,143 Записей в блоге: 2
	29.06.2017, 12:27
	В чем сложность? 0

Опции темы