24. 이진탐색트리 순회

이진탐색트리 순회

트리의 모든 노드를 한 번씩 방문하는 것을 의미한다.

중위 순회 : 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문한다. (이진탐색트리에서 오름차순으로 정렬됨)

전위 순회 : 루트, 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문한다.

후위 순회 : 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문한다.

즉, 루트를 언제 방문하느냐에 따라 순회의 종류가 결정된다.

---

중위 순회

void inorder(Nodepointer root){
    if (root == NULL) return;
    
    inorder(root->l_child);
    printf("%d ", root->key);
    inorder(root->r_child);
}

---

전위 순회

void preorder(Nodepointer root){
    if (root == NULL) return;
    
    printf("%d ", root->key);
    inorder(root->l_child);
    inorder(root->r_child);
}

---

후위 순회

void postorder(Nodepointer root){
    if (root == NULL) return;
    
    inorder(root->l_child);
    inorder(root->r_child);
    printf("%d ", root->key);
}

코드에서 나타나는 순회의 차이점은 printf()가 실행되기 전 방문하는 서브트리가 있는지 확인하면 된다.