[강의노트]이진트리의 운행법

(1) 이진트리의 표현

자식노드, 부모노드의 계산법.

3.3 이진트리의 운행법(Binary Traversal)

트리의 운행 : 트리의 모든 노드를 체계적으로 방문하는 방법.

-트리의 구조를 분석하거나 각 노드에 저장되어 있는 정보를 정해진 순서에 의해 읽어올 때 사용

 : 중순위, 전순위, 후순위, 레벨순위

전순위 (Preorder) : 루트가 노드 A고 이진트리가 있을때, 루트부터 방문하고, 왼쪽 부분트리를 Preorder로 운행하고, 오른쪽 부분트리를 마찬가지로 왼쪽부터 차례로 운행하는 방식.

노드A가 트리의 루트라는 사실만 알 수있음. 선형리스트가 아니기 때문.

Preorder는 언제나 루트부터 방문하게 되는 방식.

역순으로 값을 차례로 모두 push하고 값을 2개 pop하면서 연산자와 계산하고 다시 push and pop하면서 계산을 반복한다. (역순 Postfix notation 이라고 생각하면 간단함.)

중순위(Inoerder) : 왼쪽 부분트리를 먼저 방문하고 다른 상위루트를 방문, 최상단 루트 노드A 를 방문하고 또 오른쪽 부분트리를 또 왼쪽부터 먼저 방문하는 방식.

infix notation의 중위 표기법과 일치하는 결과를 보여줌

후순위(Postorder) : 왼쪽 최하단 노드부터 방문하고 상위로 올라가면서 A를 건너뛰고, 우측 트리도 왼쪽 최하단부터 방문한다. 그리고 가장 마지막으로 노드 A를 방문한다.

스택의 후위표기법(Postfix notation)과 일치하는 결과 -> 값은 push하고 연산자가 나왓을때 값 2개를 pop하여 연산한다.

이진트리의 운행에 대한 부분은 많은 연습을 통해서 트리를 보자마자 운행 순서가 바로 떠오를 수 있도록 하는것이 중요하다.

또한 프로그램 상에서 어떻게 트리의 운행을 구현할 수 있는지 생각해보는 것도 필요함. (스택 or 재귀)

레벨 순위 운행법 (Levelorder) : 작은 레벨부터 방문, 레벨이 같으면 왼쪽부터 방문. ABCDEF... 아주 쉬움

큐의 개념이 적용됨.

포리스트(Forest) : 1개 이상의 트리로 구성된 트리의 집합.

트리가 없으면 포리스트도 없다. 트리가 1개 이상이면 그때 트리의 루트는 포리스트의 루트가 된다. 

트리의 이진트리 변환한 BT가 왼쪽 오른쪽 부분트리가 된다.