이진트리 순회(DFS)

이진트리의 순회 이진트리에 속하는 모드 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미 이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후의의 3가지 방법이 있다. 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V 왼쪽 서브 트리 방문을 L 오른쪽 서브트리 방문을 R 루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회 루트를 서브 트리 방문 후에 방문하면 후위 순회가 된다. 이진트리에서 각각의 서브 트리 역시 이진트리이다. 전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다. -> 문제의 구조는 같고 크기만 작아지는 경우 -> 순환(재귀) 적용 전위 순회 루트 노드를 방문한다. 왼쪽 서브 트리를 방문한다. 오른쪽 서브트리를 방문한다. 중위 순회 왼쪽 서브트리를 방문한다. 루트 노드를 방문한다. 오른쪽 서...

원문링크 : 이진트리 순회(DFS)