이진 트리(Binary Tree)

1. 이진 트리

• 이진 트리는 차수가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리를 말한다.
• 이진트리의 레벨 i에서 최대 노드의 수는 2^(i-1) 이다.
• 이진트리에서 단말노드(Terminal Node) 수가 n0, 차수가 2인 노드수가 n2라 할때 n0 = n2 + 1 이 된다.

 

2. 트리의 운행법

• 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법이라한다.
• 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.

 

• Preorder 운행 : Root → Left → Right  (A, B, C)
• Inorder 운행 : Left → Root → Right  (B, A, C)
• Postorder 운행 : Left → Right → Root  (B, C, A)

 

 

 

3. Preorder 운행법

이미지 출처 : 클릭!

 

1. 루트를 시작으로 왼쪽으로 쭉 써내려간다.

2. 내려갈 곳이 없다면 해당 노드의 기준 오른쪽 노드를 써준다.

3. 오른쪽 노드를 썻다면 위로 올라가준다.

4. 만약 오른쪽 노드가 리프노드가 있다면 다시 왼쪽으로 쭉 써내려간다. 

5. 그렇게 제일 오른쪽 노드까지 써주면 완성.

 

4. Inorder 운행법

이미지 출처 : 클릭!

1. 그림을 위치를 보면서 맨 아래 왼쪽부터 맨 아래 오른쪽까지 순서대로 써주면 된다.

 

5. Postorder 운행법

이미지 출처 : 클릭!

1. 맨 아래 왼쪽을 시작으로 해당노드의 부모노드를 기준으로 왼쪽 오른쪽 노드를 써주고 부모노드를 쓴다.

2. 다 썼다면 마지막의 부모노드의 오른쪽 노드도 똑같이 써준다.

3. 이 규칙을 계속 하며 마지막은 루트노드로 끝난다.

 

6. 수식의 표기법

이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다.

 

• 전위 표기법(Prefix) : +AB 
• 중위 표기법(Infix) : A+B
• 후위 표기법(Postfix) : AB+

 

<여기서 Tip!>

이 전위 중위 후위 표기법은 운행법과 똑같다.중위가 우리가 흔히 사용하는 표기이다.

 

 

 

읽어주셔서 감사합니다!

정처기 화이팅!