이진 트리의 순회

이진 트리의 순회

이진 트리를 순회한다는 것은, 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하기 위함이다. 스택이나 큐에서는 순회하는 방법이 한가지 밖에 없었지만, 이진트리를 순회하는 방법은 여러가지 이다.

---

이진트리 순회 방법

이진트리의 순회 방법엔 크게 3가지가 있다.

• 전위 : VLR
• 후위 : LRV
• 중위 : LVR

루트노드를 방문하는 것을 V, 왼쪽 서브트리를 방문하는 것을 L 그리고 오른쪽 서브트리를 방문하는 것을 R이라고 하자. 루트노드를 방문한다음 서브트리를 방문하는 것을 전위순회라고 하고, 루트노드를 왼쪽과 오른쪽 서브트리 중간에 방문하는 것을 중위순회라고 하며, 루트노드를 서브트리 방문 후에 방문하면 후위순회라고 한다.

 

트리 순회 알고리즘은 순환 기법을 사용한다. 이진트리에서, 전체트리나 서브트리의 구조는 완전히 동일하다. 따라서, 전체트리 순회에 사용한 알고리즘은 그래도 서브트리에서도 사용가능하다. 순환을 사용하기 때문에, 문제의 크기가 작아진다.

---

전위 순회

전위 순회는 루트노드를 방문하고 그 다음, 왼쪽 오른쪽 서브트리를 방문한다.

1. 루트 노드를 방문한다
2. 윈쪽 서브트리를 방문한다
3. 오른쪽 서브트리를 방문한다

만약, 루트 노드를 방문하고 왼쪽 서브트리를 방문한다고 하자. 왼쪽 서브트리도 같은 알고리즘을 사용하면된다.

 

같은 알고리즘을 반복한다!

---

중위 순회

중위 순회는 왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리 순으로 방문한다.

1. 왼쪽 서브트리 방문
2. 루트 방문
3. 오른쪽 서브트리 방문

같은 알고리즘 반복

---

후위 순회

왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

1. 왼쪽 서브트리 전부 방문
2. 오른쪽 서브트리 전부 방문
3. 루트 방문

---

이진트리 구현하기

3가지의 순회 방법, 중위순회, 후위순회, 전위순회을 구현해보도록 하자.

함수의 매개변수는 루트를 가리키는 포인터가 된다. 순환을 이용한다는 점을 기억하자.

 

중위 순회

void inorder(TreeNode *root) {
    if(root != NULL) { //NULL을 가리키면 순회 중지
        inorder(root->left); //왼쪽 서브트리를 전부 방문하는 것과 같다.
        printf("%d ", root->data); //방문
        inorder(root->right); //오른쪽 서브트리를 전부 방문하는 것과 같다.
    }
}

전위 순회

void preorder(TreeNode *root) {
    if(root != NULL) {
        printf("%d ", root->data); //root먼저 방문
        preorder(root->left); //왼쪽을 전부 방문하는 것과 같다. 왼쪽 서브트리의 루트가 또 매개변수로 입력
        preorder(root->right); //오른쪽 전부 방문하는 것과 같다. 오른쪽 서브트리의 루트가 또 매개변수로 입력
    }
}

후위 순회

void postorder(TreeNode *root) {
    if(root != NULL) {
        postorder(root->left); //왼쪽 서브트리 처리 -> 다 처리하고 나면 print로 출력
        postorder(root->right); //오른쪽 서브트리 처리 -> 다 처리하고 나면 print로 출력
        printf("%d ", root->data); //printf하는것을 방문 하는것으로 가정
    }
}

순회를 사용하는 것!

---

지금까지, 기본적인 3가지 트리순회에 대해서 살펴보았다.

다음에는 반복을 이용한 반복적 순회, 트리의 레벨순으로 순회를 하는 레벨순회를 공부해보자.