Лево (право) сторонний обход в прямом порядке


В данном материале описывается левосторонний обход дерева. Для получения описания правостороннего обхода нужно все упоминания лево- заменить на право- и, наоборот, право- заменить на лево-

Определение левостороннего обхода в прямом порядке: обрабатываем родителя, левое поддерево, правое поддерево (применяем рекурсивно).

В структуре дерева применяются ссылки на левое и правое поддерево. У конечных сыновей эти ссылки — пустые. Их можно использовать для прошивки дерева, позволяющею обойти дерево левосторонним способом. После обхода дерево можно и нужно расшить, для приведения в изначальное состояние. Для обозначения ссылок прошивки дерева есть два способа: 1. Ссылка на заведенный специально элемент — маркер. 2. Обе ссылки прошивки указывают на один и тот же элемент, который обходится следующим. В описание алгоритма будем использовать способ с элементом-маркером.

Определение «по возможности влево ( вправо)»: идем до развилки, на развилке выбираем левого ( правого ) сына. Продолжаем с начала определения. Элемент, не имеющий сыновей — искомый.

Описание прошивки дерева: Помним, при предыдущих действиях, «корень предыдущего правого поддерева» ( в самом начале «корень предыдущего правого поддерева» — пусто, что и будет являться признаком конца обхода ). Идем до развилки «по возможности влево», если пришли к конечному элементу, берем «корень предыдущего правого поддерева» и продолжаем с начала описания прошивки дерева ( «корень предыдущего правого поддерева» делаем пустым ). На развилке идем «по возможности вправо» до конечного элемента. У этого оконечного элемента обе ссылки на сыновей — пусты ( этот элемент обходится последним в поддереве, при левостороннем обходе в прямом порядке ). Левую делаем указующую на «корень предыдущего правого поддерева», а правую делаем указующую на элемент-маркер. Правого сына у развилки запоминаем как текущий «корень предыдущего правого поддерева». Переходим к левому сыну и продолжаем с начала описания прошивки дерева.

Описание обработки дерева с расшивкой: обрабатываем текущий узел. Если у узла больше нет сыновей — конец обхода, все дерево обработано. Если сын один — переходим к обработке и продолжаем с начала описания. Если сына два и правая ссылка ссылается на элемент-маркер, переходим к обработке левого поддерева, делаем обе ссылки пустыми и продолжаем с начала описания. Если сына два и правая ссылка не ссылается на элемент-маркер, переходим к обработке левого поддерева и продолжаем с начала описания.

Как легко видно, при применении данных описаний прошивки и обхода с расшивкой, все элементы дерева будут обработаны в порядке левостороннего обхода и, в конце, дерево вернется в первоначальную структуру. Что интересно, прошивку, обработку и расшивку можно совместить в одном алгоритме, описанном ниже.

Описание обработки дерева: обрабатываем текущий узел. Если у узла нет больше сыновей — конец обхода, все дерево обработано. Если сын один — переходим к обработке и продолжаем с начала описания. Если сына два и правая ссылка ссылается на элемент-маркер, переходим к обработке левого поддерева, делаем обе ссылки пустыми и продолжаем с начала описания. Если сына два и правая ссылка не ссылается на элемент-маркер, делаем ссылки последнего в обходе поддерева узла ( его можно найти, если пройти по «возможности вправо» ), ссылающимися на: правую на элемент-маркер, левую на «корень предыдущего поддерева». Запоминаем правого сына как «корень предыдущего правого поддерева». Переходим к обработке левого поддерева и продолжаем с начала описания.

Существуют вариации описанного алгоритма для симметричного обхода и обратного.

P.S. Данный алгоритм читается, в рамках курса «Теория алгоритмов» на Математико-Механическом факультете Санкт-Петербургского Государственного факультета. Как представитель автора, претендую на инвайт. Полномочия могу подтвердить.
P.P.S. Данный пост претендует на хаб Big Data, потому что описанный алгоритм может быть использован при экстренной сборке мусора.