트리 운행법 해설 완결판.

2008년에 공부하고 간만에 다시 공부를 하는 정보처리기사. ㅋㅋㅋ

자격증이 있는데도 불구하고 다시 공부를해야하는 상황이 생겨서 공부하던중. 

트리오더를 공부하다가 쉽게 정리한것 같아 포스팅. 

자. 아래와 같은 트리가 있다고 가정하고. 진행합니다.

다들 책에서 보셨던대로. 순서는 아래와 같습니다. 

in order : left -> root -> right

pre order : root -> left -> right

post order : left -> right -> root

위의 트리로 각 방식대로 운행을 해보면.

 

결과는 이렇게 됩니다. 

in order     : D B A G E H C F

pre order   : A B D C E G H F

post order : D B G H E F C A

간단하게 해설을 드리자면. 

트리에서 어느 한곳으로 이동을 하던. 이동한 곳에 하위 노드가 있으면 운행법을 새롭게 적용하면 됩니다. 

in order 로 설명을 드리면,

운행법은 left -> root -> right 입니다.

1. left(B)로 왔는데 하위 노드가 있네요. 

   - 새롭게 시작합니다. left -> root -> right

     1. left(D)로 왔는데 없네요. 첫번재 search하는건 D 가 됩니다. 

     2. 다음번 순서는 root(B) 입니다. 두번째 search는 B.

     3. right 는 없네요. 패스. 

2. 다음번 순서는 root(A) 입니다. 세번째는 A.

3. right(C)로 갑니다. 

   - 하위노드가 있으니 다시 시작.

      1.  left(E)로 갑니다. 

         - 하위노드가 있으니 다시 시작.

             1. left(G)로 갑니다. 밑에 더 없으니. 네번째는 G.

             2. root(E) 가 이번 순서니, 다섯번째는 E.

             3. right(H) 가 이번 순서니, 여섯번째는 H.

     2. root(C) 가 순서니까, 일곱번째는 C.

     3. right(F) 가 순서니까, 여덟번째는 F.

어떤가요?  어려운가요? 흠...

쉽게 정리를 해본다고 해봤는데, 맘에 드셨으면 좋겠어요~ ㅎㅎㅎ

헷갈리신 분들은 제가 설명에 써놓은대로 1,2,3, 번으로 구분을 해서 적으면 좀 이해가 쉽지 않을까 생각이 드네요~ ^^*

그럼 다들 열공 하세요~ ^^