[자료구조] Tree: 순회

Tree

 

1. Tree traversal

 

Tree traversal(트리 순회)는 트리 구조에서 각각의 노드를 정확히 한번만, 체계적인 방법으로 방문하는 과정을 말한다.

 

앞서 살펴보았던 연결 리스트와 1차원 배열과 같은 선형 자료구조와 달리 트리는 순회에 많은 방법이 존재한다.

노드를 방문하는 순서에 따라 크게 4가지로 분류하여 설명할 예정이다.

 

1) preorder traversal(전위 순회)

 

전위 순회의 경우 노드 -> 제일 왼쪽 서브 트리 전위 순회 -> ... -> 제일 오른쪽 서브 트리의 전위 순회 순서로 진행된다.

 

위의 트리에서 전위 순회를 할 경우

 

a -> c -> h -> r -> l -> d -> x

 

의 순서로 노드를 방문하게 된다.

 

전위 순회는 depth-first traversal(깊이 우선 순회)라고도 불린다. 전위 순회 알고리즘은 순서에서 부모가 자식들보다 항상 전에 와야 하는 트리 노드의 선형순서화에 유용하다.

 

재귀적으로 구현된 트리의 특징에 따라 순회 함수 또한 재귀 함수를 활용한다.루트 노드를 시작으로 방문하는 노드의 값을 출력한 후(방문했음을 보여주기 위함) 해당 노드의 왼쪽 자식부터 함수를 재귀적으로 호출한다.아래는 이를 구현한 전위 순회 함수의 코드이다.

 

void preOrder(Node*nd) {
		cout << nd->data << " ";
		for (Node*it : nd->child)
			preOrder(it);
}

 

2) inorder traversal(중위 순회)

 

중위 순회의 경우 일반 트리보다 이진 탐색 트리에서 주로 사용된다.

이진 트리에서의 중위 순회는 왼쪽 서브 트리의 중위 순회 -> 노드 -> 오른쪽 서브 트리의 중위 순회 순서로 진행된다.

 

위의 트리에서 중위 순회를 할 경우

 

h -> c -> r -> l -> a -> x -> d

 

의 순서로 노드를 방문하게 된다.

 

void inOrder(Node*nd) {
		if (nd->left != NULL) {
			inOrder(nd->left);
		}
		cout << nd->data << " ";
		if (nd->right != NULL) {
			inOrder(nd->right);
		}
	}

 

3) postorder traversal(후위 순회)

 

후위 순회의 경우 제일 왼쪽 서브 트리의 후위 순회 -> ... -> 제일 오른쪽 서브 트리의 후위 순회 -> 노드의 순서로 진행된다.

 

위의 트리에서 후위 순회를 할 경우

 

h -> l -> r -> c -> x -> d -> a

 

의 순서로 노드를 방문하게 된다.

 

void postOrder(Node*nd) {
		for (Node*it : nd->child)
			postOrder(it);
		cout << nd->data << " ";
}

 

 

4) level-order traversal(레벨 순서 순회)

 

depth가 같은 노드들을 같은 level에 있다고 한다.

레벨 순서 순회의 경우 모든 노드를 낮은 레벨부터 차례대로 순회가 진행된다.

 

이는 breadth first traversal(너비 우선 순회)라고도 불린다.

 

레벨 순서 순회는 큐를 활용하여 구현한다.

root node부터 시작하여 방문 시 큐에서 해당 노드를 삭제하고 각 노드의 자식들을 차례로 큐에 넣어 큐가 빌 때까지 반복된다.

 

위의 트리에서 레벨 순서 순회를 할 경우

 

a -> c -> d -> h -> r -> x -> l

 

의 순서로 노드를 방문하게 된다.

 

 

void levelOrder(Node*nd) {
		queue<Node*>q;
		q.push(root);

		while (!q.empty()) {
			Node*cur = q.front();
			q.pop();
			cout << cur->data << " ";
			for (auto childs: cur->child) {
				q.push(childs);
			}
		}
}