[2024.02.20] Tree 1

트리

• 비선형 구조
• 원소들 간에 1:n 관계를 가지는 자료구조
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조

트리 - 정의

• 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다
  노드 중 최상위 노드를 루트라고 한다
  나머지 노드들은 n개의 분리 집합 T1, ... TN으로 분리될 수 있다.

• 이들 T1, ... TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라고 한다.

트리 - 용어 정리

• 노드: 트리의 원소
• 간선: 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
• 루트 노드: 트리의 시작 노드
• 형제 노드: 같은 부모 노드의 자식 노드들
• 조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 자손 노드: 서브 트리에 있는 하위 레벨 노드들
• 차수
  노드의 차수: 노드에 연결된 자식 노드의 수
  트리의 차수: 트리에 있는 노드의 차수 중에서 가장 큰 값
  단말 노드(리프 노드): 차수가 0인 노드. 자식 노드가 없는 노드
• 높이
  노드의 높이: 루트에서 노드에 이르는 간선의 수. 노드의 레벨
  트리의 높이: 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨

이진 트리

• 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리
  왼쪽 자식 노드 / 오른쪽 자식 노드
  

이진 트리 - 특성

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

포화 이진 트리 (Full Binary Tree)

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

완전 이진 트리 (Complete Binary Tree)

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

편향 이진 트리 (Skewed Binary Tree)

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
  왼쪽 편향 이진 트리 / 오른쪽 편향 이진 트리
  (선형 자료구조와 다를 게 없어 트리의 장점을 살리지 못함. 비효율적)

순회

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

순회: 트리의 노드들을 체계적으로 방문하는 것

• 3가지의 기본적인 순회방법

1. 전위순회(preorder traversal): VLR
   부모노드 방문 후, 자식노드를 좌, 우 순서로 방문
2. 중위 순회(inorder traversal): LVR
   왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문
3. 후위 순회(postorder traversal): LRV
   자식노드를 좌우 순서로 방문한 후, 부모노드로 방문

전위 순회

• 수행 방법
  1) 현재 노드 n을 방문하여 처리 -> V
  2) 현재 노드 n의 왼쪽 서브트리로 이동 -> L
  3) 현재 노드 n의 오른족 서브트리로 이동 -> R

def preorder_traverse(T): 		#전위 순회
	if T:				  		#T is not None
    	visit(T)				#print(T.item)
        preorder_traverse(T_left)
        preorder_traverse(T_right)

중위 순회

• 수행 방법
  1) 현재 노드 n의 왼쪽 서브트리로 이동 -> L
  2) 현재 노드 n을 방문하여 처리 -> V
  3) 현재 노드 n의 오른족 서브트리로 이동 -> R

def inorder_traverse(T): 		#중위 순회
	if T:				 		#T is not None
        inorder_traverse(T_left)
        visit(T)		 		#print(T.item)
        inorder_traverse(T_right)

후위 순회

• 수행 방법
  1) 현재 노드 n의 왼쪽 서브트리로 이동 -> L
  2) 현재 노드 n의 오른족 서브트리로 이동 -> R
  3) 현재 노드 n을 방문하여 처리 -> V

def postorder_traverse(T): 		#중위 순회
	if T:				 		#T is not None
        postorder_traverse(T_left)
        postorder_traverse(T_right)
        visit(T)		 		#print(T.item)

이진 트리 표현 1

• 배열을 이용한 이진 트리의 표현 => 노드 번호를 배열의 인덱스로 사용
• 노드 번호의 성질
  노드 번호가 i인 노드의 부모 노드 번호: ⌊i/2⌋
  노드 번호가 i인 노드의 왼쪽 자식 노드 번호: 2i
  노드 번호가 i인 노드의 오른쪽 자식 노드 번호: 2i+1
  레벨 n의 노드 번호 시작 번호: 2^n

이진 트리 표현 2

• 부모 번호를 인덱스로 자식 번호를 저장
  

• 자식 번호를 인덱스로 부모 번호를 저장
  

• 루트 찾기 / 조상 찾기
  

전위 순회 연습문제

#첫 줄에는 트리의 정점의 총 수 V가 주어진다. 그 다음 줄에는 V-1개 간선이 나열된다.
#간선은 그것을 이루는 두 정점으로 표기된다. 간선은 항상 부모-자식 순서로 표기된다.
#간선은 부모 정점 번호가 작은 것부터 나열되고, 부모 정점이 동일하다면 자식 정점 번호가 작은 것부터 나열된다.

#아래 이진 트리 표현에 대해 전위 순회하여 정점의 번호를 출력하라.
'''
13
1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13
'''

#전위 순회
def pre_order(T):
    if T:
        print(T, end=' ')
        pre_order(left[T])
        pre_order(right[T])

N = int(input())
E = N-1
arr = list(map(int, input().split()))
left = [0]*(N+1) #부모를 인덱스로 왼쪽 자식번호 저장
right = [0]*(N+1) #부모를 인덱스로 오른쪽 자식번호 저장
par = [0]*(N+1) #자식을 인덱스로 부모 저장

for i in range(E):
    p, c = arr[i*2], arr[i*2+1]
    if left[p] == 0:
        left[p] = c
    else:
        right[p] = c
    par[c] = p

c = N
while par[c] != 0: #부모가 있으면
    c = par[c] #부모를 새로운 자식으로 두고
root = c #더이상 부모가 없으면 root
pre_order(root)