[TIL] 이진 트리 순회

 

트리 Tree 

노드들이 나무 가지처럼 연결된 비선형 계측적 자료 구조

 

트리 구조를 왜 사용하는가?

선형 데이터 구조로는 계층형 구조를 나타낼 수 없기 때문에 

트리의 구조는 '데이터 저장'의 의미보다는

'저장된 데이터를 더 효과적으로 탐색'하기 위해 사용한다 

 

트리의 구조 

출처 https://yoongrammer.tistory.com/68

노드 Node

트리를 구성하고 있는 기본 요소

노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있다 

간선 Edge

노드와 노드 간의 연결선

루트 노트 Root Node

트리 구조에서 부모가 없는 최상위 노드

부모 노드 Parent Node

자식 노드를 가진 노드

자식 노드 Child Node

부모 노드의 하위 노드 

형제 노드 Sibling Node

같은 부모를 가지는 노드

깊이 Depth

루트에서 어떤 노드까지의 간선 Edge 수

높이 Height

어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 Edge 수 

Level

루트에서 어떤 노드까지의 간선 Edge 수

Path

한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서 

 

이진 트리 Binary Tree

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조 
자식은 왼쪽 자식 (Left child) 과 오른쪽 자식 (Right child) 로 나눠진다 

 

이진 트리 순회

1. Preorder ; Root - L - R 순서

 

2. Inorder ; L - Root - R 순서

 

3. Postorder - L - R - Root 순서 

출처 https://m.blog.naver.com/leeinje66/221622228795

 

 

 

파이썬으로 구현한 이진 트리 

# 트리의 개별 노드 
class Node:

	# 노드 초기화 
	def __init__(self, item):
    	self.data = item
        self.left = None
        self.right = None

# 트리 전체를 관리하는 클래스
class BinaryTree:

	# 트리의 루트 노드 설정 
	def __init__(self, r):
    	self.root = r