[알고리즘] 순회(전위 순회, 중위 순회, 후위 순회)

이진탐색트리의 추가 부분 입니다.

[알고리즘] 이진탐색트리

 

1. 전위 순회 (Preorder Traversal)

함수내에서 재귀로 내려가기전 출력합니다. (두개의 서브트리 순회 전)

 

1. 현재 노드를 출력(처리).

2. 왼쪽 노드를 방문

3. 오른쪽 노드를 방문

전위 순회 탐색 순서 : 8 3 1 6 4 7 10 14 13

void BST_PreOrder(Node* tree, vector<int>& pre) // 전위순회
{
    if (tree == NULL) // 재귀함수는 항상 탈출조건이 위에있어야함
        return;
    pre.push_back(tree->data); // 출력
    BST_PreOrder(tree->leftChild, pre);
    BST_PreOrder(tree->rightChild, pre);
}

---

2. 중위 순회 (Inorder Traversal)

왼쪽 서브트리 순회를 끝내고 돌아온 후 출력 후 오른쪽 서브트리로 순회

이진 검색 트리를 "중위 순회" 한다면 순서대로 정렬되어 출력 할 수 있다!

얼마전 중위 순회와 같은 구조로 하노이탑을 배웠다!

 

1. 왼쪽 노드를 방문

2. 현재 노드를 출력(처리)

3. 오른쪽 노드를 방문

중위 순회 탐색 순서 : 1 3 4 6 7 8 10 13 14

void BST_InOrder(Node* tree, vector<int>& in) // 중위순회
{
    if (tree == NULL) // 재귀함수는 항상 탈출조건이 위에있어야함
        return;
    BST_PreOrder(tree->leftChild, in);
    in.push_back(tree->data); // 출력
    BST_PreOrder(tree->rightChild, in);
}

[알고리즘/C++]하노이탑알고리즘

---

3. 후위 순회 (Postorder Traversal)

왼쪽 서브트리 순회를 마친 뒤, 오른쪽 서브트리 순회까지 끝내고 출력 한다.

즉, 모든 순회를 마친뒤 출력

 

1. 왼쪽 노드를 방문

2. 오른쪽 노드를 방문

3. 현재 노드를 출력(처리)

후위 순회 탐색 순서 : 1 4 7 6 3 13 14 10 8

void BST_PostOrder(Node* tree, vector<int>& pos) // 후위순회
{
    if (tree == NULL) // 재귀함수는 항상 탈출조건이 위에있어야함
        return;
    BST_PreOrder(tree->leftChild, pos);
    BST_PreOrder(tree->rightChild, pos);
    pos.push_back(tree->data); // 출력
}