Js рекурсивный обход дерева

Не получается подняться вверх по дереву, хотя, на мой взгляд, всё вроде правильно.

1 ответ 1

Вы забыли в рекурсивной функции объявить переменную liElements из за чего она автоматически становилась глобальной. Из за этого при вхождении в дочернюю ветку рекурсии эта глобальная переменная переприсваивалась, и родительская рекурсия продолжала работу с уже изменённым набором элементов.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками javascript jquery dom рекурсия или задайте свой вопрос.

Похожие

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2019 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2019.11.15.35459

У меня есть следующая рекурсивная структура данных и метод, повторяющийся над ней. При этом следует добавить уникальный номер n к каждому узлу, например его соответствующий номер впрохождение порядка уровней дерева.

Как я могу добиться этого без изменений в структуре данных и минимальных изменений в функции обработки? Результат process(data) должно быть

null чтобы отметить конец одного уровня.

Сначала нажмите на корневой узел и null в очередь. Затем выполните итерацию очереди, поместите дочерние элементы каждого узла в очередь и отметьте ненулевой элемент. Когда вы сталкиваетесь с null элемент, толкни новый. Итак, два последовательных null отмечает конец итерации.

Я использовал массив для очереди и неt исключить посещенные элементы (На) требуется место). Если пространство, занимаемое queue является узким местом, вы можете заменить его другой реализацией очереди и немного изменить алгоритм.

Давно я не писал, как то все времени не находилось. Мы говорили про деревья, давайте теперь поговорим про обход деревьев. Обходы деревьев нужны собственно для того чтоб оптимально быстрой найти необходимый элемент в дереве.

Собственно обход дерева, как и все обходы графов ( а дерево это обычный неориентированный граф ) делается двумя методами: в глубину (Depth-first) и в ширину (Breadth-first).

Какой из методов использовать?

На самом деле споров достаточно много, и если зайти на различные форумы — то вы получите огромное количество ответов, каждый из которых не факт что будет полезен для вас. Потому, для себя я решил таким образом( взято кстати с треда на stackoverflow):

  1. если вы знаете что решение где-то не далеко от вашей ноды — то лучше использовать обход в ширь, чтоб не закапываться глубоко в дерево
  2. если дерево очень глубокое, а решение редки — то лучше все таки попробовать поиск в ширь
  3. если дерево очень широкое, то можно попробовать поиск в глубь, потому как поиск в ширь может забрать слишком много времени.

Собственно, как я уже и писал, правильного ответа нет — потому надо пробовать разные варианты:) Эксперементировать всегда весело!

Так как мы будем пробовать на созданном бинарном дереве все алгоритмы, они редко бывают широкими, потому обсудим в начале поиск в глубь.

DFS. Алгоритмы в глубь имеют три типа обходов:

Pre-order стоит использовать именно тогда, когда вы знаете что вам нужно проверить руты перед тем как проверять их листья.

В результате Pre-order обхода мы получим такой порядок :

In-order обход используется как раз когда нам надо проверять в начале детей и только потом подыматься к родительским узлам.

В таком случае мы получаем просто: A,B,C,D,E,F,G,H,I

Post-order самый забавный случай — это случай когда нам нужно начать-так сказать с листов и завершить главным узлом — тоесть разложить дерево на то, как оно строилось.

В таком случае мы полчаем: A, C, E, D, B, H, I, G,F

Как видим — код очень похож:) просто разный порядок вызовов.

BFS точно такой же как и в графах. Все достаточно просто — мы бегаем в начале по рут ноде, потом по всем ее детям, потом по всем детям детей, и так далее.

Собственно на этом пока все:)

Как обычно: исходники примеров вы можете найти тут.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *