Tree Traversal (3) 썸네일형 리스트형 108. Postorder Traversal 트리의 후위 순회(Postorder Traversal)는 노드의 서브트리를 차례로 방문한 다음 노드를 마지막으로 방문하는 순회 방법이다. 트리의 전위 순회, 중위 순회, 후위 순회 결과 중 두 가지를 알면 나머지 한 가지 순회 결과도 알아낼 수 있다. 앞에서 설명한 트리의 후위 순회 결과는 다음과 같다.$\text{I F B G A J C H E D}$ 구현은 다음과 같다.// 인접 리스트를 사용한 경우#importusing namespace std;vectorv, e[100005];void postorder_traversal(int prev, int node){ for(auto &p: e[node])if(p != prev)postorder_traversal(p); v.push_back(nod.. 107. Inorder Traversal 트리의 중위 순회(Inorder Traversal)는 노드의 왼쪽 서브트리를 먼저 방문한 다음 노드를 방문하고 노드의 오른쪽 서브트리들을 방문하는 순회 방법이다. 여기서 서브트리의 방향에 대한 내용이 등장하는데 이 방향은 단순히 트리의 구조를 나타내었을 때의 방향이라고 생각해도 무방하다. 만약 자식 노드가 $3$개 이상일 경우 서브트리들 중 하나를 왼쪽 서브트리로, 나머지를 오른쪽 서브트리로 간주한다. 하지만 그런 노드가 있는 트리에서는 서브트리의 방향이 별로 의미 없는 경우가 많기 때문에 일반적으로 중위 순회는 이진 트리에서 수행된다. 앞에서 설명한 트리의 중위 순회 결과는 다음과 같다.$\text{I G B F D A E J C H}$ 구현은 다음과 같다.// 인접 리스트를 사용한 경우#importu.. 106. Preorder Traversal 트리의 순회(Tree Traversal)는 루트 있는 트리에 존재하는 각각의 노드를 일정한 규칙에 따라 한 번씩 방문하는 과정을 의미한다. 일반적으로 트리의 순회는 모든 노드가 최대 두 개의 자식 노드를 갖는 이진 트리(Binary Tree) 구조에서 다루어지지만, 이진 트리가 아닌 트리에서도 순회를 할 수 있다. 순회는 루트 노드에서 시작하며 자식 노드에는 순서가 있다고 가정한다. 노드를 방문하는 규칙은 크게 세 가지가 있으며 규칙에 따라 트리 순회의 이름도 달라진다.트리의 전위 순회(Preorder Traversal)는 노드를 먼저 방문하고 각각의 자식 노드를 루트로 하는 서브트리를 차례로 방문하는 순회 방법이다. 다음과 같은 트리가 있을 때 전위 순회는 다음과 같은 순서로 진행된다.루트 노드 $\t.. 이전 1 다음
