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

안녕하세요~
깜빡 졸았다가 깨어보니 아침이라는 루트를 밟고 있는 테슬라입니다.
오늘은 이진 트리를 운행하는 방식에 대하여 알아볼까합니다...

음 트리를 운행한다에 대해서 말씀드릴께요.
트리를 운행한다가 무슨 말인고 하니 트리의 각 노드들을 한번씩은 방문한다는
모든 노드를 한번씩 지나가는 경우를 말합니다.

그럼 왜 운행해야 할까요?
음 트리에 있는 정보를 적절하게 골고루 모두모두 사용하려고 입니다.
또는 트리 안에 있는 정보를 찾고자 할 때도 쭉쭉 찾아볼 필요도 있고,
(트리가 이진 검색 트리처럼 정리가 안 되있을 수도 있지요.)
순서대로 자료들을 이동시켜야 할 때 (예컨데 트리를 리스트 형식으로 바꾼다던지...)
뭐 이럴 경우 한번씩은 확인 해야 하니까요.

음 그럼 이제 운행법에 대해서 알아볼까요?

이런 트리가 있다고 해봐요
이 3개의 노드를 각각 읽는 방법은 무엇이 있을까요?
음 ,A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A 6개 입니다. 3!이군요.
물론 이때는 방향을 고려하지 않은 아무렇게나 운행되는 운행방법입니다.
그럼 한쪽 방향으로만 운행한다고 치면 절반인 3개가 나오겠죠?
음 이때 여기서는 A노드인 루트노드가 언제 방문되는가에 따라서
전위운행법(preorder), 중위운행법(inorder), 후위운행법(postorder)
이 3가지로 나누어집니다.
루트노드가 먼저 방문되면 전위운행, 가운데에 방문되면 중위운행, 마지막에 방문되면 후위운행이라고 합니다.
자 그럼 각각에 대해 알아볼까요?

우선 전위운행법(preorder traversal)은
아까 말했듯이 어떤 노드가 자신의 노드(자기 관점으로 보면 루트노드지요?)를 먼저 방문하고,
왼쪽 서브트리를 방문하고, 그 후에 오른쪽 서브트리를 방문합니다.
음 왜 아까는 노드라고 해놓고 이번에는 서브트리라는 말이 나왔냐고 물으신다면,
아까의 예는 노드가 3개밖에 없는 작은 트리였지만, 이제부터 예를 들려는 트리는 그것보다는 레벨이 높은
트리에 대해서 말씀을 드리기 위해서 입니다. 뭐 그렇다고 크게 바뀌는건...없겠지요...?

요론 트리가 있다고 치죠.
A노드에서 자신을 읽고 B노드로 향하겠죠? 자 B노드 입장에선 밑에 노드 두개를 끼고 있지요?
그럼 B노드에서도 전위운행법을 사용해야 하기 때문에 B 다음은 D노드, D노드 다음 노드는 없으므로,
B노드의 오른쪽 노드인 E노드, 자 A노드의 왼쪽 노드들은 전위운행법으로 한번씩 방문했지요?
그럼 A노드의 오른쪽 노드 C을 방문하고나서는 아까 B노드 방문했을때처럼 F->G 노드를 방문하게 되겠지요?

그러니까 제 말은 루트에서 왼쪽 노드로 향하더라도 그 왼쪽노드에 부수적으로 노드들을 달고 있다면,
그 노드들도 전위운행법으로 방문을 하고 오른쪽 노드로 가야겠지요. 이때에는 왼쪽노드가 아~까 위쪽에서
예를 제시한 노드 3개짜리 트리에서 루트의 역할을 하게 되는 것이지요.

방향으로 나타내면

요런 모양이 나옵니다.
음 한가지 사용 예로 전위표기식(prefix)이라는 산술표기식을 들 수 있는데요.

요런 모양의 트리가 있다고 하지요
일반적으로 우리들이 쓰는 중위표기법(infix)로 나타내면 (A+B)-(C/D)의 식이 나옵니다.
요 식을 전위표기식(prefix)로 나타내면

이런식으로 운행하고 결론적으로 -+AB/CD라는 전위표기식이 나옵니다.

으아 원래 중위운행법과 후위운행법에 대해서 같이 쓰려고 했지만...중요한 약속이 있어서요
죄송하지만 중위운행법과 후위운행법은 다음 번에 쓰도록 하겠습니다.
아, 그리고 레벨운행법이라는 것에 대해서도 그때 설명드릴께요.
그럼 안녕히 계세요~

아! 수정할 부분 있으면 말씀해주세요~