Монотонная последовательность узлов бинарного дерева поиска

@NatalieZ · Регистрация: 13.10.2014

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

Добрый день. есть бинарное дерево поиска и какое-то заданное число S. Нужно найти все монотонные последовательности узлов дерева, сумма значения которых равна S.
Пример.
6
/ \
3 8
/ \ / \
2 4 7 10
/ \ / \ / \
1 0 0 5 9 0

Для данного дерева если S = 9, то результат 3 последовательности: 6+3, 4+5, 9.

Как лучше построить алгоритм поиска этих последовательностей? Мне в голову пришла пока только мысль, выделить каждую ветку дерева и в ней уже искать эти последовательности. Кол-во веток равно кол-ву листков дерева. Но что-то мне подсказывает, что это не совсем оптимальный путь.

@Dedoc · 22.09.2015, 14:55

Можно написать общий метод обхода куста с одним корнем. Применить этот метод к каждому узлу до исчерпания узлов.

@NatalieZ 0 / 0 / 0 Регистрация: 13.10.2014 Сообщений: 8
		1
	Монотонная последовательность узлов бинарного дерева поиска 22.09.2015, 08:35. Показов 961. Ответов 1 Метки нет (Все метки) Добрый день. есть бинарное дерево поиска и какое-то заданное число S. Нужно найти все монотонные последовательности узлов дерева, сумма значения которых равна S. Пример. 6 / \ 3 8 / \ / \ 2 4 7 10 / \ / \ / \ 1 0 0 5 9 0 Для данного дерева если S = 9, то результат 3 последовательности: 6+3, 4+5, 9. Как лучше построить алгоритм поиска этих последовательностей? Мне в голову пришла пока только мысль, выделить каждую ветку дерева и в ней уже искать эти последовательности. Кол-во веток равно кол-ву листков дерева. Но что-то мне подсказывает, что это не совсем оптимальный путь. 0

@Dedoc -39 / 2 / 1 Регистрация: 21.09.2015 Сообщений: 58
	22.09.2015, 14:55	2
	Можно написать общий метод обхода куста с одним корнем. Применить этот метод к каждому узлу до исчерпания узлов. 0