Нерекурзивно изминување на бинарно стебло во POSTORDER

Подолу е напишан алгоритмот за итеративно изминување на бинарно стебло во POSTORDER. Замена за рекурзивните повици ќе биде експлицитен магацин во кој што ќе се чуваат јазлите од кои ќе треба да го продолжиме изминувањето во случај да дојдеме до NULL врска. Клучен при разгледувањето е тековниот јазел на обработка Т кој може да се случи да биде или да не биде NULL. Ако јазелот не е NULL (и не бил изваден од магацин), тоа значи дека не сме го изминале неговото лево потстебло. Во тој случај, во магацинот ќе го додадеме неговото десно дете (S.push(T->right)) и самиот тој јазел (S.push(T)) и ќе продолжиме со postorder изминување на неговото лево подстебло придвижувајќи се на лево. (Т=T->left). Ако јазелот е NULL, тоа сигнализира дека не сме можеле понатаму да одиме на лево или дека последно сме посетувале (печателе) јазел, што пак значи дека сме ги изминале и неговото лево и неговото десно потстебло. И во двата случаи, потребно е да извадиме јазел од магацинот со кој ќе продолжиме. Го вадиме јазелот од врвот на магацинот и сега тој јазел го означуваме како тековен јазел за обработка Т.  Ако сега на врвот на магацинот се појавува десното дете на Т, тоа значи дека сме го изминале само левото потстебло на Т и дека треба да го изминуваме десното потстебло. Во тој случај, го вадиме и десното дете на Т од магацинот, а самиот јазел Т го враќаме назад во магацинот. Десното дете на Т го назначуваме за тековен јазел на обработка и продолжуваме со него, т.е. со postorder изминување на десното потстебло на Т. Коренот Т го вративме назад во магацинот и подоцна кога ќе му се вратиме веќе под него во магацинот НЕМА да стои неговото десно дете што ќе значи дека сме го изминале неговото десно потстебло и дека овој пат му се враќаме само за да го посетиме (испечатиме). Подетално објаснување има веднаш под кодот.

void postOrderNonRecursive(node *T) {
      stack<node *> S;
      while (!S.empty() || T!=NULL) {
            if (T!=NULL) {
                  if (T->right != NULL) S.push(T->right);
                  S.push(T);    // [1]
                  T = T->left;  // [2]
            }
            else {
                  T = S.top();      // земи го за нареден јазелот на врвот
                  S.pop();          // и извади го тој јазел од магацинот
                  if (!S.empty() && T->right!=NULL && T->right == S.top()) {
                        S.pop();          // [3]
                        S.push(T);        // [4]
                        T = T->right;     // [5]
                  }
                  else {
                        printf(“%d”, T->data);  // visit(T)
                        T = NULL;
                  }
            }
      }
}

Ако тековниот јазел не е NULL тогаш во магацинот додади го прво неговото десно дете (ако нема десно дете не додаваме ништо), а потоа додади го и самиот јазел Т (како корен на некое потстебло). [1] Со овие два чекора сме ги зачувале и Т и неговото десно дете во магацинот, па можеме да продолжиме со левото потстебло на Т. Затоа се придвижуваме налево. [2]

Aко Т има десно дете (T->right!=NULL) и ако по вадењето на Т од магацинот, на врвот се наоѓа неговото десно дете (T->right == S.top()), тоа значи дека така останале залепени во магацинот  (Т и неговото десно дете) уште од првото додавање и дека не сме го изминале десното потстебло на Т. Во тој случај, ќе го извадиме и десното дете на Т од магацинот [3], кое што ќе го назначиме за нареден тековен јазел на обработка [5] (ќе продолжиме со postorder во десното потстебло на Т), а во меѓувреме Т ќе го вратиме назад во магацинот [4] за да не го изгубиме, бидејќи по завршувањето со postorder изминувањето на неговото десно потстебло, ќе треба да му се вратиме и да го посетиме. Проверката дали S е празен (!S.empty()) се прави само за да се избегне дополнително справување со крајниот случај кога ќе го извадиме и последниот јазел од магацинот. Тој секогаш ќе биде главниот корен на стеблото и него само ќе треба да го испечатиме.

Aко Т нема десно дете ИЛИ ако десното дете на Т не се наоѓа на врвот од магацинот по вадењето на Т, тоа значи дека : 1. Или Т е корен без десно дете чие лево потстебло веќе сме го изминале (чим сме го додале некогаш во магацинот и сега му се враќаме)  2. Или Т е корен со десно дете, но десното потстебло на Т веќе сме го изминале (затоа што во спротивно десното дете на Т ќе стоеше веднаш под Т во магацинот) .

Во обата случаи, без разлика дали Т е родител без десно дете со изминато лево потстебло или Т е родител со изминато десно потстебло, Т ќе биде следниот јазел за обработка во postorder изминување LDO. T го посетуваме (го печатиме) и тековниот јазел го враќаме на NULL затоа што наредниот јазел сигурно НЕ се наоѓа надолу во хиерархијата на Т (бидејќи сме го изминале неговото десно потстебло, а претходно и левото), туку е или нагоре, или во друго потстебло. Како и да е, потребно е да вадиме јазел од врвот на магацинот со кој ќе продолжиме. Тековен јазел NULL ни означува вадење нов јазел од врв на магацин, доколку има.

Единствениот аргумент кој го прима функцијата е покажувач кон јазелот на врвот од стеблото. Алгоритмот претпоставува дека на располагање имаме магацин во кој можеме да складираме покажувачи кон јазли и кој е на почетокот празен и завршува кога истовремено магацинот ќе биде празен и кога ќе се постави Т на NULL.

PDF документот можете да го преземете од тука : http://www.mediafire.com/?o2cmiuddy2hda96

3SEM AlStPo postorder non recursive iterative steblo drvo tree traversal постордер