트리 순회 편집하기 (부분)

==순회의 종류==
트리 순회는 크게 '''[[깊이 우선 탐색|깊이 우선 탐색(DFS, Depth-First Search)]]'''과 '''[[너비 우선 탐색|너비 우선 탐색(BFS, Breadth-First Search)]]'''으로 구분된다.
===[[깊이 우선 탐색|깊이 우선 탐색 (DFS)]]===
DFS는 트리의 한쪽 끝까지 탐색한 후 백트래킹하는 방식으로, 다음 세 가지 방법이 있다.
====전위 순회 (Preorder Traversal) ====
*순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
*수식 표현: V → L → R
'''슈도코드:'''<pre>
PreorderTraversal(node):
    if node is not null:
        visit(node)
        PreorderTraversal(node.left)
        PreorderTraversal(node.right)
</pre>'''파이썬 코드:'''<syntaxhighlight lang="python">
def preorder_traversal(node):
    if node is not None:
        print(node.value, end=" ")
        preorder_traversal(node.left)
        preorder_traversal(node.right)
</syntaxhighlight>
====중위 순회 (Inorder Traversal)====
*순서: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
*수식 표현: L → V → R
'''슈도코드:'''<pre>
InorderTraversal(node):
    if node is not null:
        InorderTraversal(node.left)
        visit(node)
        InorderTraversal(node.right)
</pre>'''파이썬 코드:'''<syntaxhighlight lang="python">
def inorder_traversal(node):
    if node is not None:
        inorder_traversal(node.left)
        print(node.value, end=" ")
        inorder_traversal(node.right)
</syntaxhighlight>
====후위 순회 (Postorder Traversal)====
*순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
*수식 표현: L → R → V
'''슈도코드:'''<pre>
PostorderTraversal(node):
    if node is not null:
        PostorderTraversal(node.left)
        PostorderTraversal(node.right)
        visit(node)
</pre>'''파이썬 코드:'''<syntaxhighlight lang="python">
def postorder_traversal(node):
    if node is not None:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value, end=" ")
</syntaxhighlight>
===[[너비 우선 탐색|너비 우선 탐색 (BFS)]]===
BFS는 루트에서 시작하여 같은 깊이의 노드를 먼저 방문하는 방식이다.
====레벨 순회 (Level Order Traversal)====
*순서: 레벨(깊이) 순서대로 방문
'''슈도코드:'''<pre>
LevelOrderTraversal(root):
    queue = empty queue
    queue.enqueue(root)
    
    while queue is not empty:
        node = queue.dequeue()
        visit(node)
        if node.left is not null:
            queue.enqueue(node.left)
        if node.right is not null:
            queue.enqueue(node.right)
</pre>'''파이썬 코드:'''<syntaxhighlight lang="python">
from collections import deque

def level_order_traversal(root):
    if root is None:
        return
    
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=" ")
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
</syntaxhighlight>