트리 순회(Tree Traversal) 방법 02 : 코드

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> adj[1004];
int visited[1004];

void postOrder(int here)
{
	if (visited[here] == 0)
	{
		if (adj[here].size() == 1) postOrder(adj[here][0]);
		if (adj[here].size() == 2)
		{
			postOrder(adj[here][0]);
			postOrder(adj[here][1]);
		}
		visited[here] = 1;
		cout << here << " ";
	}
}

void preOrder(int here)
{
	if (visited[here] == 0)
	{
		visited[here] = 1;
		cout << here << " ";
		if (adj[here].size() == 1) preOrder(adj[here][0]);
		if (adj[here].size() == 2)
		{
			postOrder(adj[here][0]);
			postOrder(adj[here][1]);
		}
	}
}

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  // 자식이 없는 경우 (리프 노드)
		{
			cout << here << " ";     // 현재 노드 출력
		}
	}
}

void LevelOrder(int here)
{
	queue<int> q;
	visited[here] = 1;
	q.push(here);
	while (!q.empty())
	{
		int here = q.front(); q.pop();
		cout << here << " ";
		for (auto there : adj[here])
		{
			if (!visited[there])
			{
				visited[there] = 1;
				q.push(there);
			}

		}
	}
}

int main()

{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cout << "노드의 수? :";
	cin >> n;

	cout << "부모 자식 관계를 " << n - 1 << "번 입력하세요. : \n";
	for (int i = 0; i < n - 1; i++)
	{
		int parent, child;
		cin >> parent >> child;
		adj[parent].push_back(child);
	}
	int root = 1; // 루트 노드를 1로 가정

	cout << "\n Preorder (전위 순회): ";
	fill(visited, visited + 1004, 0); // 방문 초기화
	preOrder(root);

	cout << "\n Inorder (중위 순회): ";
	fill(visited, visited + 1004, 0);
	inOrder(root);

	cout << "\n Postorder (후위 순회): ";
	fill(visited, visited + 1004, 0);
	postOrder(root);


	cout << "\n Level-order (레벨 순회): ";
	fill(visited, visited + 1004, 0);
	LevelOrder(root);

	cout << endl;

	return 0;
}

---

✅ 코드 설명

1️⃣ 트리를 vector<int> adj[1004]로 저장
2️⃣ 4가지 순회 방식 구현

• 전위 순회 (Preorder): 부모 → 왼쪽 → 오른쪽
• 중위 순회 (Inorder): 왼쪽 → 부모 → 오른쪽
• 후위 순회 (Postorder): 왼쪽 → 오른쪽 → 부모
• 레벨 순회 (Level-order): BFS 사용 (큐 활용)
  3️⃣ 매번 visited[] 배열을 초기화하여 순회 방식이 겹치지 않도록 함
  4️⃣ main()에서 노드 개수와 부모-자식 관계를 입력받아 트리를 구축
  5️⃣ 순회 결과를 출력!

---

✅ 실행 예제

📌 입력

노드 개수를 입력하세요: 5
부모-자식 관계를 4번 입력하세요:
1 2
1 3
2 4
2 5

구성된 트리

        1
       / \
      2   3
     / \
    4   5

---

📌 출력

🔹 Preorder (전위 순회): 1 2 4 5 3 
🔹 Inorder (중위 순회): 4 2 5 1 3 
🔹 Postorder (후위 순회): 4 5 2 3 1 
🔹 Level-order (레벨 순회)= BFS: 1 2 3 4 5