백준 5639 이진 검색 트리 C++

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

5639번: 이진 검색 트리

---

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

---

키의 중복이 없고, 이진검색트리이다. 전위 순회 결과가 주어졌을떄, 트리를 만드는 과정이 필요했다.

 

어떻게 이진 검색 트리를 만들어야하는가?

사실 이부분이 제일 중요한 것 같다. 

 

입력을 받을 떄마다, 트리를 새로 만들어주고, 이 트리와 루트를 비교하는 과정이 있다.

 

1)루트가 아직 NULL인 경우

이 경우 그냥 루트를 새로 만든 트리로 설정하면 끝이다.

만약 50을 넣는다고 하자. 이 경우 그냥 루트를 50으로 설정하면 끝난다.

 

2)루트보다 트리의 키 값이 작은 경우

 

만약 루트의 키 값이 50이고 새로 만든 트리의 키 값이 30이라고 가정해보자.

이 경우에서 나는 한 가지 경우만 생각했지만, 2의 경우에도 크게 2가지로 나뉘게 된다.

 

2-1) 루트의 왼쪽 노드가 존재하지 않는 경우

만약 50을 넣고, 키 값 30인 새로운 노드를 트리에 삽입해야 한다.

아까 50을 넣어두었을 떄, 50의 왼쪽은 NULL이기 떄문에, 루트의 왼쪽 자식으로 새로 만든 노드를 넣어준다.

 

2-2) 루트의 왼쪽 노드가 존재 하는 경우

 

이제 위 그림 30까지 넣은 상태에서 새로운 키 값인 25인 노드를 삽입해야 한다고 해보자.

먼저 루트를 가리키는 노드 temp를 새로 만들고, temp의 왼쪽 자식이 없을 떄까지 temp를 왼쪽으로 쭉 이동시킨다.

그 후 temp의 왼쪽 자식이 없다면 temp의 왼쪽 자식에 새로운 노드를 추가한다.

 

 

3)루트보다 트리의 키값이 큰 경우

 

문제에서 키 값의 중복이 없다고 했으므로, 루트보다 트리의 키 값이 큰 경우를 생각해보자.

이 경우도 마찬가지로 2가지로 나뉘게 된다.

 

3-1) 루트의 오른쪽 자식이 존재하지 않는 경우

이제 50-30-25를 순서대로 넣어서, 이진검색 트리가 존재한다고 생각해보자.

키 값이 100인 노드를 이진 검색 트리에 삽입해야 한다고 해보자.

루트의 오른쪽에는 아직 자식이 없으므로, 이 경우 루트의 오른쪽 자식을 새 노드로 만들어 주면 끝이다.

 

3-2) 루트의 오른쪽 자식이 존재하는 경우

 

2-2)와 마찬가지로 수행하는데 오른쪽으로 이동하면 된다.

 

---

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n = 0;
int Data;

//구조체 생성

struct node{
    int data;
    node *left = NULL;
    node *right = NULL;
};

//루트 노드 
node *rootnode;

//노드 삽입 
/*
루트가 NULL인경우,
루트보다 키 값이 작은 경우
루트보다 키 값이 큰 경우
*/
void insertNode(int data){
    node *newnode = new node;
    newnode->data = data;
    newnode->left = NULL;
    newnode->right = NULL;
    if(n == 0){
        rootnode = newnode;
    }
    else{
       node *temp = rootnode;
       while(1){
        if(temp->data > newnode->data){
            if(temp->left == NULL){
                temp->left = newnode;
                break;
            }
            else{
                temp = temp->left;
            }
        }
        else if(temp->data < newnode->data){
            if(temp->right == NULL){
                temp->right = newnode;
                break;
            }
            else{
                temp = temp->right;
            }
        }
       }
    }
 
}
 
void input(){
 
	while(cin >> Data){
		insertNode(Data);
        n += 1;
	}
 
}
 
 
 
void postorder(node *root){
    if(root == NULL){
        return;
    }
 
    postorder(root->left);
    postorder(root->right);
    cout << root->data << ' ';
 
}
 
 
int main(void){
    input();
    postorder(rootnode);
}