자료구조 <이진 트리(Binary Tree) 데이터 순회>

개요

 

트리의 순회는 말그대로 데이터를 순회하는 방식을 말합니다.

 

크게 세 종류이며 각각 전위 순회( preorder traverse ), 중위 순회( inorder traverse ), 후위 순회( postorder traverse ) 라고 불립니다.

 

본문

 

 

 

먼저 전위, 중위, 후위 순회의 방법부터 살펴보겠습니다.

• 전위 순회 : 부모 => 왼쪽 => 오른쪽 순으로 순회합니다.
• 중위 순회 : 왼쪽 => 부모 => 오른쪽 순으로 순회합니다. 
• 후위 순회 : 왼쪽 => 오른쪽 => 부모 순으로 순회합니다.

전위 순회로 순회 : 8 > 5 > 3 > 6 > 2 > 4 > 9

중위 순회로 순회 : 3 > 5 > 6 > 8 > 4 > 2 > 9

후위 순회로 순회 : 3 > 6 > 5 > 4 > 9 > 2 > 8

 

순회 메서드의 구현은 재귀 함수에 대해 이해하고 있다면 쉽게 구현할 수 있습니다.

 

1. 전위 순회

void PreOrder(Node curNode)
{
//전위 : 부모->왼쪽->오른쪽

    if (curNode == null)
        return;
    Debug.Log(curNode.item);
    PreOrder(curNode.left);
    PreOrder(curNode.right);
}

 

 

2. 중위 순회

//중위순회 //중위 : 왼쪽->자신->오른쪽
void InOrder(Node curNode)
{
    if (curNode == null)
        return;
    InOrder(curNode.left);
    Debug.Log(curNode.item);
    InOrder(curNode.right);
}

 

3. 후위 순회

//후위순회 //후위 : 왼쪽->오른쪽->자신
void PostOrder(Node curNode)
{
    if (curNode == null)
        return;
    PostOrder(curNode.left);
    PostOrder(curNode.right);
    Debug.Log(curNode.item);
}

 

마무리

 

이번 포스팅에서는 이진 트리의 순회에 대해 알아보았습니다. 트리의 재귀적인 구조를 이용하여 순회 메서드를 짜는 것이 쉽지는 않겠지만 재귀 함수에 대해 잘 이해하고 있다면 그리 어려운 내용도 아니기에 직접 함수 호출과 리턴을 생각하며 작성하면 한층 더 이해하기 수월할 것입니다.