이진 트리(Binary Tree) - 이진 트리의 운행 2

안녕하세요~
이진 트리의 운행 두번째 시간이 돌아왔습니다.
오늘 아침까지 NAT씨께서 침묵상태에 빠졌어서 오늘에야 글을 쓰게 되었군요.
(으아 임시 저장된 줄 알고 막 닫았다가 다시 쓰게되네요...흠흠)

오늘 다룰 부분은 중위운행법과 후위운행법, 레벨운행법인데요.
모두 그렇게 어려운 내용이 아니기 때문에 저번 전위운행법을 이해하셨던 분이라면 충분히 이해하실 수 있으실겁니다. 자 그럼 시작할게요.

음 저번 포스트를 생각해보죠.

이런 트리가 있다고 생각해보죠~
이 트리의 경우 전위 운행법으로 운행했을때 어땠나요?
A노드가 먼저 방문되고, A노드의 왼쪽인 B노드, A노드의 오른쪽인 C 순으로 방문되었지요?

이런식으로 A->B->C 이지요?



그렇다면 지금 이야기할 중위 운행법(inorder traversal)은 어떨까요?
중위운행법은 특정한 노드를 기점으로 해서 그 노드의 왼쪽 서브트리를 먼저 방문하고, 그 다음 자기 자신,
그 후에 그 노드의 오른쪽 서브트리를 방문하게됩니다.

예를 들어 아까 예제를 가지고 한다면
A노드가 A노드의 왼쪽서브트리를 방문한 후에 방문됩니다. 즉, 이름에 걸맞게 A노드는 중간에 방문되는거지요.
그리고 그 후에 A노드의 오른쪽 서브트리를 방문하는 거지요. 위에 있는 예를 가지고 표현한다면

요런 식으로 방문되는 겁니다. 뭐 순서는 B->A->C순이겠네요.

그럼 좀 더 큰 예제를 가지고 생각해볼까요?

저번에 예제로 썼던 트리입니다.
이 트리를 가지고 예를 들어봐요.
우선 A노드의 왼쪽서브트리인 B노드부터 시작을 하려고 하는데...
어익후 B노드도 서브트리를 가지고 있네요.
그럼 B노드의 왼쪽서브트리인 D노드부터 시작해야겠네요.
D노드에는 서브트리가 없으니까 맨 왼쪽에 있는 D노드를 방문하며 시작됩니다.
그 다음엔 D노드의 부모노드인 B노드를 방문하겠지요?
그리고 B노드의 오른쪽서브트리인 E노드로 가겠지요?
A노드의 왼쪽 서브트리는 모두 방문 했습니다.
이제 A노드가 방문 되겠군요. 그 다음 오른쪽 서브트리를 방문하겠지요?
이때 오른쪽 서브트리를 생각해보죠.
C노드는 서브트리를 가지고 있습니다. 때문에 C노드의 왼쪽 서브트리인 F노드를 먼저 방문합니다.
그 후 C노드를 방문하고 C노드의 오른쪽  서브트리인 G노드가 방문됩니다.

순서대로 나열하면 D -> B -> E -> A -> F -> C -> G 순서겠죠?



다음으로 후위운행법(postorder traversal)을 설명드릴게요.
음 전위랑 중위를 보면 후위는 어떤식으로 운영될지 예상 되시죠?
후위운행법은 특정한 노드에서 자신의 왼쪽서브트리를 모두 방문하고, 그 다음에는 오른쪽 서브트리, 마지막에야 자기 자신이 방문되는 것입니다.

이런 식인거지요.

아까 큰 트리를 예로 들어보죠.

우선 A노드의 왼쪽서브트리인 B노드부터 시작을 하려고 하는데...
어익후 B노드도 서브트리를 가지고 있네요.
그럼 B노드의 왼쪽서브트리인 D노드부터 시작해야겠네요.
D노드를 방문하고 나서 B노드의 오른쪽서브트리인 E노드를 방문합니다.
이때 E노드에는 서브트리가 없으므로, 왼쪽, 오른쪽 서브트리들을 모두 방문한 부모노드인 B노드가 방문됩니다.
A의 왼쪽 서브트리들은 모두 방문했습니다. A의 오른쪽 서브트리인 C서브트리 차례군요.
C서브트리에는 F와 G노드를 가지고 있습니다. 때문에 C노드의 왼쪽 서브트리인 F노드로 향하는군요.
F노드는 서브트리를 가지지 않으므로 F노드가 방문 됩니다.
F노드 방문후 C노드의 오른쪽 서브트리인 G노드로 가는데 마찬가지로 서브트리가 없으므로 G노드를 방문합니다.
이제 C의 왼쪽, 오른쪽 서브트리를 모두 방문 했으므로 C노드를 방문합니다.
이제 A노드의 왼쪽 오른쪽 서브트리를 모두 방문했네요 마지막에야 A노드가 방문됩니다.

순서대로 쓰면 D -> E -> B -> F -> G -> C -> A 순이 되겠군요.


저번과 같이 표기식을 사용 예로 들어볼까요?

중위표기식(infix)는

A+B-C/D 순이겠죠?

후위표기식(postfix)으로는

AB+CD/-순 이겠네요.

마지막으로 그 세가지 운행법과 다른 방식인 레벨운행법(levelorder traversal)이 있습니다.
이건 쉬워요. 이름 그대로 레벨 순서대로 방문하는 겁니다. 높은 레벨에서 낮은 레벨 순이지요.

최상위 레벨인 A노드를 방문합니다.
다음 레벨인 B노드와 C노드를 방문합니다.
마지막 레벨인 D노드와 E노드, F노드와 G노드를 방문합니다.
순서대로 쓰면 A -> B -> C -> D -> E -> F -> G순입니다.
음 레벨운행법은 그래프에서의 너비우선검색과 비슷하게 운행된다고 할 수있습니다.



음 오늘은 세가지 운행법을 알아봤는데요. 오타나 실수는 지적해주세요~
만약 틀린 부분이 있다면 그 부분도 지적해 주심 감사하겠습니다.