Рекурсивные и итеративные реализации обходов в предварительном, последовательном и последующем порядке.
Содержание
- Что такое поиск в глубину?
- Что такое обходы по предварительному заказу, по заказу и после заказа?
- Какой из трех поисков проходит по бинарному дереву поиска в порядке возрастания?
- Можете ли вы представить результат каждого из трех обходов?
- Реализовать рекурсивный предварительный поиск в глубину.
- Реализовать рекурсивный поиск в глубину по порядку.
- Реализовать рекурсивный поиск в глубину после заказа.
- Каковы компромиссы для рекурсивного поиска в глубину?
- Какая структура данных используется для итеративного поиска в глубину?
- Реализуйте итеративный поиск в глубину с предварительным заказом.
- Реализуйте итеративный поиск в глубину по порядку.
- Реализуйте итеративный поиск в глубину после заказа.
Поиск в глубину, в отличие от поиска в ширину, бинарного дерева — это форма поиска, которая идет от корня к высоте дерева перед возвратом и повторением путей, которые еще не исследованы.
Рассмотрим отправку значений следующего бинарного дерева поиска по мере того, как узлы просматриваются в глубину. Эти обходы, а следовательно, и толчки, могут выполняться следующими способами: предварительный заказ, порядок и пост-порядок.
Порядок обхода следующий:
- Предварительный заказ: родительский → левый дочерний элемент → правый дочерний элемент
- По порядку: левый дочерний элемент → родительский элемент → правый дочерний элемент
- Пост-порядок: левый дочерний → правый дочерний → родительский
Обратите внимание, что префикс показывает, когда посещается родитель. Это мысленный способ запоминания связанных порядков: родительский элемент посещается перед дочерними элементами в предварительном порядке, родительский элемент посещается между дочерние элементы в в-порядке, а родительский элемент посещается после дочерних элементов в после-порядке.
Результаты следующие:
- Предзаказ: [27, 14, 10, 19, 35, 31, 42]
- По порядку: [10, 14, 19, 27, 31, 35, 42]
- Почтовый заказ: [10, 19, 14, 31, 42, 35, 27]
Для бинарных деревьев поиска обход по порядку является особенным, поскольку он посещает узлы в порядке возрастания (т. е. по порядку). Это примечательный умственный ярлык! На самом деле, если обход бинарного дерева по порядку не является восходящим, дерево по определению не является бинарным деревом поиска.
Один из способов представить результат обхода по порядку — это падение здания прямо вниз. Вы видите это ниже?
Один из способов мысленно представить результат обхода предварительного порядка — представить бинарное дерево поиска как самое высокое здание в мире, падающее влево. Поскольку он такой высокий, вершина падает полностью влево. Когда он падает, верхняя часть здания опрокидывается влево, и при падении оно хватается за две свои колонны — наконец, падает влево. Чем выше узел, тем больше он падает влево. База не двигается. Вы видите это ниже?
Представьте, что то же самое происходит с почтовым заказом, но справа. Вы видите это ниже?
Визуализация выходных данных указывает, какой из трех поисковых запросов следует реализовать в данной проблеме. Кроме того, в то время как пост-порядок и порядок — это способ обхода дерева снизу вверх, предварительный порядок — это способ обхода сверху вниз.
Существует два способа реализации поиска в глубину: рекурсивный и итеративный.
Хотя рекурсивная реализация кратка и ясна, она всегда вызывает переполнение стека, если число высоты дерева больше, чем стек вызовов. С другой стороны, итеративная реализация всегда будет работать, но она гораздо менее элегантна и ее сложнее концептуализировать.
Для реализации класс узла и бинарные деревья поиска реализованы как:
Рекурсивные реализации
Рекурсивные реализации интуитивно следуют из определений порядков обхода. В предварительном порядке родительское значение помещается перед рекурсивными вызовами левого и правого дочерних элементов. По порядку родительское значение помещается между рекурсивными вызовами левого и правого дочерних элементов. В обратном порядке родительское значение помещается после рекурсивных вызовов левого и правого дочерних элементов.
Хотя эти реализации элегантны, они не работают для больших деревьев. Вот почему предпочтительны итеративные реализации.
Итеративные реализации
Стек используется для итеративных реализаций. Узлы вставляются в стек и извлекаются из него до тех пор, пока в дереве не останется узлов для обхода.
Предварительный заказ
Предварительный обход проще всего реализовать итеративно, потому что он выполняется сверху вниз. В отличие от двух других, восходящих, нет необходимости проверять, что текущий узел не имеет дочерних элементов, перед отправкой в пройдено. Когда выбор между тремя обходами неважен, эта реализация предпочтительнее, потому что она итеративна и наиболее лаконична.
В приведенном выше коде стек инициализируется корнем (строка 2). Поскольку узлы помещаются, когда левый и правый дочерние элементы не равны нулю, стек будет пуст, когда дерево будет полностью пройдено (строка 6).
Более того, правый дочерний элемент помещается в стек перед левым дочерним элементом. Это делается для того, чтобы поддерживать левый дочерний элемент перед порядком правого дочернего элемента, когда они извлекаются из стека (т. е. выталкиваются вправо, а затем влево, чтобы порядок извлечения был левым, а затем правым).
Обратите внимание, что неважно, происходит ли отправка в traversed в строке 8, 9 или 10. Важно то, что сначала извлекается стек (строка 7), а затем перемещается вправо (строка 8). , а левая нажимается последней (строка 9).
В качестве альтернативы обход предварительного порядка также может быть выполнен, как показано выше. Этот подход отражает итеративный обход по порядку, показанный ниже, с той разницей, когда происходит нажатие на обход. Здесь push происходит перед назначением curr левому и правому дочерним элементам (строки 8, 10 и 13).
Чтобы
По порядку - это обход снизу вверх. Цикл while помещается в стек до тех пор, пока не останется дочерних элементов (строки 7–10). Затем извлеките из стека и поместите в пройденный (строки 11–12).
Переназначение curr правому дочернему элементу (строка 13) и предшествующий ему цикл while (строка 7) делают так, что отправка только пройденного (строка 12) происходит, когда curr указывает на нижний узел, который не был перемещен в traversed. Каждый поп эквивалентен возврату.
Более того, переход к traversed происходит между назначением curr левому и правому дочерним элементам (строки 9, 12 и 13). Интуитивно это следует из определения обхода по порядку.
Почтовый заказ
Эта реализация обхода после заказа с двумя стеками отражает первую реализацию предварительного заказа. Есть два различия:
1. Левый дочерний элемент помещается в стек раньше правого дочернего элемента.
2. Заталкивание во второй стек происходит после того, как дочерние элементы помещаются в первый стек.
Второй цикл while (строки 14–17) служит для заполнения traversed путем обращения второго стека.
В качестве альтернативы второго цикла while можно избежать, вернув второй стек в обратном порядке (строка 13). Обратите внимание, что эти две реализации имеют одинаковую временную сложность.
Это можно сделать с одним стеком, как показано выше, но, поскольку временные и пространственные сложности всех трех реализаций одинаковы, этой реализации следует избегать.
Создавайте компонуемые интерфейс и серверную часть
Не создавайте веб-монолиты. Используйте Bit для создания и компоновки несвязанных программных компонентов — в ваших любимых фреймворках, таких как React или Node. Создавайте масштабируемые и модульные приложения с мощными и приятными возможностями разработки.
Перенесите свою команду в Bit Cloud, чтобы совместно размещать и совместно работать над компонентами, а также значительно ускорить, масштабировать и стандартизировать разработку в команде. Начните с компонуемых интерфейсов, таких как Design System или Micro Frontends, или исследуйте компонуемый сервер. Попробуйте →
