자료구조 트리 순회 정리

이걸 처음에 배울 때 preorder는 VLR로 postorder는 LRV로 Inorder는 LVR로 배웠는데 도무지 이해가 되지 않았다.

근데 역시 코드로 보고 하나씩 적으니까 의미가 이해되었다.

Preorder 전위순회

전위순회는 하나씩 찍으면서 내려가는 것으로 바로 이해가 되었다.

---

void preorderTraversal(Node* root) {
    if (root != NULL) {
      printf("%d ", root->data); 
      preorderTraversal(root->left); 
      preorderTraversal(root->right);
	} 
}

Preorder에서는 recursion이 일어날 때마다 바로 방문이 일어나므로 바로 이해가 가능했다.
(+ab)

Postorder 후위순회

후위순회는 그냥 끝까지 내려갔다가 올라오면서 print한다고 생각했다.
즉, 자식 노드가 없으면 출력하는 것이다.

---

void postorderTraversal(Node* root) {
    if (root != NULL) {
      postorderTraversal(root->left); 
      postorderTraversal(root->right);
      printf("%d ", root->data);
	} 
}

Postorder에서는 recursion이 일어나서 tree의 먼저 끝까지 내려가고 나중에 출력하는 방식이다.
(ab+)

Inorder 중위순회

제일 이해가 되지 않았는데, root->right가 나오면 print한다고 생각하니까 바로 이해가 되었다!

---

void inorderTraversal(Node* root) {
    if (root != NULL) { 
      inorderTraversal(root->left);
      printf("%d ", root->data); 
      inorderTraversal(root->right);
	} 
}

Inorder는 출력 다음에 inorderTraversal(root->right)가 있으므로 R이 나오면 출력하는 방식으로 이해했다.
즉, inorderTraversal(root->right)가 실행되기 위해서는 printf("%d ", root->data)가 선행되어야 한다.
(a+b)

이걸 이해할 때 하노이탑처럼 생각하니까 이해가 편했다.

하노이탑의 구조가 중위순회와 같았다! 이걸 깨달았을 때는 기분이 정말 좋았다.

하노이탑 호출 순서 정리