[자료구조] Tree(트리)(Python)

* 개요

수학, 특히 그래프 이론에서 회로가 없는 연결된 무향의 그래프를 Tree(트리)라고 한다. 트리의 각 부분의 명칭과 용어는 다음과 같다.

트리는 항상 root 노드에서 시작된다. 루트 노드는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리 구성을 띤다. 레벨은 0부터 시작한다. 트리는 항상 단방향이기 때문에(단방향이 아니면 순환 참조가 발생하여 문제 발생) 간선의 화살표는 생략이 가능하다. 일반적으로 방향은 위에서 아래로 향한다.

• 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
• 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
• 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
• 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
• 리프 노드(leaf node/leaf): 루트 노드를 제외한 차수가 1인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.

* 트리 순회

트리 순회의 종류에는 대표적으로 4가지가 있다. 전위 순회, 중위 순회, 후위 순회, 레벨 순회가 있다. 해당 개념은 다음과 같다.

• 전위 순회(pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
• 중위 순회(in-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
• 후위 순회(post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.
• 레벨 순서 순회(level-order traversal): 너비 우선 순회(Breadth-First traversal)라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있다. BFS(너비 우선 탐색)과 동일.

 

* 파이썬으로 구현한 Tree(트리)

트리는 연결리스트로 쉽게 구현할 수 있다.

class Node :
    def __init__(self, data) :
        self.data = data
        self.left = None
        self.right = None
        
class Tree :
    def __init__(self) :
        self.root = None
    
    # 전위순회   
    def preOrder(self, node) :
        print(node.data, end = ' ')
        
        if node.left is not None :
            self.preOrder(node.left)
            
        if node.right is not None :
            self.preOrder(node.right)
    
    # 중위순회
    def inOrder(self, node) :
        if node.left is not None :
            self.inOrder(node.left)
                
        print(node.data, end = ' ')
        
        if node.right is not None :
            self.inOrder(node.right)
    
    # 후위순회
    def postOrder(self, node) :
        if node.left is not None :
            self.postOrder(node.left)
            
        if node.right is not None :
            self.postOrder(node.right)
        
        print(node.data, end = ' ')
        
node1 = Node('A')
node2 = Node('B')
node3 = Node('C')
node4 = Node('D')
node5 = Node('E')
node6 = Node('F')
node7 = Node('G')
node1.left = node2
node1.right = node3
node2.left = node4
node3.left = node5
node3.right = node6
node6.right = node7

t = Tree()
t.root = node1

t.preOrder(t.root) # A B D C E F G 
print()
t.inOrder(t.root) # D B A E C F G
print()
t.postOrder(t.root) # D B E G F C A

코드를 통해 연결한 트리의 형태는 다음과 같다.

전위 순회(루트, 왼쪽 자식, 오른쪽 자식 순)를 진행할 경우 A -> B -> D -> C -> E -> F -> G 순으로 노드를 순회한다.

중위 순회(왼쪽 자식, 루트, 오른쪽 자식 순)를 진행할 경우 D -> B -> A -> E -> C -> F -> G 순으로 노드를 순회한다.

후위 순회(왼쪽 자식, 오른쪽 자식, 루트 순)를 진행할 경우 D -> B -> E -> G -> F -> C -> A 순으로 노드를 순회한다.

레벨 순회(BFS)는 A -> B -> C -> D -> E -> F -> G으로 노드를 순회한다.