이진트리 (Binary Trees)

이진 트리의 추상적 자료구조

연산의 정의

• size(): 현재 트리에 포함되어 있는 노드의 수를 구함
• depth(): 현재 트리의 깊이 (또는 높이: height)를 구함
• traversal: 순회

이진 트리의 구현

노드 (Node)

• data/left/right를 가지고 있음
• Node
  • Data
  • Left Child
  • Right Child

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

• root node 지정

class BinaryTree:
	def __init__(self, r):
    	self.root = r

size()

• 재귀적인 방법으로 쉽게 구할 수 있다.
• root를 right/left subtree로 보면 root의 size는 left size() + right size() + 1
• 전체 이진 트리의 size() = left subtree의 size() + right subtree의 size() + 1 (자기 자신)

class Node:
	def size(self):
    	l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

class BinaryTree:
	def size(self):
    	if self.root:
        	return self.root.size()
        else:
        	return 0 

depth()

• 재귀적인 방법으로 쉽게 구할 수 있다.
• 전체 이진 트리의 depth() = left subtree의 depth()와 right subtree의 depth() 중 더 큰 것 + 1

이진 트리의 순회 (Traversal)

• 깊이 우선 순회 (depth first traversal)
  • 중위 순회 (in-order traversal):
    • 순회의 순서
      (1) left subtree
      (2) 자기 자신
      (3) right subtree
  • 전위 순회 (pre-order traversal):
    • 순회의 순서
      (1) 자기 자신
      (2) left subtree
      (3) right subtree
  • 후위 순회 (post-order traversal):
    • 순회의 순서
      (1) left subtree
      (2) right subtree
      (3) 자기 자신
• 넓이 우선 순회 (breadth first traversal)

이진 트리의 순회 - 넓이 우선 순회

• 원칙
  • 수준(level)이 낮은 노드를 우선으로 방문
  • 같은 수준의 노드들 사이에는,
    • 부모 노드의 방문 순서에 따라 방문
    • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문 (즉, 왼쪽에서 오른쪽으로 방문)
• 재귀적(recursive) 방법이 적합하지 않다.
• 한 노드를 방문 했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야 한다. -> 큐를 사용

• 알고리즘 설계
  • level 0(root) 노드를 큐에 넣는다.
  • 큐에서 노드를 하나씩 꺼내면서 처리
  • 노드를 방문 할 때 왼쪽, 오른쪽 노드를 하나씩 큐에 넣는다.
  • 큐에서 노드를 꺼내고 왼쪽, 오른쪽 노드는 큐에 넣어 준다.
  • 위 과정을 큐가 빌때 까지 반복

1. (초기화) traversal <- 빈 리스트, q <- 빈 큐
2. 빈 트리가 아니면, root node를 q에 추가 (enqueue)
3. q가 비어 있지 않은 동안
   3.1 node <- q 에서 원소를 추출 (dequeue)
   3.2 node를 방문
   3.3 node의 왼쪽, 오른쪽 자식 (있으면)들을 q에 추가
4. q가 빈 큐가 되면 모든 노드 방문 완료

• 중위 순회 구현

class Node:
	def inorder(self):
    	traversal = []
        if self.left:
        	traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
        	traversal += self.right.inorder()
        return traversal

class BinaryTree:
	def inorder(self):
    	if self.root:
        	return self.root.inorder()
        else: 
        	return []