Вход на сайт
Задачки на дерево
802 просмотров
Перейти к просмотру всей ветки
в ответ Программист 30.10.19 11:48
За 1-й проход ты определил, что у узла 5 в предках есть узел 2. Ну и, что предок узла 2 узел 0. Является ли узел 5 потомком узла 4 ты не выяснил.
------
Не понял.
Я взял узел 5.
Проверил цепочку предков (паренИД) до руута на наличие узла 4.
Если нашел - есть потомок - отметил, если нет - не потомок - не надо больше ничего.
Перешел к следующему непровернному узлу.
Что еще надо проверять?
Все делается в один проход по узлам и куче возвратов (но их существенно меньше чем прямых проверок) по парентам.
Про возможную акселерацию процесса - дополнительное поле и три статуса - пока не говорим.