사이클이 없는 연결 그래프
- 비선형 구조
- 원소들 간에 1:n 관계를 가지는 자료구조
- 원소들 간에 계층관계를 가지는 계층형 자료구조
- 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조
- 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족
- 노드 중 최상위 노드: 루트(root)
- 나머지 노드들은 n(>=0)개의 분리 집합 T1, ... , TN으로 분리 가능
- T1, ..., TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 함
노드: 트리의 원소
간선: 노드를 연결하는 선, 부모와 자식 노드 연결
루트 노드: 트리의 시작 노드
형제 노드: 같은 부모 노드의 자식 노드들
조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
자손 노드: 서브 트리에 있는 하위 레벨의 노드들
1. 현재 노드 n을 방문하여 처리 V
2. 현재 노드 n의 왼쪽 서브트리로 이동 L
- 왼쪽 찍고 출력, 돌아오면서 왼쪽이 없으면 오른쪽 보고 찍어옴
3. 현재 노드 n의 오른쪽 서브트리로 이동 R
- 왼쪽 찍고 출력, 돌아오면서 왼쪽이 없으면 오른쪽 보고 찍어옴
1. 현재 노드 n을 방문, 처리는 x, 왼쪽 서브트리로 이동 L
2. 왼쪽으로 가고, 없으면 돌아와서 본인 찍다가 부모 노드 찍고 V
3. 오른쪽 서브트리로 가서 왼쪽 가다가 없으면 본인 찍으며 돌아옴 R
1. 왼쪽 서브트리 자식들부터 보고 L
- 왼쪽, 오른쪽 보다가 값 없으면 돌아오면서 찍고
2. 오른쪽 서브트리 자식들 보고 R
- 값 없으면 돌아오면서 찍고
3. 부모 노드 본인에게 돌아옴 V
모든 자녀 노드가 둘 이하인 트리
0. 이진 트리 종류
- 완전 이진 트리
→ 마지막 레벨을 제외한 모든 레벨은 꽉 차있어야 한다
→ 마지막 레벨 노드는 왼쪽부터 채워줘야한다
- 포화 이진 트리
→ 모든 레벨이 꽉 차있다
1. 순회 방법 : 데이터를 어떻게 찾아갈 것인가? 무슨 데이터를 먼저 볼 것인가?
2. 트리 저장 방법 : 순회를 구현하기 위해서 실제 코드에서 트리를 어떻게 저장했는가?
# 0. 이진 트리 저장
# - 일차원 배열 저장
# 1. 연결 리스트로 저장 - 개발용
class TreeNode:
def __init__(selft, value):
self.value = value
self.left = None
self.right = None
# 삽입 함수
def insert(self, childNode):
# 왼쪽 자식이 없을 경우
if not self.left:
self.left = childNode
return
# 오른쪽 자식이 없을 경우
if not self.right:
self.right = childNode
return
return
# 전위 순회
def preorder(self):
# 아무 것도 없는 트리를 조회
if self != None:
print(self.value, end=' ')
# 왼쪽이 있다면 왼쪽 자식 조회
if self.left:
self.left.preorder()
# 오른쪽이 있다면 오른쪽 자식 조회
if self.right:
self.right.preorder()
arr = [1, 2, 1, 3, 2, 4, 3, 5, 3, 6]
# 이진 트리 만들기
nodes = [TreeNode(i) for i in range(0, 14)]
for i in range(0, len(arr), 2):
parentNode = arr[i]
childNode = arr[i+1]
nodes[parentNode].insert(nodes[childNode])
nodes[1].preorder()
arr = [1, 2, 1, 3, 2, 4, 3, 5, 3, 6]
# 이진 트리 만들기
nodes = [[] for _ in range(0, 14)]
for i in range(0, len(arr), 2):
parentNode = arr[i]
childNode = arr[i + 1]
nodes[parentNode].append(childNode)
# 자식이 더 이상 없단 걸 표현하기 위해 None 삽입
for li in nodes:
for _ in range(len(li), 2):
li.append(None)
# 전위 순회
def preorder(nodeNumber):
if nodeNumber == None:
return
print(nodeNumber, end=' ')
preorder(nodes[nodeNumber][0])
preorder(nodes[nodeNumber][1])
추후, 그림 정리해보기