[자료구조] 트리 순회(Tree traversal)

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

트리 순회

개요

　앞선 포스팅에선 트리에 원소를 삽입하는 방법에 대해 알아보았다. 이번 포스팅에선 트리의 원소를 순회하는 방법에 대해 알아보도록 하자. 여기서 순회란 모든 노드를 한 번씩 방문하는 것을 의미한다.

---

본문

　트리를 순회하는 방법은 크게 4가지가 존재한다.

• 전위 순회(Preorder traversal): 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드, 마지막으로 현재 노드의 오른쪽 하위 노드를 재귀적으로 방문하는 방식.
• 중위 순회(In-order traversal): 왼쪽 노드를 먼저 방문하고, 그다음에는 현재 노드, 마지막으로 오른쪽 노드를 방문하는 방식.
• 후위 순회(Post-order traversal): 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문하는 방식.
• 레벨 순서 순회(Level order traversal): 트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽 노드에서 오른쪽 노드 순서로 방문하는 방식.

 

　이를 구현하기 위해, 전 게시글에서 사용했던 조직도와 코드를 가져와 구현해 보도록 하자.

 

 

---

구현

　먼저 전위 순회를 구현해보도록 하자. 전위 순회는 항상 부모 노드 → 왼쪽 → 오른쪽 순으로 방문한다.

 

	static void PreOrder(node* start) // 전위 순회
	{
		if (!start)
			return;

		cout << start->_position << " "; // 부모 노드
		PreOrder(start->_left); // 왼쪽
		PreOrder(start->_right); // 오른쪽
	}

 

　다음은 중위 순회다. 

	static void InOrder(node* start) // 중위 순회
	{
		if (!start)
			return;

		InOrder(start->_left); // 왼쪽
		cout << start->_position << " "; // 부모 노드
		InOrder(start->_right); // 오른쪽
	}

 

　그리고 후위 순회다.

	static void PostOrder(node* start) // 후위 순회
	{
		if (!start)
			return;

		PostOrder(start->_left); // 왼쪽
		PostOrder(start->_right); // 오른쪽
		cout << start->_position << " "; // 부모 노드
	}

 

　마지막 레벨 순서 순회다. 

	static void LevelOrder(node* start) // 레벨 순서 순회
	{
		if (!start)
			return;

		queue<node*> q;
		q.push(start);

		while (!q.empty())
		{
			for (int i = 0; i < q.size(); i++)
			{
				auto currnetVal = q.front();
				q.pop();

				cout << currnetVal->_position << " ";

				if (currnetVal->_left)
					q.push(currnetVal->_left);
				if (currnetVal->_right)
					q.push(currnetVal->_right);
			}

			cout << '\n';
		}
	}

　앞선 순회들과 다르게 재귀적으로 구성하지 않았다. 이는 레벨 순서 순회 방법이 현재 노드에 직접 연결되어 있지 않은 노드에 방문하기 때문이다. 따라서 queue 자료구조를 이용하여 작성하였다. 

　위 코드는 현재 레벨의 노드를 방문할 때 다음 레벨 노드를 미리 큐에 추가하는 방식으로 작동한다. 이러한 작업을 다음 레벨에 노드가 없을 때까지 (큐가 비어있을 때까지) 반복하는 방식이다.

 

　이제 main 함수에 해당 함수들을 호출하고, 결과를 확인해 보자.

int main()
{
	...
	cout << '\n';
	cout << "전위 순회: "; Tree::PreOrder(tree.GetRootNode()); cout << '\n';
	cout << "중위 순회: "; Tree::InOrder(tree.GetRootNode()); cout << '\n';
	cout << "후위 순회: "; Tree::PostOrder(tree.GetRootNode()); cout << '\n';
	cout << "레벨 순회: "; Tree::LevelOrder(tree.GetRootNode());
}

실행 결과

---

요약

트리 순회
1. 정의: 트리 자료구조 내의 모든 원소들을 방문하는 것
2. 종류
　a. 전위 순회: 부모 → 왼쪽 → 오른쪽
　b. 중위 순회: 왼쪽 → 부모 → 오른쪽
　c. 후위 순회: 왼쪽 → 오른쪽 → 부모
　d. 레벨 순서 순회: 상위 → 하위