[자료구조] 트리(Tree) - python

트리란 ?

비선형 자료구조로, 원소들간에 1:n 관계, 계층 관계를 가진다.

상위 원소에서 하위 원소로 확장되는 구조를 갖고 있다.

 

트리의 구성요소

출처 : https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

1. 노드(node) : 트리의 원소

2. 루트(root) : 트리의 시작 노드

3. 간선(edge) : 노드를 연결하는 선 / 부모 노드와 자식 노드를 연결한다.

4. 차수(degree) : 노드에 연결된 자식 노드의 수

5. 높이

      (1) 노드의 높이 : 루트에서 마지막 노드에 이르는 간선의 수 / 노드의 레벨

              -> B의 높이는 1 / F의 높이는 2

      (2) 트리의 높이 : 트리에 있는 노드의 높이 중 가장 큰 값 / 최대 레벨

              -> 트리의 높이 : 3

 

이진 트리

1. 이진 트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리

자식 노드 개수를 최대 2개로 제한하는 트리

높이가 h인 이진트리는 최소 h개의 노드를 가지며, 최대 2^h-1개의 노드를 가진다.

 

2. 포화 이진 트리

모든 레벨에 노트가 포화상태로 차 있는 이진 트리

이진 트리에서 높이의 최대치가 n일 때 가장 많이 존재할 수 있는 노드 수인 2^n-1 개를 모두 채운 트리.

 

3. 완전 이진 트리

노드가 왼쪽에서 오른쪽으로 빠짐없이 채워진 트리

레벨 1 부터 K-1까지는 노드가 다 채워져 있고, 마지막 레벨 k는 왼쪽부터 오른쪽 까지 노드가 순서대로 채워진 트리

 

4. 편향 이진 트리

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

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

 

 

 

 

트리를 배열로 표현하기

1. 이진 트리에 각 노드 번호를 부여한다

2. 부모 번호를 인덱스로 왼쪽 자식, 오른쪽 자식 번호를 저장한다

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

for i in range(E):
	p, c = arr[i*2], arr[i*2+1]
	if left[p] == 0:	# 왼쪽 부터 채우기
		left[p] = c
	else:				# left가 채워져 있으면 right에 채우기
		right[p] = c
	par[c] = p			# par 리스트에 자식 번호 인덱스에 부모 번호 넣기
    
root = 1
while par[root] != 0:
	root += 1

 

 

 

 

트리 순회

1. 전위 순회 ( VLR ) : 부모 -> 왼 자식 -> 오른 자식

# 전위순회
def preorder(i):
	if i:   # 존재하는 정점이면
		print(i, end=' ')
		preorder(left[i])
		preorder(right[i])
	return

 

2. 중위 순회 ( LVR ) : 왼 자식 -> 부모 -> 오른 자식

# 중위순회
def inorder(i):
	if i:   # 존재하는 정점이면
		inorder(left[i])
		print(i, end=' ')
		inorder(right[i])
	return

3. 후위 순회 ( LRV ) : 왼 자식 -> 오른 자식 -> 부모

# 후위순회
def postorder(i):
	if i:   # 존재하는 정점이면
		postorder(left[i])
		postorder(right[i])
		print(i, end=' ')
	return