트리

• 노드(Node)와 에지(Edge)로 구성
• 노드는 자식을 가질 수 있다
• 맨 꼭대기에 있는 1번 노드를 루트(Root)라고 한다.

용어

• 노드(Node): 트리를 구성하는 각각의 요소
• 간선(Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선
• 깊이(Depth): 루트 노드에서 해당 노드까지 도달하는 데 사용하는 간선의 개수, 루트 노드의 깊이는 0
• 레벨(Level): 노드의 깊이+1
• 노드의 분지 수, 노드의 차수(Degree): 노드의 자식 수
• 트리의 분지 수, 트리의 차수(Degree of tree): 해당 트리 내 모든 노드의 분지 수 중 최댓값
• 높이(Height): 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수, 노드 중 가장 높이가 높은 노드의 높이를 트리의 높이라고 함
• 루트 노드(Root Node): 트리 구조에서 최상위에 있는 노드
• 단말 노드(Terminal Node, Leaf Node): 하위에 다른 노드가 연결되어 있지 않은 노드
• 내부 노드, 비단말 노드(Internal Node): 단말 노드를 제외한 모든 노드로 루트 노드를 포함
• 부모 노드(Parent Node): 부모 자식 관계에서 상위 계층에 있는 노드로, 상위 계층에 있을수록 노드의 깊이와 레벨이 낮음
• 자식 노드(Childe Node): 부모 자식 관계에서 하위 계층에 있는 노드
• 형제 노드: 부모가 동일한 노드
• 조상 노드: 한 노드의 부모노드부터 루트노드까지 가는 경로에 존재하는 모든 노드
• 후손 노드: 한 노드를 루트로 하는 서브트리에 있는 모든 노드

이진트리

• 모든 노드가 최대 두 개의 자식을 갖는 트리를 이진트리라고 한다. 이진트리는 깊이 h에 최대 2^(h-1)만큼 노드를 가질 수 있다.

파이썬을 사용한 이진트리 구현

노드 클래스 구현

class Node:
	def __init__(self, item):
    	self.item = item
        self.left = None
        self.right = None

각 노드 생성

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
n7 = Node(7)
n8 = Node(8)

각 노드를 엮기 위해 BinaryTree 클래스 만든다

class BinaryTree():
	def __init__(self): # 트리 생성
    	self.root = None

tree = BinaryTree()
tree.root = n1
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7
n4.left = n8

트리 순회

• 트리의 노드를 지정한 순서대로 방문하는 것을 말한다.

전위 순회 (Preorder)

• 자기 자신을 먼저 출력하고 자식 노드를 호출한다.
• 자기 자신 출력 -> 왼쪽 서브 트리 호출 -> 오른쪽 서브 트리 호출

# 전위 순회
def preorder(self, n):
	if n!= None:
    	print(n.item, '', end='') # 노드 방문
        if n.left:
        	self.preodrer(n.left) # 왼쪽 서브 트리 순회
        if n.right:
        	self.preodrer(n.right) # 오른쪽 서브 트리 순회

output: 1 2 4 8 5 3 6 7

후위 순회 (Postorder)

• 자기 자신 출력을 가장 나중에 한다.
• 왼쪽 서브 트리 호출 -> 오른쪽 서브 트리 호출 -> 자기 자신 출력

# 후위 순회
def postorder(self, n):
	if n!= None:
    	if n.left:
        	self.postorder(n.left)
        if n.right:
        	self.postorder(n.right)
        print(n.item, '', end='') # 노드 방문

output: 8 4 5 2 6 7 3 1

중위 순회 (Inorder)

• 자기 자신 출력이 중간에 있다
• 왼쪽 서브 트리 호출 -> 자기 자신 출력 -> 오른쪽 서브 트리 호출

# 중위 순회
def inorder(self, n):
	if n!= None:
    	if n.left:
        	self.inorder(n.left)
        print(n.item, '', end='') # 노드 방문
    if n.right:
    	self.inorder(n.right)

output: 8 4 2 5 1 6 3 7

레벨 순회 (Levelorder)

• 깊이(레벨) 단위로 출력

# 레벨 순회
def levelorder(self, n):
	q = []
    q.append(n)
    while q:
    	t = q.pop(0)
        print(t.item, '', end='')
        if t.left != None:
        	q.append(t.left)
        if t.right != None:
        	q.append(t.right)

output: 1 2 3 4 5 6 7 8