[7] Tree, 트리

👇🏻 오늘도 여김없이 오늘의 짤

네... 저는 다이어트 중이거든여...

---

무는 뿌리를 바탕으로 가지를 통해 잎이 난다. 나무에 영양분이 공급되는 경로(루트)가 트리(Tree)의 자료구조 형태와 비슷하다.

 

 

오른쪽 그림이 트리 자료구조를 시각화한 것이다.

알파벳 트리(오른쪽 그림)에서 화살표가 양분이 뻗어나가는 통로(즉, 가지)라고 하면 나무의 뿌리는 A가 될 것이다. 트리에서는 이것을 루트 노드(root node, 노드는 연결리스트에서 등장한 개념과 동일)라고 한다. 영양분이 뻗어나가는 통로를 간선(edge)라고 하고 영양분이 최종적으로 전달되는 D,E,C를 리프 노드(leaf node)라고 한다. 

 

 

컴퓨터가 정하기 좋아하는 것 중 하나가 관계를 정의하는 것이다. 트리에서는 edge(화살표)를 기준으로 시작하는 노드가 부모, 가리키는 노드가 자식 노드가 된다. 이것과 연관되어 트리의 구성요소를 정리해보자.

 

트리(Tree) : 노드(데이터를 저장하는 곳)와 간선(edge, 노드들을 연결해줌)으로 이루어진 자료구조
  부모 노드  하나 이상의 자식이 있는 노드
  자식 노드  부모 노드가 있는 노드
  루트 노드  부모 노드가 없는 최상위 노드
  리프 노드  자식이 없는 노드

 

트리는 한 노드에 자식이 무조건 0,1,2명만 있어야 하는 것은 아니다. 3,4,5명도 가능하다. 

하지만 보통 자식이 0~2명인 노드로 이루어진 트리를 주로 다루는데 이를 이진트리(Binary Tree)라고 한다. 

 

이제, 이진트리를 구현해보겠다. 먼저 우리는 언제나와 같이 노드를 찍어내는 틀을 만들어 주어야 한다. 

 

노드의 구성 요소

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

 

노드를 생성했으면 이진트리를 찍어내는 틀을 만들 수 있다. 이진트리의 가장 윗 부분인 루트 노드를 None으로 초기화해주면 된다. 

 

class BinaryTree():
    def __init__(self):
        self.root = None

 

이제 앞서 봤던 트리를 예로 들어 노드를 찍어내고 이진트리에 넣은 후 순서에 맞게 연결해보자.

 

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

A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')

binary_tree = BinaryTree()

binary_tree.root = A
A.left = B
A.right = C

B.left = D
B.right = E

 

이렇게 트리를 만든 후에, 우리는 항상 결과를 눈으로 보고 싶어 한다. 하지만 여기서 약간의 의견들이 충돌할 수 있다. 

트리를 순회하는 방법은 자그마치 3가지나 있기 때문이다.

 

트리 순회(Tree Traversal) 
전위 순회 (Preorder Traversal) 
중위 순회 (Inorder Traversal)
후위 순회 (Postorder Traversal)

 

전위 순회(Preorder Traversal) 

루트에서 시작 -> (루트) 왼쪽 자식노드 트리 전위 순회 -> (루트) 오른쪽 자식노드 트리 전위 순회

부모 노드의 왼쪽 자식 노드를 최우선으로 방문하고 방문이 끝날 경우 오른쪽 자식 노드를 방문한다.

 

 

루트에서 시작해 왼쪽에 있는 자식 노드를 차례로 먼저 방문한 후에 오른쪽 노드를 차례로 거슬러 올라가 방문한다. 

 

def preorderTraversal(node):
    if node:
        print(node.data, end=' ')
        preorderTraversal(node.left)
        preorderTraversal(node.right)
            
preorderTraversal(binary_tree.root)

# 결과 출력
A B D E C

 

중위 순회(Inorder Traversal)

가장 왼쪽에 위치한 노드에서 시작 -> 부모 노드 -> 오른쪽 자식 노드  

 

 

def inorderTraversal(node):
    if node:
        inorderTraversal(node.left)
        print(node.data, end=' ')
        inorderTraversal(node.right)
       
inorderTraversal(binary_tree.root)

# 출력 결과
D B E A C

 

후위 순회(Postorder Traversal)

가장 왼쪽에 위치한 노드에서 시작 -> 오른쪽 자식 노드 -> 부모 노드

 

 

루트누드를 가장 마지막에 순회한다. 

 

def postorderTraversal(node):
    if node:
        postorderTraversal(node.left)
        postorderTraversal(node.right)
        print(node.data, end=' ')
       
postorderTraversal(binary_tree.root)

# 출력 결과
D E B C A

 

다음 포스트에는 이진 탐색 트리(BST)에 대해 알아보도록 하겠다.

 

끝 !

 

https://github.com/Seeun-Lim/Data-Structure/blob/main/BinaryTree.py

GitHub - Seeun-Lim/Data-Structure