이진 트리 (Binary Trees)

1 이진 트리 (Binary Trees) 란?

• 모든 노드의 차수가 2 이하인 트리
• 재귀적으로 정의할 수 있다
  • 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
    (단, 모든 서브트리가 이진 트리)
  • terminal 조건: 빈 트리(empty tree)도 이진트리다

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

2.1 연산의 정의

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

2.2 이진 트리의 구현

class Node:
		def __init__(self, item):
				self.data = item
				self.left = None
				self.right = None
				
		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
				
		def depth(self):
				l = self.left.depth() if self.left else 0
				r = self.right.depth() if self.right else 0
				return l + 1 if l > r else r + 1 

class BinaryTree:
		def __init__(self, r):
				self.root = r
		
		def size():
				if self.root:
						return self.root.size()
				else:
						return 0
		
		def depth(self):
				if self.root:
						return self.root.depth()
				else:
						return 0

3 이진 트리의 순회 (Traversal)

• 깊이 우선 순회 (depth first traversal)
  • 중위 순회 (in-order traversal)
  • 전위 순회 (pre-order traversal)
  • 후위 순회 (post-order traversal)
• 넓이 우선 순회 (BFS; Breadth First Traversal)

3.1 중위 순회 (in-order traversal)

순회(방문) 순서

1. left subtree
2. 자기 자신
3. right subtree

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

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

3.2 전위 순회 (pre-order traversal)

순회(방문) 순서

1. 자기 자신
2. left subtree
3. right subtree

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

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

3.3 후위 순회 (post-order traversal)

순회(방문) 순서

1. left subtree
2. right subtree
3. 자기 자신

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

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

3.4 넓이 우선 순회 (BFS; Breadth First Traversal)

• 원칙
  • level이 낮은 노드를 우선으로 방문
  • 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문하고 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문한다

→ 재귀적 방법은 적합하지 않다

• 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야 한다 → 큐를 이용하면 가능할 것이다
  • 방문한 노드의 왼쪽 자식과 오른쪽 자식을 큐에 넣으면 순서대로 기록할 수 있다

class ArrayQueue:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]

class Node:

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

class BinaryTree:

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

    def bft(self):
        traversal = []
        q = ArrayQueue()
        
        if self.root:
            q.enqueue(self.root)
        
            while not q.isEmpty():
                node = q.dequeue()
                traversal.append(node.data)

                if node.left:
                    q.enqueue(node.left)
                if node.right:
                    q.enqueue(node.right)
        
        return traversal