트리 순회 알고리즘#02 중위 순회(Inorder Traversal)

• 중위 순회

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

-왼쪽을 가장 먼저 방문하며, 오른쪽 노드 방문전에 부모노드를 방문

-이진 탐색 트리에서 사용하면 크기 순서대로 나열됨

• 코드보기

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

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

void BinaryTree::Inorder_Recursion(NODE * node)

{

        if (node == NULL)

               return;

 

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

        Inorder_Recursion(node->Left);

 

        //자신 데이터 출력

        PrintNode(node->Data);

 

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

        Inorder_Recursion(node->Right);

}

-스택을 이용한 중위 순회

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

void BinaryTree::Inorder_Stack(NODE* rootNode)

{

        NODE *indexNode = rootNode;

 

        m_Stack.Clear();

 

        while (true)

        {

               //현재 노드에서 도달 할 수 있는 최좌측 노드 찾기 & 경로에 있는 노드들 저장

               while (indexNode != NULL)

               {

                       //현재 노드 저장

                       m_Stack.Push(indexNode);

 

                       //다음 좌측 노드 지정

                       indexNode = indexNode->Left;

               }

 

               //스택에 노드가 있다면

               if (!m_Stack.IsEmpty())

               {

                       //가장 늦게 이력된 노드 수령

                       indexNode = m_Stack.Pop();

 

                       //그 노드 데이터 출력

                       PrintNode(indexNode->Data);

 

                       //현재 노드의 우측노드를 다음 노드로 => 다음 반복에서 상위 While문에 있는 m_Stack.Push로 스택에 입력됨

                       indexNode = indexNode->Right;

               }

               else

                       break;

        }

}

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