3.7.1 Pre-Order Traversal(전위 순회)

CS - 3. Common Algorithms - 3.7 Tree - 3.7.1 Pre-Order Traversal

Tree Algorithms

💡A tree is non-linear and a hierarchical data structure consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

트리는 비선형적이며 노드 모음으로 구성된 계층적 데이터 구조로, 트리의 각 노드가 값과 다른 노드에 대한 참조 목록("자식")을 저장합니다.

 

Pre-Order Traversal

💡Pre-order traversal is a tree traversal algorithm that visits the root node first, then recursively traverses the left subtree, followed by the right subtree.

사전 순회 탐색(전위 순회)은 루트 노드를 먼저 방문한 다음 왼쪽 하위 트리를 재귀적으로 탐색한 다음 오른쪽 하위 트리를 탐색하는 트리 탐색 알고리즘입니다.

 

 

 

자료구조에서 Tree 를 다뤄봤습니다. 

https://parkpakrsu.tistory.com/336

Data structures (with python) - 8.Tree - 8.1 Binary Tree

이제 트리에 관련된 알고리즘을 알아보겠습니다.

http://www.ktword.co.kr/test/view/view.php?no=5560

Pre-Order Traversal 이란?

 

먼저 트리를 전위 순회 하는 알고리즘입니다. 前位巡廻 전위, Pre-order, 앞자리 부터 순회한다는 뜻입니다.

트리나 그래프를 순회하는 방법 중 하나로, 루트 노드를 가장 먼저 방문한 후, 왼쪽 서브트리, 그리고 오른쪽 서브트리 순으로 방문하는 방법을 말합니다. 이 방법은 트리의 모든 노드를 효과적으로 방문할 수 있어, 트리의 구조를 복사하거나 트리를 문자열로 변환하는 등의 작업을 수행할 때 주로 사용됩니다.

In Python

이제 파이썬을 사용해 Pre-Order Traversal을 어떻게 구현할 수 있는지 살펴보겠습니다.

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

def pre_order_traversal(node):
    if node is not None:
        print(node.value, end=" ")
        pre_order_traversal(node.left)
        pre_order_traversal(node.right)

 

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

pre_order_traversal(root) # 1 2 4 5 3 6 7

 

 

위의 그래프를 전위 순회 하면 이렇습니다.

1-2,3 에서 낮은 2번노드로 진입 (1-2),

2-4,5 에서 낮은노드 순서대로 2-4, 그다음 2-5, 더 내려갈 노드가 없으므로 되돌아갑니다.

1-3 진입 후 3-6,7 도 위와 마찬가지대로 탐색.

따라서 1,2,4,5,3,6,7 순서대로 탐색하게 됩니다.

 

 

 

 

참고

정보통신기술용어해설

http://www.ktword.co.kr/test/view/view.php?no=5560

트리 순회