트리 순회 알고리즘#01 전위 순회(Preorder Traversal)

• 전위 순회
  

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

-왼쪽을 우선으로 진행하며, 부모노드 방문 후 자식노드를 좌, 우 순서로 방문한다고 생각하면 쉽다.

• 코드보기

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

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

void BinaryTree::Preorder_Recursion(NODE* node)

{

        if (node == NULL)

               return;

 

        //자신을 출력하고

        PrintNode(node->Data);

 

        //왼쪽 방문

        Preorder_Recursion(node->Left);

 

        //마지막으로 오른쪽 방문

        Preorder_Recursion(node->Right);

}

-스택을 이용한 전위 순회

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

void BinaryTree::Preorder_Stack(NODE* rootNode)

{

        NODE* indexNode;

 

        m_Stack.Clear();

        //스택에 제일먼저 루트를 입력

        m_Stack.Push(rootNode);

 

        //스택이 빌때까지 반복

        while (!m_Stack.IsEmpty())

        {

               //스텍 최상단 노드 출력

               indexNode = m_Stack.Pop();

 

               //노드 데이터 프린트

               PrintNode(indexNode->Data);

 

               //오른쪽 노드가 있다면 스텍에 입력

               StackNode(indexNode->Right);

 

               //왼쪽 노드가 있다면 스텍에 입력 <= 후입선출(LIFO)이니까 먼저 출력됨

               StackNode(indexNode->Left);

        }

}

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