트리 순회(Tree Traversal)
배열은 인덱스를 통해 모든 데이터를 접근할 수 있다. 연결 리스트의 경우도 처음부터 끝까지 링크를 통해 접근할 수 있다. 하지만 트리는 선형 자료구조가 아니기 때문에 트리를 선형 자료 구조와 같은 방법으로 접근할 수 없다. 그렇다면 트리 구조에서 모든 데이터를 보고 싶다면 어떻게 해야할까? 트리에서는 순회(traversal)를 통해 모든 노드들을 접근할 수 있다. 트리를 순회하는 방법은 노드를 방문하는 순서에 따라 전위(preorder), 중위(inorder), 후위(postorder), 레벨(level)로 나뉜다.
전위 순회(Preorder Traversal)
전위 순회(preorder traversal)는 루트 노드를 먼저 방문한 후 이 노드의 왼쪽 서브트리를 방문하고 더 이상 방문할 왼쪽 서브트리가 없으면 오른쪽 서브트리를 방문하는 방법이다.
전위 순회를 할 때는 노드를 방문하면 오른쪽 자식, 왼쪽 자식 순으로 스택에 push한다. 스택에 있는 노드가 pop되면서 방문을 하게되고 이 과정을 스택이 공백이 될때까지 반복한다. 위 그림을 예시로 방문 순서를 설명하겠다. A를 방문하면서 스택에는 C, B가 순서대로 들어간다. 이후 B를 pop하면서 방문하고 동시에 B의 자식 노드인 E, D를 순서대로 push한다. 그렇게 스택이 빌 때까지 반복하면 모든 노드를 방문하게 된다.
중위 순회(Inorder Traversal)
중위 순회(inorder traversal)는 왼쪽 자식을 갖지 않는 노드에 도달할 때까지 왼쪽 서브트리를 따라간다. 조건에 만족하는 노드를 찾으면 해당 노드를 방문하고 부모 노드를 방문한 후 오른쪽 노드로 넘어가 왼쪽 서브트리를 따라가는 재귀적인 순회를 한다. 오른쪽 서브트리가 존재하지 않으면 부모 노드를 방문하고 다시 오른쪽 노드의 왼쪽 서브트리를 따라가게 된다.
중위 순회는 왼쪽 자식을 갖지 않는 노드를 찾을 때까지 계속해서 왼쪽 서브트리를 따라간다. 이때 경로상에 있는 모든 노드들을 지나온 순서대로 스택에 push한다. 그림에서는 A, B, D순서로 거쳐가기 때문에 A, B가 스택에 순서대로 push된다. D노드는 왼쪽에 자식을 갖지 않기 때문에 D노드를 방문하고 2번에서 B를 pop하면서 방문 후 오른쪽 노드인 E를 push한다. E가 push되는 이유는 E가 왼쪽, 오른쪽 자식을 갖지 않는 말단 노드이기 때문이다. 이렇게 스택에 모든 요소들이 pop될때까지 중위 순회를 반복한다.
후위 순회(Postorder Traversal)
후위 순회(postorder traversal)는 왼쪽 서브트리의 모든 노드를 방문한 후, 오른쪽 서브트리를 모두 방문하고 마지막으로 루트 노드를 방문하는 방식으로 순회한다.
왼쪽 자식을 갖지 않는 노드를 찾을 때까지 왼쪽 서브트리를 따라간다. 이때 지나온 모든 노드들을 스택에 push한다. 조건에 만족하는 노드에 도달하면 스택에서 pop 을 하면서 노드를 방문한다. 이때 방문을 하면서 오른쪽 노드에 대한 후위 순회를 진행한다. 그림에서는 E가 마지막이기 때문에 E를 push하게 된다. 2번에서 E를 pop하면서 방문을 한다. 3번에서는 D, E의 부모노드인 B를 pop하면서 방문하게 된다. 이런 과정을 스택이 공백이 될 때까지 진행한다. 위 그림에서 D와 E, F는 바로 들어왔다가 빠지는 데이터이다.
레벨 순회(Level Traversal)
레벨 순회(preorder traversal)는 각 노드를 레벨 순서대로 방문하는 순회 방법이다. 루트 노드를 시작으로 같은 레벨에서는 왼쪽에서 오른쪽 순으로 방문을 하게 된다. 다른 순회 방법과는 다르게 레벨 순회는 원형 큐를 이용하여 표현한다.
레벨 순회는 루트 노드를 방문으로 시작한다. 루트 노드를 방문하면서 B, C를 차례대로 큐에 넣는다.. 다음 B를 방문하면서 B의 자식 노드인 D와 E를 큐에 넣고 B는 큐에서 꺼낸다. 이런 방식으로 큐가 공백이 될때까지 진행한다.
'자료구조' 카테고리의 다른 글
| 일반 트리에서 이진 트리로 변환 (0) | 2022.03.29 |
|---|---|
| 스레드 이진 트리(Threaded binary tree) (0) | 2022.03.03 |
| 트리(Tree) (0) | 2022.03.01 |
| 이중 연결 리스트(Doubly Linked List) (0) | 2022.02.25 |
| 원형 연결 리스트(Circular Linked List) (0) | 2022.02.25 |