[자료구조]트리 순회(Tree Traversals)

트리 순회(Tree Traversals)의 개념

-트리 구조에서, 모든 노드를 효율적이고 체계적인 방법으로 한 번씩 순회하는 과정

 

 

트리 순회의 종류

-트리 순회 방식에는 대표적으로 4가지가 있습니다.

1. 전위 순회(Preorder Traversal)
2. 중위 순회(Inorder Traversal)
3. 후위 순회(Postorder Traversal)
4. 레벨 순서 순회(Level Order Traversal)

 

아래는 각 트리 순회에 사용될 코드입니다.(C언어)

typedef struct treeNode* treePointer;
typedef struct treeNode{
    int data;
    treePointer leftChild;
    treePointer rightChild;
} treeNode;

 

1.  전위 순회(Preorder Traversal)

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

다음은 재귀적으로 전위 순회를 하면서 각 노드의 값을 출력하는 코드입니다.(C언어)

void preOrder(treePointer ptr)
{
    if(ptr)
    {
    	printf("%d ",ptr->data);
    	preOrder(ptr->leftChild);
        preOrder(ptr->rightChild);
    }
}

 

2.  중위 순회(Inorder Traversal)

1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

다음은 재귀적으로 중위 순회를 하면서 각 노드의 값을 출력하는 코드입니다.(C언어)

void inOrder(treePointer ptr)
{
    if(ptr)
    {
    	inOrder(ptr->leftChild);
        printf("%d ",ptr->data);
        inOrder(ptr->rightChild);
    }
}

 

3. 후위 순회(Postorder Traversal)

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

다음은 재귀적으로 후위 순회를 하면서 각 노드의 값을 출력하는 코드입니다.(C언어)

void postOrder(treePointer ptr)
{
    if(ptr)
    {
    	postOrder(ptr->leftChild);
        postOrder(ptr->rightChild);
        printf("%d ",ptr->data);
    }
}

 

4. 레벨 순서 순회(Level Order Traversal)

-모든 노드를 낮은 레벨부터 차례대로 순회하는 것을 말합니다.

-너비 우선 순회(breadth-first traversal)라고도 합니다.

 

낮은 레벨 부터 차례대로 방문하기 위해서는 큐(Queue)를 사용하면 됩니다.

레벨 순서 순회를 하면서 각 노드의 값을 출력하는 코드는 다음과 같습니다.(C언어)

//전역변수
#define QUEUE_SIZE 100 //원하는 만큼 설정
treePointer queue[QUEUE_SIZE];
int front = 0;
int rear = 0;

//이 코드에서는 큐(Queue)는 전역변수로 설정하는게 편함. addq, deleteq에 매개변수로 넣을 필요가 없어지기 때문.

//레벨 순서 순회를 하면서 노드를 방문하여 값을 출력하는 함수
void levelOrder(treePointer ptr)
{
    if(!ptr) return;
    addq(ptr);
    while(1)
    {
        ptr = deleteq();
        if(ptr)
        {
            printf("%d ",ptr->data);
            if(ptr->leftChild)
                addq(ptr->leftChild);
            if(ptr->rightChild)
                addq(ptr->rightChild);
        }
        else break;
    }
}
//addq는 queue에 해당 요소를 담는 함수
//deleteq는 queue에서 맨 앞의 요소를 리턴하는 함수

void addq(treePointer ptr){
    queue[rear++]=ptr;
}

treePointer deleteq(){
    return queue[front++];
}

 

 

정리

-재귀적으로 방식으로 전위 순회, 중위 순회, 후위 순회를 하여 각 노드의 값을 출력할 때는, 언제 출력하는냐의 차이입니다.

• 전위 순회 : 먼저 출력하고, 왼쪽 서브 트리를 순회하고, 오른쪽 서브 트리를 순회한다.
• 중위 순회 : 왼쪽 서브 트리를 순회하고, 출력하고, 오른쪽 서브 트리를 순회한다.
• 후위 순회 : 왼쪽 서브 트리를 순회하고, 오른쪽 서브 트리를 순회하고, 출력한다.

-레벨 순서 순회를 큐(Queue)를 사용하면 구현할 수 있습니다.