postOrder, preOrder, inOrder

 

postOrder, preOrder, inOrder 

#include <bits/stdc++.h> // C++ 표준 라이브러리 사용
using namespace std;

vector<int> adj[1004]; // 트리의 인접 리스트 표현 (1-based index)
int visited[1004];     // 노드 방문 여부를 저장하는 배열

// **후위 순회 (PostOrder)**
void postOrder(int here) {
    if (visited[here] == 0) { // 현재 노드가 방문되지 않았다면
        if (adj[here].size() == 1) // 자식이 1개인 경우
            postOrder(adj[here][0]); // 왼쪽 자식을 순회
        if (adj[here].size() == 2) { // 자식이 2개인 경우
            postOrder(adj[here][0]); // 왼쪽 자식을 순회
            postOrder(adj[here][1]); // 오른쪽 자식을 순회
        }
        visited[here] = 1; // 현재 노드 방문 처리
        cout << here << ' '; // 현재 노드 출력 (후위 순회)
    }
}

// **전위 순회 (PreOrder)**
void preOrder(int here) {
    if (visited[here] == 0) { // 현재 노드가 방문되지 않았다면
        visited[here] = 1; // 현재 노드 방문 처리
        cout << here << ' '; // 현재 노드 출력 (전위 순회)
        if (adj[here].size() == 1) // 자식이 1개인 경우
            preOrder(adj[here][0]); // 왼쪽 자식을 순회
        if (adj[here].size() == 2) { // 자식이 2개인 경우
            preOrder(adj[here][0]); // 왼쪽 자식을 순회
            preOrder(adj[here][1]); // 오른쪽 자식을 순회
        }
    }
}

// **중위 순회 (InOrder)**
void inOrder(int here) {
    if (visited[here] == 0) { // 현재 노드가 방문되지 않았다면
        if (adj[here].size() == 1) { // 자식이 1개인 경우
            inOrder(adj[here][0]); // 왼쪽 자식을 순회
            visited[here] = 1; // 현재 노드 방문 처리
            cout << here << ' '; // 현재 노드 출력 (중위 순회)
        } else if (adj[here].size() == 2) { // 자식이 2개인 경우
            inOrder(adj[here][0]); // 왼쪽 자식을 순회
            visited[here] = 1; // 현재 노드 방문 처리
            cout << here << ' '; // 현재 노드 출력 (중위 순회)
            inOrder(adj[here][1]); // 오른쪽 자식을 순회
        } else { // 자식이 없는 리프 노드인 경우
            visited[here] = 1; // 현재 노드 방문 처리
            cout << here << ' '; // 현재 노드 출력
        }
    }
}

int main() {
    // 트리 정의 (인접 리스트)
    adj[1].push_back(2); // 1번 노드의 왼쪽 자식: 2번 노드
    adj[1].push_back(3); // 1번 노드의 오른쪽 자식: 3번 노드
    adj[2].push_back(4); // 2번 노드의 왼쪽 자식: 4번 노드
    adj[2].push_back(5); // 2번 노드의 오른쪽 자식: 5번 노드

    int root = 1; // 트리의 루트 노드

    // **후위 순회**
    cout << "\n트리순회: postOrder \n";
    postOrder(root); 
    memset(visited, 0, sizeof(visited)); // 방문 배열 초기화

    // **전위 순회**
    cout << "\n트리순회: preOrder \n";
    preOrder(root); 
    memset(visited, 0, sizeof(visited)); // 방문 배열 초기화

    // **중위 순회**
    cout << "\n트리순회: inOrder \n";
    inOrder(root);

    return 0;
}

/*
출력 예제:
트리순회 : postOrder
 4 5 2 3 1
트리순회 : preOrder
 1 2 4 5 3
트리순회 : inOrder
 4 2 5 1 3
*/

---

주석 추가 설명

1. 전역 변수
   • adj: 트리 구조를 저장하는 인접 리스트.
   • visited: 각 노드의 방문 여부를 저장하는 배열.
2. postOrder (후위 순회)
   • 왼쪽 자식 → 오른쪽 자식 → 현재 노드 순으로 방문.
3. preOrder (전위 순회)
   • 현재 노드 → 왼쪽 자식 → 오른쪽 자식 순으로 방문.
4. inOrder (중위 순회)
   • 왼쪽 자식 → 현재 노드 → 오른쪽 자식 순으로 방문.
5. main 함수
   • 트리를 인접 리스트로 정의합니다.
   • 후위, 전위, 중위 순회를 각각 수행하며 결과를 출력합니다.
   • 순회가 끝날 때마다 visited 배열을 초기화합니다.

---

트리 구조

트리는 다음과 같은 구조를 가집니다:

        1
       / \
      2   3
     / \
    4   5

---

출력 결과

트리순회: postOrder
4 5 2 3 1
트리순회: preOrder
1 2 4 5 3
트리순회: inOrder
4 2 5 1 3

---