5-1) 트리 - 완전 트리와 정 트리, 순회, 표현

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

완전 이진 트리(Complete binary tree)

 

마지막 줄을 제외한 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고, 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리이다.

 

정 이진 트리(Full binary tree)

모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고, 모든 잎이 같은 레벨에 있는 트리이다. (모든 노드가 0 개 또는 2개의 자식 노드만을 가짐)

 

트리 순회

전위 순회 (Pre order traversal)

1) 루트 노드에서 시작하여 2) 왼쪽 자식 노드에 갔다가 3) 오른쪽 자식 노드로 가는 순회 방법. 다른 모든 노드를 지나기 전에 루트 노드를 방문하기 때문에 전위(Pre order) 순회라고 한다.

 

중위 순회 (In order traversal)

왼쪽 자식 노드에서 시작하여 루트 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법.

 

후위 순회 (Post order traversal)

왼쪽 자식 노드에서 시작하여 오른쪽 자식 노드에 갔다가 루트 노드로 가는 순회 방법.

 

너비 우선 선회/레벨 순서 순회 (Breadth first traversal/level order traversal)

가장 위에 있는 노드에서 시작하여 왼쪽에서 오른쪽으로 가는 순회 방법. 일반적으로는 사용되지 않는다.

 

표현식

중위 표기식: 2 * 3
후위 표기식: 2 3 *

 

 

 

중위 표기식: (((22 / 11) + 3) * (6 + 5)) - 50
후위 표기식: 22 11 / 3 + 6 5 + * 50 -

 

 

중위 -> 후위표기법

결과: ABC*+DE/-