Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой

@artlinenn · Регистрация: 15.02.2013

Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

@salam · 20.04.2013, 20:43

дфс от корня. условие перехода в другую вершину: выполнение условия для пирамиды. любой путь будет пирамидой.

@ya_noob · 20.04.2013, 21:16

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

дфс от корня. условие перехода в другую вершину: выполнение условия для пирамиды. любой путь будет пирамидой.

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

@artlinenn 0 / 0 / 0 Регистрация: 15.02.2013 Сообщений: 61
		1
	Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой 20.04.2013, 19:40. Просмотров 2631. Ответов 2 Метки нет (Все метки) Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой. 0

@salam 193 / 173 / 30 Регистрация: 10.07.2012 Сообщений: 799
	20.04.2013, 20:43	2
	дфс от корня. условие перехода в другую вершину: выполнение условия для пирамиды. любой путь будет пирамидой. 0

@ya_noob _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	20.04.2013, 21:16	3
	Сообщение от salam дфс от корня. условие перехода в другую вершину: выполнение условия для пирамиды. любой путь будет пирамидой. А как же условие сбалансированности пирамиды? после дфс нужно снова обходить получившееся дерево и обрезать ненужные ветви. по-моему бфс с доп. условием (проверяющим сохранение свойств пирамиды) здесь будет эффективнее, т.к. этот обход соответствует порядку построения пирамиды (по уровням). 0

Опции темы