백준 5639 이진 검색 트리(linked list 활용) c++ [컴공과고씨]

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

 

문제 간단 정리

이진트리가 있음

- 노드의 왼쪽 서브트리에 있는 모든 노드의 값은 부모의 값보다 작음.

- 노드의 오른쪽 서브트리에 있는 모든 노드이 값은 부모의 값보다 큼.

 

이 이진 트리에서

전위 순회 -> 루트 - 왼쪽 - 오른쪽 방문 하며 출력.

후위 순회 -> 왼쪽 - 오른쪽 - 루트 방문 하며 출력.

인데 전위 순회 결과가 주어졌을 때

후위 순회한 결과를 한 줄에 하나씩 출력해라.

 

방문 순회 이해하기

이 방문 순회가 이해가 힘든 분들은 이렇게 이해하면 쉽습니다.

3줄 코드가 한 세트로 보시고

코드 구성은 루트에 출력코드가 나머지는 이동코드로 구성되어있다고 생각하시고

새로운 노드에 도착할 때마다 한 세트가 다시 시작된다. (마치 재귀 함수 처럼)

즉, 전위 순회는 cout -> 왼쪽이동 -> 오른쪽이동

     후위 순회는 왼쪽이동 -> 오른쪽이동 -> cout

 

문제 예시에서 전위 순회를 해봅시다.

cout -> left -> right를 기억하시고

노드 도착 cout -> 50출력 go left 30에 도착 다시 한 세트 시작 cout -> 30 다시 왼쪽 이동 

....... 해서 cout << 5 후 왼쪽 비어있고 오른쪽 비어있기 때문에 24 노드로 가면 

24노드는 go right가 남은 상태이기 때문에 go right 그럼 28에 도착 새로운 세트 코드 시작

28 출력 이런식인거죠

 

똑같이  후위 노드에 적용해보면

왼쪽 이동 30 도착 다시 왼쪽이동 24 도착 다시 왼쪽이동 5 도착

여기서 왼쪽 이동불가 오른쪽 이동 불가 cout << 5

24에서 go left 했었으니까 go right 그럼 28 도착 28에서 go left right 후 cout 

다시 24로 가면 go left go right 완료한 상태이기 때문에 cout << 24

이런식으로 반복됩니다.

여기까지 순회 내용이였고 이제 본론으로 들어가겠습니다.

참고로 전위 순회해서 나온 값을 새로운 트리에 넣어주면 똑같은 트리를 만들 수 있습니다.

 

문제 해결 방법

일단 저는 이진트리를 만드는 방법으로 문제를 해결하였습니다.

여기서 이진트리를 만드는 방법은 2가지가 있습니다. 

1. 배열을 이용한 방법

2. 링크드 리스트 (linked list)를 이용한 방법 (포인터를 쓸 수 있어야함)

저는 오랜만에 linked list도 다시 사용해볼겸 linked list로 만들어 보았습니다.

코드는 배열이 포인터도 안쓰고 간단하지만 말이죠.

어차피 원리는 같기 때문에 링크드 리스트로 풀 수 있으면 배열로는 더 쉽게 풀 수 있습니다.

그래서 배열로 트리를 구성하는 방법만 알려드리겠습니다.

 

배열 같은 경우는 루트 노드 index를 0으로 두고 왼쪽으로 갈 때는 2n+1로 하고 오른쪽으로 갈때는 2n+2로 구성해주면

이진트리를 쉽게 만들 수 있습니다. 

 

이렇게 트리를 구성한 뒤 전위 순회해서 나온 값을 트리에 넣어서 

똑같은 트리를 구성해준 후 해준 후 후위 순회를 해주면 됩니다.

 

1. 트리 만들기

* 포인터를 모르시는 분은 그냥 푸는 원리만 보고 트리를 배열로 구성하셔도 무방합니다.

자 linked list를 만들기 위해서 먼저 구조체를 선언해 줍니다. 여기서 구조체는 하나의 노드라고 보시면 됩니다.

구조체의 명은 노드 타입이고 안에는 노드의 값을 담는 int info 변수와 오른쪽, 왼쪽 노드를 가르키는 포인터 1개씩을 가지고 있습니다. 

그림으로 표현하면 이렇게 됩니다. 

하나의 직사각형이 하나의 노드가 되며 이 노드는 3개의 값을 가진다.

 

class tree 선언

tree 객체를 만들어 줍니다.

tree의 구성

1. NodeType* root (노드 타입을 가르키는 포인터)

2. enqueue(트리에 값을 푸쉬하는 함수)

3. 후위 탐색하는 함수 

이렇게 3개가 필요하겠죠. 트리의 초기 상태는 root가 null이기 때문에 생성자에 root=NULL을 추가해줍니다.

 

자 먼저 enqueue 함수를 구성해 봅시다.

이해는 a값을 넣는 다면 먼저 root 포인터 부터 시작합니다.

root 포인터가 0이라면 root 포인터가 가르키는 NodeType 노드를 생성한 후 왼쪽, 오른쪽 포인터에 NULL을 넣어주고

info에 a를 넣어주면 됩니다.

 

만약 NULL이 아니라면 다시 함수에 값을 비교하여 큰 값이면 오른쪽 포인터로 이동 아니면 왼쪽 포인터로 이동시키면

됩니다. 코드를 보시면

tree 클래스에서 enqeue를 해주면 insert 함수로 가고 

insert 함수에서 왼쪽 오른쪽 이동을 하다가 아무것도 가르키고 있지 않는 포인터에 도달하면 거기에

노드를 생성한 후 값을 저장합니다.

중요한것은 insert() 파라미터에 NodeType*& 레퍼런스가 붙는 것을 주의 하시면 됩니다.

&가 있어야 tr = new NodeType 한 것이 유지가 됩니다.

 

이렇게 하면 push  하는 함수는 끝났습니다. 이제 마지막으로 후위 순회하는 함수를 만들어 주면됩니다.

자 inorder 함수는 root 를 넣어주면 아까 위에서 설명했듯이 먼저 포인터가 비어있지 않다면 왼쪽으로 이동

그 다음 오른쪽으로 이동 값을 queue에 넣어줌. 이렇게 구성이 되고 왼쪽으로 이동이 되었다면 다시 함수를 실행해 주면됩니다. (재귀함수 처럼)

 

이해가 어렵다면 전체코드 보면서 이해하셔도 되고 아니면 배열로 짜셔도 무방합니다.

 

전체코드

#include <iostream>
#include <queue>
using namespace std;
struct NodeType{ // 하나의 노드를 구조체로 표현
    int info; // 노드의 값
    NodeType *right; // 노드의 오른쪽을 가르킴
    NodeType *left; // 노드의 왼쪽을 가르킴
};
void InOrder(NodeType* tr ,queue<int>& q){
    if(tr != NULL){ // 가르키는 포인터가 있으면
        InOrder(tr->left, q); // 왼쪽으로 이동 
        InOrder(tr->right, q); // 오른쪽으로 이동
        q.push(tr->info); // 값을 저장
    }
}
void insert(NodeType*& tr, int a){ // &를 붙여주어야 포인터가 노드를 생성하고 // 가르키고 있는 것이 유지가 됨.
    if(tr == NULL){ // 노드에 값이 없는 경우
        tr = new NodeType; // 새로운 노드를 생성해서 포인터로 연결
        tr->left = NULL; // 왼쪽 포인터 NULL
        tr->right = NULL; // 오른쪽 포인터 NULL
        tr->info = a; // 값 삽입
    }else if(a > tr->info){ // 넣을 값이 크다면
        insert(tr->right, a); // 오른쪽 포인터로 이동
    }else{
        insert(tr->left, a); // 왼쪽 포인터로 이동
    }
}
class tree{
    public:
        tree(){
            root = NULL; // 초기 tree 상태 root = NULL
        }
        void enqueue(int a){
            insert(root, a); // root pointer와 a를 넣어줌
        }
 
        void InOrderTree(queue<int>& q){
            InOrder(root, q);
        }
 
    private:
        NodeType *root;
};
int main(){
    ios::sync_with_stdio(false);
 
    queue<int> q; // 후위 순회한 값들을 저장할 큐
    tree t;
    int n;
    while(cin >> n){
        if(n == EOF)
            break;
        t.enqueue(n); // 전위 순회한 값을 트리에 넣음
    }
    t.InOrderTree(q);
    while(!q.empty()){
        cout << q.front() << '\n'; // 후위 순회 값 출력 
        q.pop();
    }
 
    return 0;
}