Inorder Preorder Поступорядоченный обход двоичного дерева
Типы обхода двоичного дерева и его преобразование из упорядоченного в предварительный-поступорядоченный
Мотивация:
- Обход предварительного заказа при дублировании узлов и значений может создать полную копию двоичного дерева. Его также можно использовать для создания префиксного выражения (польская нотация) из деревьев выражений: предварительно пройти дерево выражений.
- Обход по порядку очень часто используется в деревьях двоичного поиска, поскольку он возвращает значения из базового набора в порядке, в соответствии с компаратором, который установил дерево двоичного поиска (отсюда и название).
- Пост-заказный обход при удалении или освобождении узлов и значений может удалить или освободить все двоичное дерево. Он также может генерировать постфиксное представление двоичного дерева.
мы используем stack :) Итак, поехали!
Inorder Traversal:
СЛЕВА * КОРЕНЬ * ВПРАВО
Поскольку мы не используем рекурсию, мы будем использовать стек для хранения обхода, нам нужно помнить, что обход в порядке: сначала пройти левый узел, затем корень, а затем правый узел.
Псевдокод:
- Создать стек
- Вставьте корень в стек, пока не установите root = root.left continue, пока он не достигнет NULL.
- Если root равен нулю, а стек пуст, вернитесь, все готово.
- В противном случае выберите верхний узел из стека и установите его как root = popped_Node.
- распечатайте корень и идите вправо, root = root.right.
- Перейти к шагу. Конец, если
мы должны отслеживать корень, поэтому мы используем стек! если мы рассматриваем каждое поддерево как отдельное, становится легче понять обход, а затем переместиться в стек
Вывод: в порядке
4 2 5 1 3 4 2 5 1 3
Предварительный обход: мы должны помнить, что предварительный обход - это сначала обход корневого узла, затем левого узла, а затем правого узла.
* КОРЕНЬ * ЛЕВЫЙ ВПРАВО
Вывод:
1 2 4 5 3 6 7 1 2 4 5 3 6 7
Последующий обход: мы должны помнить, что предварительный обход - это сначала обход корневого узла, затем левого узла, а затем правого узла.
ВЛЕВО ВПРАВО * КОРЕНЬ *
Подход:
- Мы видели, как мы выполняем обходы по порядку и по предварительному заказу без рекурсии с использованием Stack, но обход по порядку будет отличаться и немного сложнее, чем два других. Причина в том, что почтовый заказ не является хвостовым рекурсивным (операторы выполняются после рекурсивного вызова).
- Если вы просто заметили здесь, обход после порядка - это просто обратное обходу до обхода (1 3 7 6 2 5 4, если мы сначала пройдем правый узел, а затем левый).
- Таким образом, идея состоит в том, чтобы следовать той же методике, что и обход предварительного заказа, и вместо того, чтобы печатать его, переместите его в другой стек, чтобы они вышли в обратном порядке (LIFO).
- В конце просто вытащите все элементы из второй стопки и распечатайте ее.
Вывод:
4 5 2 6 7 3 1 4 5 2 6 7 3 1
Ресурсы: https://en.wikipedia.org/wiki/Tree_traversal
находите все больше и больше полезных ресурсов, связанных с #ai #machinelearning #deeplearning # python… https://twitter.com/Ajinkya_Tweets
Аджинкья Джавале, https://www.linkedin.com/in/ajinkya-jawale-b3421a12a/
Https://angel.co/ajinkya-jawale
свяжитесь со мной здесь, [email protected]
милости!
