3.7.2 In-Order Traversal(중위 순회)

CS - 3. Common Algorithms - 3.7 Tree - 3.7.2 In-Order Traversal

In-Order Traversal

💡In-order traversal is a tree traversal algorithm that visits the left subtree, the root, and then the right subtree. This is the most common way to traverse a binary search tree. It is also used to create a sorted list of nodes in a binary search tree.

중위 순회(Inorder Traversal)은 왼쪽 하위 트리, 루트, 오른쪽 하위 트리를 차례로 방문하는 트리 탐색 알고리즘입니다. 이진 검색 트리를 탐색하는 가장 일반적인 방법입니다. 또한 이진 검색 트리에서 정렬된 노드 목록을 만드는 데도 사용됩니다.

 

 

In-Order Traversal은 이진 트리를 순회하는 방법 중 하나로, 가장 보편적으로 사용되는 방법 중 하나입니다. 이 방법은 노드를 '왼쪽 자식 - 부모 - 오른쪽 자식' 순서로 방문하는 방식을 의미합니다. 이 방식을 사용하면 이진 탐색 트리의 경우 오름차순으로 노드를 출력할 수 있습니다.

 

 

In Python

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

def in_order_traversal(node):
    if node is not None:
        in_order_traversal(node.left)
        print(node.data, end=' ')
        in_order_traversal(node.right)

노드를 만들고, 함수를 설정해준다.

 

이런 그래프를 예시로 중위순차(inorder traversla)을 해보겠습니다.

 

 

 

 

함수의 동작 과정은 다음과 같습니다:

1. 루트 노드(1)에서 시작합니다.
2. 루트 노드의 왼쪽 자식노드(2)로 이동합니다.
3. 이동한 노드(2)가 왼쪽 자식노드(4)를 가지고 있으므로, 다시 왼쪽 자식노드(4)로 이동합니다.
4. 이동한 노드(4)는 더 이상 왼쪽 자식노드가 없으므로, 이 노드를 방문(출력)합니다.
5. 노드(4)는 오른쪽 자식노드도 없으므로, 이 노드의 부모 노드(2)로 돌아가서 이 노드를 방문(출력)합니다.
6. 이제 노드(2)의 오른쪽 자식노드(5)를 방문(출력)합니다.
7. 노드(2)의 모든 자식노드를 방문했으므로, 노드(2)의 부모 노드(1)로 돌아가서 이 노드를 방문(출력)합니다.
8. 마지막으로 노드(1)의 오른쪽 자식노드(3)를 방문(출력)합니다.

 

 

---(나중수정)

이거 이러면 재귀적으로 1에서 타고타고 들어가서 제일 아래의 자식노드에서 시작하는데

이러면 연산을 처음 1부터 pre-order 보다 과정이 더 있는것 아닌가??

왜 쓰는거지?