[c++] 전위 순회(Preorder Traversal)

12 Dec 2023

전위 순회(preorder traversal)는 이진 트리의 노드를 순회하는 방법 중의 하나이다. 이 방법은 다음과 같이 노드를 순회한다:

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

전위 순회 방법은 노드의 값을 출력하거나 노드의 값을 다른 배열에 저장하는 등 다양한 용도로 활용될 수 있다.

전위 순회 방법을 C++로 구현하면 다음과 같이 할 수 있다:

#include <iostream>
using namespace std;

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

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

int main() {
    // 이진 트리 생성 및 초기화
    Node* root = new Node{1, new Node{2, nullptr, nullptr}, new Node{3, nullptr, nullptr}};

    // 전위 순회
    cout << "Preorder traversal: ";
    preorderTraversal(root);
    return 0;
}

위 코드에서는 preorderTraversal 함수를 사용하여 전위 순회를 구현하였다.

이 방법을 사용하면 이진 트리의 노드를 전위 순회하는 데 활용할 수 있으며, 이러한 방법은 트리를 순회하는 데 많이 사용된다.

이러한 이진 트리의 순회 방법은 트리 자료 구조를 다루는 프로그램에서 매우 유용하며, 다양한 응용 분야에 활용될 수 있다.

참고자료

https://en.wikipedia.org/wiki/Tree_traversal