[트리순회] 중위탐색(inorder)

저번에는 트리탐색방법 중 하나인 전위탐색을 살펴봤었는데

https://coding-juuwon2.tistory.com/441

[트리순회] 전위탐색

 

 

 

 

이번에는 중위탐색을 살펴볼것이다!!

중위탐색(inorder) 순서

1. 왼쪽 서브트리를 inorder
2. 루트 노드 방문 
3. 오른쪽 서브트리를 inorder

 

 

위의 트리를 중위탐색을 이용해서 탐색해볼건데

 

탐색방식과 상관없이 시작은 항상 루트노드부터 시작하게된다.

루트노드인 A노드부터 시작을 하더라도 중위탐색의 순서에따라 왼쪽 서브트리를 먼저 방문하게된다.

그래서 왼쪽 서브트리인 B노드에 대해서 먼저 inorder를 수행해야하는데, B노드는 B를 루트로하는 서브트리를 또 구성하고 있으므로, B를 기준으로 inorder를 재귀적으로 먼저 실행하면서 B노드의 왼쪽 서브트리인 D노드를 먼저 방문하게 된다.

근데 여기서 D는 왼쪽 자식노드가 없기때문에 자기자신인 루트노드를 방문하게된다.

따라서 이 트리에서 제일 처음 방문하는 노드는 D가된다.

제일처음 D노드 방문

 

 

D노드를 기준으로 왼쪽 자식노드는 존재하지 않고, 루트노드인 D도 방문했으니깐

오른쪽 자식노드를 탐색할 차례다.

따라서 H노드를 방문한다.

H노드는 리프노드이자, 자신 H를 루트로하는 원소가 하나뿐인 서브트리를 구성한다고 볼 수 있다.

따라서 왼쪽 서브트리에 대한 탐색할것이 없기때문에 바로 종료가되고, 루트노드인 자기 자신노드(H노드)를 방문하고,

오른쪽 서브트리도 없기때문에 이렇게 바로 종료가된다.

 

H노드 방문

 

 

 

여기까지 했을때 D노드를 기준으로 한 서브트리에서 오른쪽 서브트리 중위탐색도 끝난상태다.

그리고 D노드는 B노드를 기준으로하는 왼쪽 서브트리였기 때문에, B노드를 기준으로 왼쪽 서브트리의 중위탐색도 종료되게된다.

따라서 이제 루트노드인 B노드를 방문하게 된다

 

B노드 방문

 

 

이제 B노드의 오른쪽 자식노드인 E노드를 방문한다.

E노드 역시 자식이 없고, 자신을 루트로하는 원소가 하나뿐인 서브트리이므로, 바로 탐색이 종료되게 된다.

E노드 방문

 

 

E노드가 종료되서 지금까지 B노드를 루트로하는 서브트리에 대한 탐색이 모두 종료되었고,

다시 A노드로 돌아가게되는데, B노드는 A노드의 왼쪽 서브트리였는데 이미 중위탐색이 종료된 상태이기때문에 

루트노드인 A를 방문하게된다.

 

A노드 방문

 

 

이제 A노드를 기준으로 오른쪽 서브트리를 방문해야되므로 C노드로 이동하게되고,

C노드의 왼쪽 자식인 F노드를 중위탐색해야한다.

근데 F노드도 자식을 갖고있기때문에 F노드를 기준으로 왼쪽의 서브트리부터 탐색해야하기 떄문에 I를 탐색한다.

I는 자식노드가 없기때문에 바로 종료된다.

 

I노드 방문

 

 

 

이제 왼쪽서브트리까지 중위탐색을 했으므로, 루트노드를 방문해야되기 때문에 F노드를 방문한다.

F노드 방문

 

 

 

이제 F를 중심으로 오른쪽 서브트리인 J를 방문하게된다.

역시 J는 자식노드가 없기때문에 탐색을 종료한다.

J노드 방문

 

 

여기까지하면, F노드를 기준으로하는 서브트리의 탐색이 종료되고

동시에 C노드를 기준으로 왼쪽 서브트리의 탐색도 종료되게 된다.

따라서 그 다음엔 F의 루트노드인 C를 방문하게 된다.

 

C노드 방문

 

 

 

이제 오른쪽 서브트리를 방문해야되기때문에 G노드를 방문해준다. G노드는 왼쪽 서브트리가 없기때문에 건너뛰고 루트노트인 자기자신 G노드를 방문한다. 그리고 오른쪽 서브트리를 방문해야되기때문에 K로 이동한다.

K노드는 서브트리가 없기때문에 루트노드인 자기자신 K노드를 방문하게되면서 탐색이 종료된다!!

 

 

G, K 노드 방문 <최종결과>

 

K노드가 종료되면서 G노드의 오른쪽 서브트리의 탐색이 끝나게 되고,

G노드가 종료되면서 C노드의 오른쪽 서브트리에 대한 탐색이 끝나게되고,

C노드가 종료되면서 A노드의 오른쪽 서브트리에 대한 탐색 또한 끝나게 된다.

 

이렇게 최종적으로 모든 노드에대해서 방문이 완료되었다.

따라서 결과적으로 D - H - B - E - A - I - F - J - C - G - K의 순서로 중위탐색이 이루어지는것을 확인해볼 수 있다.