DFS(깊이우선탐색)기초 - 1. 이진트리 순회(깊이우선탐색)

이진 트리(Binary Tree)를 탐색하는 방법에는 크게 다음의 4가지가 있다.



전위순회(Preorder Traversal)

중위순회(Inorder Traversal)

후위순회(Postorder Traversal)

레벨순회(Levelorder Traversal) 또는 BFS(Breadth-First Search; 너비 우선 탐색)




레벨순회(;BFS)를 제외한 나머지 순회방식은

DFS(Depth-First Search; 깊이 우선 탐색)으로 분류할 수 있다.

전위순회(preorder traversal)

전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색

부모-왼쪽-오른쪽

중위순회(inorder traversal)

중위순회는 왼쪽 자식 노드를 탐색하고 , 루트 노드를 탐색하고 , 오른쪽 자식 노드를 탐색

왼쪽-부모-오른쪽

후위순회(postorder traversal)

후위순위는 왼쪽 자식 노드를 탐색하고 , 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색 왼쪽-오른쪽-부모

https://www.jiwon.me/binary-tree-traversal/

이진 트리 순회: 전위, 중위, 후위, 레벨