트리 순회

트리 순회(Tree Traversal)

트리 자료구조 내의 모든 노드를 체계적으로 방문하는 과정을 말합니다

이러한 순회는 데이터의 구조적 특성을 분석하거나 특정 연산을 수행하기 위해 사용됩니다.

대표적인 트리 순회 방법으로는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 가 있습니다. 여기서는 이진 트리를 기준으로 설명하겠습니다. 

 

1. 전위 순회 (Preorder Traversal)

전위 순회는 다음과 같은 순서로 노드를 방문합니다:

1. 현재 노드를 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다.

이 방식은 노드를 처리한 후 자식 노드를 순차적으로 처리합니다. 따라서 트리의 루트를 먼저 처리하고자 할 때 유용합니다.

2. 중위 순회 (Inorder Traversal)

중위 순회는 다음과 같은 순서로 노드를 방문합니다:

1. 왼쪽 서브트리를 중위 순회한다.
2. 현재 노드를 방문한다.
3. 오른쪽 서브트리를 중위 순회한다.

이 방식은 이진 검색 트리에서 매우 유용하며, 중위 순회 결과는 키가 정렬된 순서로 출력됩니다. 이를 통해 트리 내의 데이터를 정렬된 형태로 검색하거나 출력할 수 있습니다.

3. 후위 순회 (Postorder Traversal)

후위 순회는 다음과 같은 순서로 노드를 방문합니다:

1. 왼쪽 서브트리를 후위 순회한다.
2. 오른쪽 서브트리를 후위 순회한다.
3. 현재 노드를 방문한다.

후위 순회는 모든 자식 노드를 먼저 처리한 후에 노드 자신을 처리하기 때문에 노드의 후처리 작업에 적합합니다. 예를 들어, 트리의 리소스를 해제하거나 계산을 수행할 때 사용됩니다.

 

 

예시 코드

#include <iostream>
#include <vector>

using namespace std;

static int N;

class Node
{
public:
	bool isRoot = false;
	Node* left;
	Node* right; 
	char c = ' ';

	void Preorder(vector<char>* result = new vector<char>())
	{
		// root
		result->push_back(c);

		if (left) 
			left->Preorder(result); 
		
		if (right)
			right->Preorder(result);

		if (isRoot) {
			for (char a : *result)
				cout << a;
			cout << "\n";
		}
	}

	void Inorder(vector<char>* result = new vector<char>())
	{

		if (left)
			left->Inorder(result);

		result->push_back(c);

		if (right)
			right->Inorder(result);

		if (isRoot) {
			for (char a : *result)
				cout << a;
			cout << "\n";
		}
	}

	void Postorder(vector<char>* result = new vector<char>())
	{
		if (left)
			left->Postorder(result);

		if (right)
			right->Postorder(result);

		result->push_back(c); 

		if (isRoot) {
			for (char a : *result)
				cout << a;
			cout << "\n";
		}
	} 


};
vector<Node> tree;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	tree.resize(N);

	for (int i = 0; i < N; i++)
	{
		char root, left, right;
		cin >> root >> left >> right;
		int rootIndex = root - 'A';
		int leftIndex = left != '.' ? left - 'A' : -1;
		int rightIndex = right != '.' ? right - 'A' : -1;
		tree[rootIndex].c = root;

		if (leftIndex > 0) {
			tree[rootIndex].left = &tree[leftIndex];
			tree[rootIndex].left->c = left;
		}
		if (rightIndex > 0)
		{
			tree[rootIndex].right = &tree[rightIndex]; 
			tree[rootIndex].right->c = right;
		}
	} 
	tree[0].isRoot = true;

	tree[0].Preorder();
	tree[0].Inorder();
	tree[0].Postorder();
}