[c언어] 트리 순회 알고리즘

26 Dec 2023

c언어

트리는 데이터를 계층적으로 표현하는 자료구조입니다. 이번 글에서는 트리를 순회하는 알고리즘에 대해 다뤄보겠습니다. 트리를 순회한다는 것은 모든 노드를 한 번씩 방문하는 것을 의미합니다. 이때, 방문 순서에 따라 세 가지 종류의 순회 알고리즘이 있습니다.

전위 순회 (Preorder Traversal)

전위 순회는 루트 노드를 가장 먼저 방문한 후, 왼쪽 서브트리를 순회하고 나중에 오른쪽 서브트리를 순회하는 방법입니다.

void preorderTraversal(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data); // 노드 방문
        preorderTraversal(root->left); // 왼쪽 서브트리 순회
        preorderTraversal(root->right); // 오른쪽 서브트리 순회
    }
}

중위 순회 (Inorder Traversal)

중위 순회는 왼쪽 서브트리를 먼저 순회한 후, 루트 노드를 방문하고 나서 오른쪽 서브트리를 순회하는 방법입니다.

void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left); // 왼쪽 서브트리 순회
        printf("%d ", root->data); // 노드 방문
        inorderTraversal(root->right); // 오른쪽 서브트리 순회
    }
}

후위 순회 (Postorder Traversal)

후위 순회는 왼쪽 서브트리와 오른쪽 서브트리를 먼저 순회한 후, 루트 노드를 방문하는 방법입니다.

void postorderTraversal(Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left); // 왼쪽 서브트리 순회
        postorderTraversal(root->right); // 오른쪽 서브트리 순회
        printf("%d ", root->data); // 노드 방문
    }
}

이렇게 트리를 순회하는 알고리즘은 매우 유용하며, 데이터의 처리나 탐색 등 다양한 응용에 활용될 수 있습니다.

그럼, 알고리즘에 대해 잘 이해했으면서 관련 코드를 작성하는데 어려움이 있다면, 아래 참고 자료를 참고해 보시기 바랍니다.