트리 순회 알고리즘#03 후위 순회(Postorder Traversal)

 

 

 

 

 

 

 

• 후위 순회

 

 

 

 

 

 

 

후위 순회 결과 : A -> C -> D -> B ->F -> H -> G -> E

 

-왼쪽노드 -> 오른쪽 노드 -> 부모노드 순으로 방문

 

-쉽게 생각하면, 자식 노드들 모드 방문 후 마지막으로 부모 노드 방문

 

-루트 노드를 가장 마지막에 방문

 

 

• 코드보기

 

-재귀함수를 이용한 후위 순회

//재귀함수를 이용한 후위 순회

void BinaryTree::Postorder_Recursion(NODE *node)

{

        if (node == NULL)

               return;

 

        //왼쪽 노드 재귀함수 실행

        Postorder_Recursion(node->Left);

 

        //오른쪽 노드 재귀함수 실행

        Postorder_Recursion(node->Right);

 

        //자신 데이터 출력

        PrintNode(node->Data);

 

}

 

 

-스택을 이용한 후위 순회

//스택을 이용한 후위 순회

void BinaryTree::Postorder_Stack(NODE* node)

{

        m_Stack.Clear();

 

        while (true)

        {

               while (NULL != node)

               {

                      //현재 노드를 2번 입력

                       m_Stack.Push(node);

                       m_Stack.Push(node);

 

                       //왼쪽 노드로 이동

                       node = node->Left;

               }

 

               if (!m_Stack.IsEmpty())

               {

                       node = m_Stack.Pop();

 

                       //현재 노드의 첫번째 방문일때, 오른쪽으로 이동

                       if (!m_Stack.IsEmpty() && node == m_Stack.Peek())

                       {

                              node = node->Right;

                       }

                       //현재 노드를 두번째 방문 했을때 출력한다.

                       else

                       {

                              PrintNode(node->Data);

                              node = NULL;

                       }

               }

               else

               {

                       break;

               }

        }

}

 

출처  https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

• 전체 코드가 있는 곳으로 이동