1. 이진 트리 순회 (Binary Tree Traversal)#
이진 트리는 비선형 자료구조이기 때문에 순차적으로 방문할 수 없다. 탐색 방법에 따라 노드를 방문하는 순서가 달라지는데, 이진 트리 순회 방법은 전위(Preorder), 중위(Inorder), 후위(Postorder) 순회 세 가지로 분류된다. 루트 노드의 자식 노드는 서브 트리의 루트 노드로 볼 수 있다. 이런 재귀적 특성을 갖는 구조 때문에 재귀적 방법의 순회는 매우 쉽게 구현할 수 있다. 재귀적 방법이 아닌 반복문을 사용하는 반복적(Iterative) 순회도 가능하다. 트리 순회를 공부하면서 재귀적 순회를 구현 완료 후 반복적 순회 구현을 시도했는데, 간단할 줄 알았지만 생각 이상으로 정말 어려웠다(후위 순회 구현은 실패). 방법을 알고난 지금은 단순하다고 느끼지만 모르면 떠올리기 쉽지 않은 내용인 것 같아 이 글에 정리한다.
2. 전위 순회 (Preorder Traversal)#
전위 순회의 탐색 순서는 루트 노드를 먼저 방문 후 서브 트리를 탐색하는 것이다. 코드에선 왼쪽 서브트리 탐색 후 오른쪽 서브트리를 탐색한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| void IterPreorder()
{
if (!root_) return;
Stack<Node*> s;
s.Push(root_);
// 스택에 방문할 노드가 있으면 반복
while (!s.IsEmpty())
{
// 스택에서 노드를 꺼낸다
Node* cur = s.Top();
s.Pop();
// 루트 노드를 방문
Visit(cur);
// 오른쪽 자식노드 있으면 스택에 넣는다
if (cur->right)
{
s.Push(cur->right);
}
// 왼쪽 자식노드 있으면 스택에 넣는다
if (cur->left)
{
s.Push(cur->left);
}
}
}
|
3. 중위 순회 (Inorder Traversal)#
탐색 순서는 왼쪽 서브트리 → 루트 노드 → 오른쪽 서브트리이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| void IterInorder()
{
if (!root_) return;
Stack<Node*> s;
Node* cur = root_;
// cur이 nullptr고 스택이 비면 반복 종료
while (cur || !s.IsEmpty())
{
// cur이 nullptr가 아니면 스택에 cur 노드를 넣고
// 왼쪽 자식 노드로 내려간다
while (cur)
{
s.Push(cur);
cur = cur->left;
}
// cur이 nullptr면 스택에서 노드를 꺼낸 후 그 노드로 이동
cur = s.Top();
s.Pop();
// cur의 왼쪽 서브트리는 탐색이 끝났으므로 cur을 방문
Visit(cur);
// cur의 오른쪽 서브트리 탐색을 위해 오른쪽 자식 노드로 이동
cur = cur->right;
}
}
|
4. 후위 순회 (Postorder Traversal)#
순회 순서는 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 노드이다. 스택을 두 개 사용한다. 이런 식으로 해결하는 것은 처음에 떠올리지 못 했다. 단순하지만 기발한 방법인 것 같다. 첫 번째 반복에선 방문하지 않고 s2 스택에 모든 노드를 넣는다. 두 번째 반복에선 s2에서 노드를 꺼내면서 방문한다. s1의 역할은 s2에 노드가 올바른 순서로 들어가도록 하는 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| void IterPostorder()
{
if (!root_) return;
Stack<Node*> s1, s2;
s1.Push(root_);
// s1에 노드가 있으면 반복
while (!s1.IsEmpty())
{
// s1에 있는 노드를 꺼내서 s2에 넣는다
s2.Push(s1.Top());
s1.Pop();
// s2에 방금 넣은 노드가 cur
Node* cur = s2.Top();
// cur의 왼쪽 자식 노드가 있으면 s1에 넣는다
if (cur->left)
{
s1.Push(cur->left);
}
// cur의 오른쪽 자식 노드가 있으면 s1에 넣는다
if (cur->right)
{
s1.Push(cur->right);
}
}
// s2에 노드가 있으면 노드를 꺼내서 방문
while (!s2.IsEmpty())
{
Visit(s2.Top());
s2.Pop();
}
}
|