테크니션

이진 트리(binary tree)

​

모든 노드들의 자식 노드가 두 개 이하인 트리를 의미한다

​

서브 트리가 두 개 이하기 때문에 서브 트리는 왼쪽 서브 트리와 오른쪽 서브 트리로 구분한다.

​

1.전위 순회(Preorder) :Root -left -right

1

2 3

​

2.중위 순회(Inorder) : left-root-right

2

1 3

​

3.후위 순회(Postorder) :left-right-root

3

1 2

숫자는 순회하는 순서이다. 이름이 다 그 이름 같고 영어로만 말해도 알아 들을수 있어야 하기 때문에

​

6개 의 명칭 및 순회방법이 서로 매칭이 되어야 한다

​

이 트리를 3가지 방법으로 순회해보자

​

1. 전위순회(PreOrder)

​

2 - (7 하위) - (5 하위)

​

순서로 순회한다

​

2번 7 하위를 쪼개보자

​

7 - 2 하위 -6하위

6 하위를 쪼개보자

6-5-11

​

---> 2 - (7 하위) - (5 하위)

: 2 - (7-(2)-(6-5-11)) - (5하위)

​

5 하위는 9 - 4 순서대로 간다

​

결론 : 2-7-2-6-5-11-5-9-4 [Preorder]

​

InOrder은 다음기회에

2.중위 순회(Inorder) : left-root-right

2

1 3

​

아래 트리를 순회해보자

​

첫번째 순회

​

2 - 7 - 6(하위)

​

6 하위는 -> 5-6-11

​

1차 완료 : 2-7-5-6-11

​

두번째 순회

(2-7-5-6-11) // 2 // 5 하위

​

5 하위는 제일 아래부터 시작한다.

4- 9 -?? 해당 노드가 없으면 다음 단계로 넘어간다

​

(2-7-5-6-11) // 2 // 4 -9 - 5

​

결론 : 2-7-5-6-11-2-4-9-5

​

3.후위 순회(Postorder) :left-right-root

3

1 2

이번에는 트리를 바꿔서 적용해보자

​

POST ORDER 첫번째 단계

​

D - ( E/H) - B

​

(E/H) 를 분석해보자

(E/H) --> H-E 순서가 된다

​

첫번째 단계 : D-H-E-B

​

두번째 단계

​

두번째 단계를 세부적으로 가보자

​

F - (G//I) - C

​

첫번째 단계 (E/H) 와 비슷한 케이스이다

​

F - I - G - C

​

결론 : D-H-E-B - F - I - G - C - A