[BOJ] 이진검색 트리

[문제]

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

5639번: 이진 검색 트리

[풀이]

 

5639

맞았습니다!!

2572

96

C++14 / 수정

1235

36초 전

 

#include <iostream>
 
using namespace std;
 
//이진 검색 트리
 
typedef struct Node {
    int data;
    struct Node *left, *right;
 
};
 
void insertNode(Node* node, int data) {
    Node* parent;
    Node* tmp;
    Node* newNode;
 
    parent = NULL;
    tmp = node;
    
    while(tmp != NULL) {
        parent = tmp;
 
        if (tmp->data > data) {
            //왼쪽으로 간다. 
            if (tmp->left != NULL) 
                tmp = tmp->left;
            else 
                break; //그 자리에 자리잡는다. 
            
        }
        else {
            //오른쪽으로 간다. 
            if (tmp->right != NULL) 
                tmp = tmp->right;
                
            else break;
        }
    }//while 
 
    newNode = new Node;
    //새로 넣어줄 노드 
 
    if (parent->data > data) {
        //수가 들어갈 수 있는 자리를 만들어준다. 
        parent-> left = newNode;
 
    } 
    else 
        parent->right = newNode;
 
    
    newNode->data= data;
    newNode->left = NULL;
    newNode->right = NULL;
}
 
void postOrder(Node *root) {
    if (root) {
        postOrder(root->left);
        postOrder(root->right);
        cout << root->data <<'\n';
    }    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tmp;
 
    cin >> tmp;
 
    Node *root = new Node;
    root-> data = tmp;
    root-> left=  NULL;
    root-> right = NULL;
 
    while(cin>>tmp) {
        insertNode(root, tmp);
    }
 
    postOrder(root);
    return 0;
}