Массив центрированного обхода Прошивка — это ссылки на предшествующий и последующий узлы данного узла согласно центрированному обходу. Если порядок прошитого дерева — это ABCDEFGHI, узел D предшествует E, а F следует за узлом E Массив центрированного обхода Массив центрированного обхода Пример Попытаемся сформировать прошитое дерево из обычного двоичного дерева Упорядочение вершин центрированного обхода для дерева выше — D B A E C. Таким образом, соответствующее прошитое двоичное дерево будет выглядеть следующим образом Нерекурсивный центрированный обход для прошитого двоичного дерева Нерекурсивный центрированный обход для прошитого двоичного дерева
Как нерекурсивный метод обхода, метод должен быть итеративной процедурой, все шаги обхода узла должны быть в цикле, так что то же самое можно применить ко всем узлам дерева. Мы снова предположим центрированный обход дерева. Тогда для любого узла мы обходим сначала левое поддерево (если оно существует и в случае, если мы не обходили его ранее). Затем мы посещаем (то есть печатаем значение узлов в нашем случае) сам узел, а уж затем обходим правое поддерево (если оно существует). Если правого дерева нет, проверяем прошитую ссылку и делаем прошитую вершину текущим узлом в рассмотрении. Смотрите пример ниже.
Алгоритм Алгоритм
Шаг-1: Для текущего узла проверяем, имеется ли левый потомок, которого нет в списке посещённых. Если такой имеется, переходим к шагу 2, иначе — к шагу 3.
Шаг-2: Помещаем левого потомка в список посещённых узлов и делаем его текущим узлом. Переходим к шагу 6.
Шаг-3: Печатаем узел и если узел имеет правого потомка, переходим к шагу 4, иначе переходим к шагу 5.
Шаг-4: Делаем правого потомка текущим узлом.
Do'stlaringiz bilan baham: |
