17강/18강/19강: 트리(Trees) / 이진 트리(Binary Trees) / 넓이 우선 순회(breadth first traversal)

강의

"트리" 는 node와 edge를 이용하여 데이터의 배치 형태를 추상화한 자료구조 입니다.

 

노드의 종류

• Root node : 맨 위 시작 노드
• Leaf node : 맨 아래 마지막 노드
• Internal node : 그 외의 중간 노드
• Parent node : root node에 더 가까운 쪽의 노드
• Child node : leaf node에 더 가까운 쪽의 노드
• Sibling node : 같은 parent node를 갖는 내가 아닌 노드
• ancestor : parent node부터 root node까지 이어지는 모든 노드
• descendant node : child node부터 leaf node까지 이어지는 모든 노드

 

노드의 수준(level)은 root node를 0으로 시작하여 거쳐온 edge의 개수 입니다.

 

트리의 높이(height) / 깊이(depth)는 노드의 최대 수준 + 1 입니다.

 

부분 트리(Subtree)는 특정 노드를 root node로 지정하여 모든 descendant를 포함한 트리를 말합니다.

 

노드의 차수(Degree)는 subtree의 수로 child node로 이어진 edge의 수와 같습니다.

 

 

"이진 트리(Binary Tree)"는 모든 노드의 차수가 2 이하인 트리 입니다.

이진 트리는 재귀적으로 정의할 수 있습니다.

• empty tree
• root node + left subtree + right subtree

 

연산

• size() : 노드의 수
• depth() : 트리의 깊이
• traversal : 순회
  • 깊이 우선 순회(depth first traversal)
  • 넓이 우선 순회(breadth first traversal)

 

깊이 우선 순회 

1. 중위 순회(in-order traversal) : left subtree → root node → right subtree 반복

class Node:
	
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None
        
    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 __init__(self, r):
        self.root = r


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

2. 전위 순회(pre-order traversal) : root node → left subtree → right subtree 반복

3. 후위 순회(post-order traversal) : left subtree → right subtree → root node 반복

 

 

넓이 우선 순회

• 수준이 낮은 노드 우선 방문
• 같은 수준일 때, 부모 노드의 방문 순서에 따라 왼쪽 자식 노드부터 방문
• 나중에 방문할 노드의 순서대로 기록 필요

→ 재귀적 방법 부적절

→ 큐 이용

 

 

 

특수한 이진 트리

포화 이진 트리 (Full Binary Tree) : 모든 레벨의 노드들이 모두 채워져 있는 이진 트리 (height = k, node 개수 = \(2^k\)-1)

완전 이진 트리 (Complete Binary Tree)

완전 이진 트리

 

 

18강 실습: (1) 이진트리의 depth() 연산 구현

⭐ 이진트리의 재귀적 성질을 이용하여 left subtree, right subtree로 나누어서 구하는 문제!

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 max(l,r) + 1


class BinaryTree:

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

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


    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0


def solution(x):
    return 0

 

 

18강 실습: (2) 이진트리의 전위순회 연산 구현

class Node:

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


    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 __init__(self, r):
        self.root = r


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

 

 

18강 실습: (3) 이진트리의 후위순회 연산 구현

class Node:

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


    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 __init__(self, r):
        self.root = r


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

 

 

19강 실습: 이진트리의 넓이 우선 순회

⭐ queue와 traversal을 이용하여 순서와 방문 기록하여 푸는 문제!

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):
        visitQueue = ArrayQueue()
        
        treaversal = []
        
        if self.root:   # 빈 트리가 아닐 때
            visitQueue.enqueue(self.root)
        
        while visitQueue.isEmpty() == False:    #큐가 비어있지 않을 때
            node = visitQueue.dequeue()
            treaversal.append(node.data)
            
            if node.left:
                visitQueue.enqueue(node.left)
            if node.right:
                visitQueue.enqueue(node.right)
        
        return treaversal

def solution(x):
    return 0