이진 트리(Binary Tree)

이진 트리

• 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리 : 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node)
• 이진 트리의 예

이진 트리

이진 트리 - 특성

• 레벨 i에서의 노드의 최대 개수는 2^i개
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1) - 1)개

이진 트리 - 종류

포화 이진 트리(Full Binary Tree)

• 모든 레벨에 노드가 포화상태로 차있는 이진 트리
• 높이가 h일 때, 노드의 개수가 (2^(h+1) - 1)인 이진 트리
• 높이가 3일 때 노드의 개수 : 2^(3+1) - 1 = 15개
• 루트를 1번으로 하여 2^(h+1) - 1까지 정해진 위치에 대한 노드 번호를 가짐

포화 이진 트리

완전 이진 트리(Complete Binary Tree)

• 높이가 h이고 노드 수가 n개일 때 (단, h+1 <= n <= 2^(h+1) - 1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리
• 예) 노드가 10개인 완전 이진 트리

완전 이진 트리

편향 이진 트리(Skewed Binary Tree)

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리

왼쪽 편향 이진 트리 / 오른쪽 편향 이진 트리

이진 트리 - 순회(traversal)

순회(traversal)

• 트리의 노드들을 체계적으로 방문하는 것
• 트리의 각 노드를 중복되지 않게 전부 방문(visit)하는 것을 말하는데 트리는 비선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없다. 따라서 특별한 방법이 필요하다.

순회 방법

순회 방법

1. 전위 순회(preorder traversal) : VLR

• 부모 노드 방문 후, 자식 노드를 좌→우 순서로 방문
• 수행 방법
  1. 현재 노드 n을 방문하여 처리한다. (V)
  2. 현재 노드 n의 왼쪽 서브트리로 이동한다. (L)
  3. 현재 노드 n의 오른쪽 서브트리로 이동한다. (R)

def preorder_traverse(T):	# 전위 순회
    if T:	# T가 유효한 노드면
        visit(T)
        preorder_traverse(T.left_child)
        preorder_traverse(T.right_child)

전위 순회

2. 중위 순회(inorder traversal) : LVR

• 왼쪽 자식 노드→부모노드→오른쪽 자식 노드 순으로 방문
• 수행 방법
  1. 현재 노드 n의 왼쪽 서브트리로 이동한다. (L)
  2. 현재 노드 n을 방문하여 처리한다. (V)
  3. 현재 노드 n의 오른쪽 서브트리로 이동한다. (R)

def inorder_traverse(T):	# 중위 순회
     if T:	# T가 유효한 노드면
         inorder_traverse(T.left_child)
         visit(T)
         inorder_traverse(T.right_child)

중위 순회

3. 후위 순회(postorder traversal) : LRV

• 자식 노드를 좌→우 순서로 방문 후, 부모 노드로 방문
• 수행 방법
  현재 노드 n의 왼쪽 서브트리로 이동한다. (L)
  현재 노드 n의 오른쪽 서브트리로 이동한다. (V)
  현재 노드 n을 방문하여 처리한다. (R)

 def post_traverse(T):	# 후위 순회
     if T:	# T가 유효한 노드면
         post_traverse(T.left_child)
         post_traverse(T.right_child)
         visit(T)

후위 순회

순회(traversal) 연습 문제

이진 트리 순회 연습문제

전위 순회 (preorder traversal)

• A - B - D - H - I - E - J - C - F - K - G - L - M

중위 순회 (inorder traversal)

• H - D - I - B - J - E - A - F - K - C - L - G - M

후위 순회 (postorder traversal)

• H - I - D - J - E - B - K - F - L - M - G - C - A

이진 트리의 표현

트리의 표현 - 연결리스트

1. 이진 트리에 각 노드 번호를 다음과 같이 부여(루트의 번호를 1로 함)

2. 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 (2^n)부터 (2^(n+1) - 1)까지 번호를 차례로 부여

이진 트리의 노드 번호

노드 번호의 성질

1. 노드 번호가 i인 노드의 부모 노드 번호 : floor(i/2)

2. 노드 번호가 i인 노드의 왼쪽 자식 노드 번호 : 2 * i

3. 노드 번호가 i인 노드의 오른쪽 자식 노드 번호 : 2 * i + 1

4. 레벨 n의 노드 시작 번호 : 2^n

노드 번호의 성질

인덱스 번호

- 노드 번호를 배열의 인덱스로 사용

- 레벨 I의 최대 노드 수 : 2^i

- 높이가 h인 이진 트리를 위한 배열의 크기 : 1 + 2 + 4  + 8 + .. + 2^i = 2^(h+1) - 1

노드 번호 - 인덱스

노드 번호 - 인덱스

배열을 이용한 이진 트리 표현의 단점

- 편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생

- 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경이 어려워 비효율적

트리의 표현 - 연결리스트

- 배열을 이용한 이진 트리의 단점을 보완하기 위해 연결리스트를 이용하여 트리를 표현할 수 있다. 

- 연결 자료구조를 이용한 이진트리의표현

- 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현

연결 리스트

수식 트리

• 수식을 표현하는 이진 트리
• 수식 이진 트리(Expression Binary Tree)라고 부르기도 함
• 연산자는 루트 노드이거나 가지 노드
• 피연산자는 모두 잎 노드

수식 트리의 순회

수식 이진 트리

• 중위 순회 : A / B * C  * D + E
• 후위 순회 : A B / C * D * E +
• 전위 순회 : + * * / A B C D E