[c++] 이진 트리 순회(Binary Tree Traversal) 알고리즘

08 Dec 2023

전위 순회(pre-order traversal)

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

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

중위 순회(in-order traversal)

중위 순회는 왼쪽 서브 트리를 순회한 후에 루트 노드를 방문하고, 마지막으로 오른쪽 서브 트리를 순회합니다.

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

후위 순회(post-order traversal)

후위 순회는 왼쪽 서브 트리와 오른쪽 서브 트리를 순회한 후에 루트 노드를 방문합니다.

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

위와 같은 방법으로 이진 트리를 순회할 수 있으며, 각 순회 방법은 트리의 구조를 다르게 보여줍니다.

더 자세한 내용은 Stanford University의 “Binary Tree Traversal” 페이지를 참조하시기 바랍니다. (https://web.stanford.edu/class/cs166/lectures/03/Small03.pdf)