Бинарное дерево — вопросы интервью и практические задачи
А Бинарное дерево представляет собой древовидную структуру данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым дочерним элементом и правым дочерним элементом, а самый верхний узел в дереве называется корнем.
В этом посте мы перечислили часто задаваемые вопросы на собеседовании, в которых используется бинарное дерево:
- Неупорядоченный обход дерева Средний
- Обход дерева предзаказа Средний
- Обход дерева постпорядков Средний
- Проверьте, идентичны ли два бинарных дерева или нет Простой
- Распечатать вид снизу бинарного дерева Средний
- Распечатать вид сверху бинарного дерева Средний
- Преобразование двоичного дерева в его дерево сумм на месте Простой
- Определить, являются ли заданные узлы бинарного дерева двоюродными братьями друг другу Средний
- Вывести кузенов данного узла в бинарном дереве Средний
- Проверить, является ли бинарное дерево деревом сумм или нет Средний
- Комбинации слов, образованные заменой данных цифр соответствующими алфавитами Жесткий
- Определить, является ли бинарное дерево поддеревом другого бинарного дерева Средний
- Найдите диаметр бинарного дерева. Средний
- Проверить, является ли бинарное дерево симметричным или нет Простой
- Преобразование бинарного дерева в его зеркало Простой
- Определите, можно ли преобразовать бинарное дерево в другое, выполнив любое количество обменов дочерними элементами. Простой
- Найдите наименьшего общего предка (LCA) двух узлов в двоичном дереве Средний
- Вывести все пути от корня до листовых узлов бинарного дерева Простой
- Найти предков данного узла в бинарном дереве Средний
- Найти расстояние между заданными парами узлов в бинарном дереве Жесткий
- Найдите диагональную сумму бинарного дерева Средний
- Узлы стока, содержащие ноль, в нижнюю часть бинарного дерева Жесткий
- Преобразование двоичного дерева в полное дерево путем удаления половинных узлов Средний
- Обрезать бинарное дерево, чтобы удалить узлы, лежащие на пути, сумма которого меньше k Средний
- Найдите максимальную сумму от корня до листа в двоичном дереве Средний
- Проверьте, сбалансировано ли бинарное дерево по высоте или нет Средний
- Преобразование бинарного дерева в левое дочернее бинарное дерево правого брата Средний
- Вывести все пути от листа до корневого узла бинарного дерева Средний
- Итеративно распечатайте путь от листа к корню для каждого листового узла в двоичном дереве. Средний
- Построить бинарное дерево из родительского массива Жесткий
- Найти все узлы на заданном расстоянии от листовых узлов в бинарном дереве Жесткий
- Подсчитайте все поддеревья, имеющие одинаковое значение узлов в двоичном дереве. Средний
- Найдите максимальную разницу между узлом и его потомками в бинарном дереве Средний
- Найдите путь максимальной суммы между двумя листьями в бинарном дереве. Жесткий
- Построить бинарное дерево из обхода в прямом и прямом порядке Жесткий
- Построить бинарное дерево из обходов в прямом и обратном порядке Жесткий
- Построить бинарное дерево из последовательностей порядка и порядка уровней Жесткий
- Построить полное двоичное дерево из последовательности предварительного заказа с информацией о листовых узлах. Жесткий
- Построить полное бинарное дерево из последовательности предварительного и обратного порядка Жесткий
- Найдите обратный обход бинарного дерева из его последовательности в прямом и прямом порядке. Средний
- Установить следующий указатель на неупорядоченный преемник всех узлов в двоичном дереве Простой
- Найдите обход двоичного дерева в прямом порядке из его последовательности в прямом и обратном порядке. Жесткий
- Найдите разницу между суммой всех узлов, присутствующих на нечетных и четных уровнях в двоичном дереве. Простой
- Клонировать бинарное дерево со случайными указателями Жесткий
- Многопоточное двоичное дерево — обзор и реализация Средний
- Определите, удовлетворяет ли бинарное дерево свойству сбалансированности высоты красно-черного дерева. Средний
- Создайте матрицу предков из бинарного дерева Простой
- Найдите все возможные бинарные деревья, имеющие одинаковый неупорядоченный обход Жесткий
- Выполнить обход границы на бинарном дереве Средний
- Проверить, есть ли у каждого узла бинарного дерева ровно один дочерний элемент Простой
- Оцените двоичное дерево выражений Простой
- Построение дерева выражений Простой
- Исправить свойство child-sum в бинарном дереве Средний
- Максимальная сумма путей в двоичном дереве Жесткий
- Создайте зеркало м–арного дерева Простой
- Распечатайте двумерное представление бинарного дерева Простой
- Построить бинарное дерево из матрицы предков Жесткий
- Определить, является ли данное бинарное дерево BST или нет Средний
- Найти преемника по порядку для данного ключа в BST Средний
- Исправьте двоичное дерево, которое находится всего в одном обмене от превращения в BST. Жесткий
- Найдите размер наибольшего BST в бинарном дереве Жесткий
- Распечатать структуру двоичного дерева с его содержимым на C++ Средний
- Задача о максимальном независимом множестве Средний
- Алгоритм сжатия кода Хаффмана Жесткий
- Построить декартово дерево из неупорядоченного обхода Средний
- Вычислить высоту бинарного дерева с листовыми узлами, образующими круговой двусвязный список Средний
- Узлы связи присутствуют на каждом уровне бинарного дерева в виде связанного списка Жесткий
- Преобразование троичного дерева в двусвязный список Средний
- Извлечь листья бинарного дерева в двусвязный список Средний
- Найдите вертикальную сумму бинарного дерева Жесткий
- Преобразование двоичного дерева в двусвязный список на месте Жесткий
- Проверьте, является ли обход листьев заданных бинарных деревьев одинаковым или нет Жесткий
- Эффективно печатать все узлы между двумя заданными уровнями в двоичном дереве Простой
- Вычислить высоту бинарного дерева Простой
- Удалить бинарное дерево Простой
- Обход по порядку уровней бинарного дерева Простой
- Спиральный обход бинарного дерева Средний
- Обход бинарного дерева в обратном порядке Простой
- Вывести все узлы идеального бинарного дерева в определенном порядке Жесткий
- Распечатать левое представление бинарного дерева Простой
- Найдите следующий узел на том же уровне, что и данный узел в бинарном дереве. Средний
- Проверить, является ли бинарное дерево полным бинарным деревом или нет Средний
- Вывести диагональный обход бинарного дерева Средний
- Распечатайте угловые узлы каждого уровня в бинарном дереве Простой
- Инвертировать бинарное дерево Простой
- Преобразование двоичного дерева в двусвязный список по спирали Жесткий
- Проверьте, является ли бинарное дерево минимальной кучей или нет Средний
- Инвертировать альтернативные уровни идеального бинарного дерева Жесткий
- Выполнить вертикальный обход бинарного дерева Средний
- Вычислить максимальное количество узлов на любом уровне бинарного дерева Простой
- Вывести правый вид бинарного дерева Средний
- Найдите минимальную глубину бинарного дерева Простой
- Поиск в глубину (DFS) и поиск в ширину (BFS) Новичок
- Вывести узлы бинарного дерева в вертикальном порядке Средний
Также см:
Средний рейтинг 4.9 /5. Подсчет голосов: 104
Голосов пока нет! Будьте первым, кто оценит этот пост.
Сожалеем, что этот пост не оказался для вас полезным!
Расскажите, как мы можем улучшить этот пост?
Спасибо за чтение.
Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.
Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования 🙂
Этот веб-сайт использует файлы cookie. Используя этот сайт, вы соглашаетесь с использованием файлов cookie, нашей политикой, условиями авторского права и другими условиями. Читайте наши Политика конфиденциальности. Понятно
Источник
14.10. Задачи на бинарные деревья
1. Найти сумму элементов бинарного дерева. 2. Найти вершины, у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве. 3. Найти вершины, для которых высота левого поддерева не равна высоте правого поддерева.
4. Написать функцию, которая определяет число вхождений элемента x в бинарное дерево. 5. Найти максимальный элемент бинарного дерева и количество повторений максимального элемента в данном дереве. 6. Написать функцию, которая определяет, есть ли в бинарном дереве хотя бы два одинаковых элемента. 7. Написать функцию, определяющую максимальное количество одинаковых элементов бинарного дерева. 8. Написать функцию, которая определяет, является ли бинарное дерево симметричным. 9. Написать функцию, которая определяет, является ли бинарное дерево деревом поиска. 10. Вывести все листья дерева поиска в порядке возрастания. 11. Пусть имеется бинарное дерево T . Сформировать два идеально сбалансированных дерева из отрицательных и неотрицательных элементов дерева T . 12. Вывести на экран все пути, ведущие от корня к листьям бинарного дерева, у которых суммарный вес элементов минимальный. 13. Найти последний номер из всех уровней бинарного дерева, на которых есть положительные элементы. 14. На каждом уровне бинарного дерева найти максимальный элемент. 15. На каждом уровне дерева найти количество внутренних вершин и количество листьев. 16. Найти суммы элементов всех нечетных уровней. 17. Найти минимальный и максимальный пути между листьями бинарного дерева. 18. Удалить из бинарного дерева наименьшее количество вершин таким образом, чтобы полученное дерево было строго бинарным. 19. Пусть имеется текстовый файл. Используя дерево поиска, создать другой текстовый файл – частотный словарь, содержащий слова и количество появлений каждого слова в исходном файле. 20. Написать функцию, которая осуществляет послойный обход бинарного дерева , при котором значения вершин печатаются от уровня к уровню, начиная с корневой вершины. Значения вершин дерева на каждом уровне печатаются слева направо. Для
реализации алгоритма использовать структуру очередь следующим образом. На первом шаге вставить в очередь корневую вершину. Затем прописать цикл, работающий по такому принципу. Пока очередь не пуста: 1) берем из очереди первый элемент q ; 2) выводим значение элемента q на экран; 3) если у вершины q есть левая вершина-потомок в дереве, то добавляем этот потомок в очередь; 4) если у вершины q есть правая вершина-потомок в дереве, то добавляем этот потомок в очередь; 5) удаляем из очереди элемент q .
Источник
Задания про двоичные деревья
В первой строке входа дано число N, после него следует N строк с командами для двоичной кучи. Необходимо начать с пустой кучи. Если в строке написано число, нужно добавить его в кучу. Если в строке написано GET, нужно написать в выходной файл текущий максимальный элемент кучи и удалить его из кучи.
11 10 30 GET 40 20 60 10 GET GET 0 GET Двоичные деревья поиска
Эту задачу можно решать для разных двоичных деревьев:
- Двоичное дерево поиска, наивная реализация без оптимизаций: материалы про наивную реализацию
- Декартово дерево: материалы про декартово дерево
- Дерево из стандартной библиотеки вашего языка. Найдите у себя в языке такое дерево и воспользуйтесь им для решения задачи.
Реализуйте те деревья, которые сами считаете нужным. Я рекомендую реализовать пункт 3 всем, чтобы познакомиться со стандартной библиотекой своего языка. 1 я рекомендую только тем, кто этого не делал. 2 рекомендую всем, у кого осталось на это время после решения других задач.
Только проверка на вхождение элемента
В стандартном входе в первой строке написано число N, оно означет количество чисел, которые будут даны дальше для добавления в двоичное дерево. Заведите пустое двоичное дерево поиска. Дальшее в N строках находится по одному числу. Для каждого числа вы сначала проверяете, было ли это число в дереве, а потом добавляете число в дерево, если его не было. В вывод в отдельную строку нужно написть + или — в зависимости от того, было ли число в дереве. Т.е., встречалось ли оно раньше. Например, для входа 4 10 20 10 30 (в примере всё в одну строку) вы должны вывести — — + — .
Для проврки файлы с тестами заканчиваются на слово contains , например, 1.contains.out .
Поиск следующего элемента
Задача аналогична предыдущей, но кроме знака + или — в строку надо вывести следующее по порядку число за вставленным. Или — , если такого числа нет. Например, для входа 5 20 10 20 40 30 (в примере всё в одну строку) вы должны вывести
- - (потому что 20 еще нет) - 20 (потому что сразу за 10 в дереве идет число 20 по порядку) + - (число 20 есть, но следующего по порядку за ним нет) - - - 40 (числа 30 нет, но по порядку за ним идет 40) Для проверки файлы с тестами заканчиваются на слово min-after , например, 1.min-after.out .
Источник