16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
||||||
1 | ||||||
Удаление элементов из бинарного дерева28.11.2017, 09:49. Показов 7946. Ответов 16
Метки нет (Все метки)
Доброго времени суток!
Реализую обычное бинарное дерево (НЕ поиска) на базе массива (то еще извращение ._.) Следует написать функцию удаление элемента. Если элемент имеет дочерние узлы, то удаляется всё поддерево. Написала часть функции, а именно: случай с удалением листа и случай с одним дочерним узлом. Что делать, если узел имеет два дочерних узла - ума не приложу. Еще страшнее кажется ситуация, если дочерние узлы тоже имеют своих потомков Подозреваю, что функцию придется вызывать рекурсивно, но это мало что дает Заранее благодарю.
0
|
28.11.2017, 09:49 | |
Ответы с готовыми решениями:
16
Обратный обход бинарного дерева и удаление элементов Удаление элементов из бинарного дерева (не дерево поиска) Удаление из бинарного дерева Удаление Узла бинарного дерева |
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
28.11.2017, 10:00 | 2 |
Сообщение было отмечено Okozaoko как решение
Решение
Либо рекурсия, либо через контейнер.
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
28.11.2017, 10:02 [ТС] | 3 |
И как это реализовать? У Вас есть какие-нибудь конкретные примеры?
0
|
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
28.11.2017, 10:24 | 4 |
Если дерево в массиве, то при удалении в элемент записывается специальное значение. Не вижу у тебя такого.
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
28.11.2017, 10:39 [ТС] | 5 |
Конечно, не видите, ведь я даже не до конца понимаю, что Вы имеете в виду
0
|
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
28.11.2017, 10:46 | 6 |
Дерево всегда хранится как полное, если каких-то узлов нет, то в ячейку записывают специальное значение. Никаких сдвигов элементов не делают. Нужно просто пометить удаляемый узел и его потомков. А координаты вычисляются по формулам.
Здесь смотри "Представление бинарного дерева в виде массива": http://mirznanii.com/a/314244/... de-massiva
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
28.11.2017, 11:07 [ТС] | 7 |
Хорошо, я прочитала и поняла. Но нам просто иначе всё объясняли. И формулы узлов у нас другие (левый: 2*(i+1)-1, правый: 2*(i+1)).
Чувствую, если я сделаю по данному примеру, то ничего хорошего из этого не выйдет
0
|
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
28.11.2017, 13:36 | 8 |
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
01.12.2017, 12:21 [ТС] | 9 |
Я Вам еще раз повторяю: у нас совершенно другие формулы, совершенно другой подход
0
|
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
01.12.2017, 12:23 | 10 |
Может, у вас и математика другая? И физика тоже.
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
01.12.2017, 12:43 [ТС] | 11 |
Может быть, но это сути не меняет
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
07.12.2017, 11:14 [ТС] | 12 |
Задача решена.
0
|
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
07.12.2017, 12:19 | 13 |
Кем?
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
07.12.2017, 12:23 [ТС] | 14 |
Мной, кем же ещё?
Посидела и поразмыслила: при удалении элемента, у которого два дочерних узла, в массиве реализовать невозможно. По той простой причине, что нужно будет каждый раз смещать элемента массива, что приведет к потере дочерних узлов и одних элементов и перезапись - у других. Объяснила на примерах преподавателю, со мной согласились. Функцию решили реализовать так: если у удаляемого узла два потомка, то на место удаляемого записываем самый последний элемент массива.
0
|
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
07.12.2017, 12:26 | 15 |
Я тебе уже писал, что такое дерево хранится в массиве как полное, никакого смещения не делают. Если какого-то узла нет, то в ячейку записывают спец. значение.
0
|
16 / 16 / 10
Регистрация: 27.10.2015
Сообщений: 104
|
|
07.12.2017, 12:28 [ТС] | 16 |
Это один из подходов к реализации дерева на базе массива, но он же не единственный.
Девушки не могут программировать?
0
|
7803 / 6567 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
07.12.2017, 12:32 | 17 |
Для простого массива единственный. Ну можно усложнить элемент. Тогда получится по сути список в массиве - проще на указатели перейти.
0
|
07.12.2017, 12:32 | |
07.12.2017, 12:32 | |
Помогаю со студенческими работами здесь
17
Удаление элемента из бинарного дерева Удаление узла бинарного дерева Удаление узла из бинарного дерева Удаление вершины бинарного дерева удаление элемента бинарного дерева Удаление узла из бинарного дерева Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |