트리는 계층적인 자료 구조로, 각 노드는 하나 이상의 자식 노드를 가질 수 있습니다. 트리 순회는 트리 구조를 탐색하는 방법 중 하나로, 모든 노드를 방문하여 원하는 작업을 수행합니다.

이 문서에서는 C++ 언어를 사용하여 트리의 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 방법을 구현하는 방법을 설명하겠습니다.

전위 순회(Preorder Traversal)

전위 순회는 루트 노드를 먼저 방문한 후에 왼쪽 서브트리를 순회하고, 이후에 오른쪽 서브트리를 순회하는 방법입니다. 전위 순회의 순서는 다음과 같습니다.

1. 현재 노드를 출력
2. 왼쪽 서브트리를 전위 순회
3. 오른쪽 서브트리를 전위 순회

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
};

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

중위 순회(Inorder Traversal)

중위 순회는 왼쪽 서브트리를 순회한 후에 현재 노드를 방문하고, 이후에 오른쪽 서브트리를 순회하는 방법입니다. 중위 순회의 순서는 다음과 같습니다.

1. 왼쪽 서브트리를 중위 순회
2. 현재 노드를 출력
3. 오른쪽 서브트리를 중위 순회

void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}

후위 순회(Postorder Traversal)

후위 순회는 왼쪽 서브트리와 오른쪽 서브트리를 순회한 후에 현재 노드를 방문하는 방법입니다. 후위 순회의 순서는 다음과 같습니다.

1. 왼쪽 서브트리를 후위 순회
2. 오른쪽 서브트리를 후위 순회
3. 현재 노드를 출력

void postorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    std::cout << root->data << " ";
}

이 예제에서는 각 순회 방법에 대한 재귀적인 방법을 사용하여 트리를 순회하고, 현재 노드에 대한 작업을 수행하는 방법을 보여주었습니다.

결론

C++를 사용하여 트리 순회를 구현하는 방법에 대해 알아보았습니다. 이러한 순회 방법은 트리 구조를 탐색하고 데이터를 처리하는 데 유용하게 사용될 수 있습니다.

[참조]

• Preorder, Inorder, and Postorder Tree Traversals in C++: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/