[Programmers] 13. 기본 자료구조: 트리 (Tree) (2): 이진 트리의 연산 구현

illstandtall·2021년 4월 29일

programmers python 이진 트리 자료구조 트리 트리 순회

Programmers dev course

목록 보기

14/34

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

자료구조 5-2. 이진 트리

이진 트리의 연산

size(): 현재 트리에 포함되어 있는 노드의 수를 구합니다.
depth(): 현재 트리의 깊이(또는 높이; height)를 구합니다.
traversal(): 현재 트리의 모든 노드를 방문합니다.
방문하는 방법은 뒤에서 다시 언급하겠습니다.

이진트리의 연산 구현 0. 초기 Class

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

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

이진 트리의 연산 구현 1. size()

이진 트리의 크기는 재귀적인 방법으로 구할 수 있습니다.
왼쪽 서브 트리의 크기 + 오른쪽 서브트리의 크기 + 자신(1)의 방법으로 구할 수 있습니다.
BinaryTree.size()에서는 Node.size()를 호출하고,
Node.size()에서는 재귀적인 호출이 일어납니다.

# Node.size()
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

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

이진 트리의 연산 구현 2. depth()

이진 트리의 깊이 또한 재귀적인 방법으로 구할 수 있습니다.
왼쪽 서브 트리의 깊이와 오른쪽 서브 트리의 깊이 중 더 큰 것에 자기 자신(1)을 더하는 방법으로 구할 수 있습니다.
BinaryTree.depth()에서는 Node.depth()를 호출하고,
Node.depth()에서는 재귀적인 호출이 일어납니다.

# Node.depth()
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
    
# BinaryTree.depth()
def depth(self):
    if self.root:
        return self.root.depth()
    else:
        return 0

이진 트리의 연산 구현 3. travasal()

- 깊이 우선 순회 (Depth First Traversal)

중위 순회 (in-order Traversal): LDR
1. L: 왼쪽 자식 노드를 먼저 방문합니다.
2. D: 더이상 방문할 왼쪽 자식 노드가 없으면, 현재 노드를 방문합니다.
3. R: 그 후, 오른쪽 자식 노드를 방문합니다.
전위 순회 (pre-order Traversal): DLR
1. D: 현재 노드를 먼저 방문합니다.
2. L: 그 후, 왼쪽 자식 노드를 방문합니다.
3. R: 더이상 방문할 왼쪽 자식 노드가 없으면, 오른쪽 자식 노드를 방문합니다.
후위 순회 (post-order Traversal): LRD
1. L: 왼쪽 자식 노드를 먼저 방문합니다.
2. R: 더이상 방문할 왼쪽 자식 노드가 없으면 오른쪽 자식 노드를 방문합니다.
3. D: 그 후, 현재 노드를 방문합니다.

- 깊이 우선 순회 code 구현

BinaryTree Class에서는 Node Class의 순회를 호출하고,
Node Class에서는 재귀적인 호출이 일어납니다.

### Node Class의 순회

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


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


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

### BinaryTree Class의 순회

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


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


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

- 넓이 우선 순회 (Bredth First Traversal)

재귀적 방법이 적절하지 않습니다.
수준이 낮은 노드를 우선으로 방문합니다.
같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문합니다.
왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문합니다.

루트 노드를 큐에 집어 넣고 시작합니다.
큐에서 노드를 꺼내 방문하고 모든 자식을 큐에 집어넣습니다.
2번 과정을 큐가 빌 때까지 반복합니다.

- 넓이 우선 순회 code 구현

넓이 우선 순회에서는 배열로 구현한 큐가 이용됩니다.

import ArrayQueue

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