[c++] 중위 순회(Inorder Traversal) 트리 순회 알고리즘

08 Dec 2023

이번에는 C++로 중위 순회(Inorder Traversal) 트리 순회 알고리즘에 대해 살펴보겠습니다.

중위 순회(Inorder Traversal)란?

중위 순회는 이진 트리를 순회하는 방법 중 하나로, 왼쪽 서브트리를 방문한 뒤 루트 노드를 방문하고, 마지막으로 오른쪽 서브트리를 방문하는 방법입니다. 이 방법은 왼쪽 서브트리 -> 루트 노드 -> 오른쪽 서브트리 순으로 노드를 방문하며, 이진 탐색 트리의 경우에는 노드의 키 값이 오름차순으로 출력됩니다.

중위 순회(Inorder Traversal) 알고리즘 구현

다음은 중위 순회 알고리즘의 간단한 구현 예시입니다.

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);

    return 0;
}

이 코드를 실행하면, 중위 순회를 통해 이진 트리의 노드들이 방문되는 순서를 확인할 수 있습니다.

중위 순회는 이진 검색 트리를 사용하여 노드를 정렬한 후에 출력하기 위해 유용하며, 이진 트리의 모든 노드를 순회해야 하는 경우에도 이 알고리즘이 유용하게 활용될 수 있습니다.

참고 문헌:

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein