알고리즘 기초 - 이진 트리(Binary Tree)

반응형

▶ 이진 트리(Binary Tree)란?

이진 트리는 트리 자료구조 중에서 가장 간단한 형태의 트리입니다. 일반적인 이진 탐색 트리는 아래 그림과 같은 구조를 갖습니다.

모든 트리가 다 이진 트리는 아니며, 이진 탐색 트리는 아래와 같은 두 가지의 특징을 가집니다.

- 부모 노드보다 왼쪽 자식 노드가 작습니다.

- 부모 노드보다 오른쪽 자식 노드가 작습니다.

수식으로 표현하자면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립해야지만 이진 트리라고 할 수 있는 것입니다.

​

보통 이진 트리는 파이썬의 클래스를 이용해 표현합니다. 위 그림의 이진트리를 파이썬 코드를 이용해 나타내보겠습니다.

class Node:  ## 각 노드의 값과 왼쪽 노드와 오른쪽 노드의 정보 저장
    def __init__(self, item):
        self.item=item
        self.left=None
        self.right=None
        
class BinaryTree():  ## 각 노드의 값과 왼쪽 노드와 오른쪽 노드의 정보 저장
    def __init__(self):
        self.root=None

tree=BinaryTree()
n1=Node(30)
n2=Node(17)
n3=Node(48)
n4=Node(5)
n5=Node(23)
n6=Node(37)
n7=Node(50)

tree.root=n1
n1.left=n2
n1.right=n3
n2.left=n4
n2.right=n5
n3.left=n6
n3.right=n7

▶ 이진트리 순회하기

이진 트리의 각 노드를 순회하는 방법에는 전위순회, 중위순회, 후위순회, 레벨순회 총 4가지가 있습니다. 현재 노드 n을 언제 순회하는지, 순서에 따라 이름이 달라집니다.

​

 

● 전위순회(Preorder Traversal)

첫 번째는 전위순회입니다. 전위순회는 현재 노드 n방문 -> 현재 노드n의 왼쪽 서브트리 순회 -> 현재 노드n의 오른쪽 서브트리 순회 순으로 이루어집니다. 재귀를 이용해 구현할 수 있습니다. 이 방법으로 위 이진트리를 순회하면 30- 17- 5 -23- 48- 37- 50 순으로 순회하게 됩니다.

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

tree.preorder(tree.root) # 30 17 5 23 48 37 50

 

 

● 중위순회(Inorder Traversal)

두 번째는 중위순회입니다. 중위순회는 현재 노드n의 왼쪽 서브트리 순회 -> 현재 노드 n방문 -> 현재 노드n의 오른쪽 서브트리 순회 순으로 이루어집니다. 역시 재귀를 이용해 구현할 수 있습니다.이 방법으로 위 이진트리를 순회하면 17- 5- 23- 30 -48- 37 -50 순으로 순회하게 됩니다.

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)  # 오른쪽 서브트리 순회

tree.inorder(tree.root) # 17 5 23 30 48 37 50

 

 

● 후위순회(Postorder Traversal)

세 번째는 후위순회입니다. 후위순회는 현재 노드n의 왼쪽 서브트리 순회 -> 현재 노드n의 오른쪽 서브트리 순회 -> 현재 노드 n방문 순으로 이루어집니다. 이 방법 또한 재귀를 이용해 구현할 수 있습니다. 이 방법으로 위 이진트리를 순회하면 17- 5 -23 -48 -37- 50 -30 순으로 순회하게 됩니다.

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=' ')  # 현재 노드 방문

tree.postorder(tree.root) # 17 5 23 48 37 50 30

 

 

● 레벨순회(Level-order Traversal)

네 번째는 레벨 순회입니다. 레벨순회는 루트가 있는 곳부터 각 레벨마다 좌에서 우로 노드들을 방문해줍니다. 큐를 이용해 구현할 수 있습니다. 이 방법으로 위 이진트리를 순회하면 30 -17 -48 -5 -23 -37- 50 순으로 순회하게 됩니다.

def levelorder(self, root):
    q=[] # 리스트 구현(큐를 이용하여 구현)
    q.append(root)
    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) # 오른쪽 자식 큐에 삽입

tree.levelorder(tree.root) # 30 17 48 5 23 37 50

 

 

● 이진트리에서 검색하기

이진 트리내에 특정 값이 존재하는지 검색하고 싶을 때는 아래 코드를 이용하면 됩니다. key는 검색하고싶은 값입니다.

def search(self, key):
        node = self.root  # 루트에 주목
        while True:
            print(node.item)
            if node is None:  # 더 이상 진행할 수 없으면
                return -1  # 검색 실패
            if key == node.item:  # key와 노드 p의 키가 같으면
                return node.item  # 검색 성공
            elif key < node.item:  # key가 작으면
                node = node.left  # 왼쪽 서브 트리에서 검색
            else:  # key가 작으면
                node = node.right  # 오른쪽 서브 트리에서 검색

 

 

※ 트리의 높이 구하기

트리의 높이를 구하고 싶을때는 아래 코드를 이용하면 됩니다. 재귀함수를 이용해 구현할 수 있습니다!

def height(self, root):
    if root==None:
        return 0
    # 루트 노드를 기준으로 두 자식 노드의 높이 중 큰 높이 반환
    return max(self.height(root.left), self.height(root.right))+1

print(tree.height(tree.root)) # 3