이원 탐색 트리(Binary Search Tree) 배열 만들기

문제 :

배열을 이용하여 이원 탐색 트리를 만들고 탐색하는 프로그램을 작성하라.

1. 입력 : 정렬이 되지 않은 숫자들

2. 프로그램 : 

  2.1 입력된 숫자들을 하나씩 읽으면서 이원 탐색 트리 배열 만들기

  2.2 숫자 하나를 입력하면 이원탐색트리 알고리즘을 적용하여 해당하는 배열의 첨자를 출력하기

         (이 때 출력은 배열 원소들을 차례대로 출력하고 해당하는 배열 첨자를 출력)

 

실행 결과 :

 

코드 :

#include<iostream>
using namespace std;
 
void newBinarySearchTree(int *num_arr, int size, int *new_num_arr) {
    
    for(int i=0; i<size+20; i++){ // 이원탐색트리 배열 -1로 초기화 
        new_num_arr[i] = -1;
    }
    new_num_arr[0] = num_arr[0];
    
    for(int i=1; i<size; i++){
        int index=0;
        // 새로 들어올 숫자가 이원탐색트리 배열의 루트보다 작으면 왼쪽으로 이동    
        if(new_num_arr[0] > num_arr[i]) {     
        for(int j=2*index+1;;) {
                if(new_num_arr[j] != -1){ //삽입하려는 이원탐색트리 배열공간이 NULL이 아니면 비교 
                    if(new_num_arr[j] < num_arr[i]) j=2*j+2; //  삽입하고자 하는 숫자가 더 크면 2j+2
                    else if(new_num_arr[j] > num_arr[i]) j=2*j+1; // 삽입하고자 하는 숫자가 더 작으면 2j+1  z
                    else {
                        //같은 숫자가 나오면 오류메시지 출력 후 프로그램 비정상 종료 
                        cout << "same data error...\n"; exit(1); 
                    }
                }
                else if(new_num_arr[j] == -1) { // 삽입하려는 이원탐색트리 배열 공간이 NULL이면 바로 삽입 
                    new_num_arr[j] = num_arr[i];
                    break;
                }
            }
        }
        // 새로 들어올 숫자가 이원탐색트리 배열의 루트보다 크면 오른쪽으로 이동
        else if(new_num_arr[0] < num_arr[i]) {   
            for(int j=2*index+2;;) { 
                if(new_num_arr[j] != -1){ // 삽입하려는 이원탐색트리 배열공간이 NULL이 아니면 비교 
                    if(new_num_arr[j] < num_arr[i]) j=2*j+2; 
                    else if(new_num_arr[j] > num_arr[i]) j=2*j+1;
                    else {
                        cout << "same data error...\n"; exit(1); 
                    }
                }
                else if(new_num_arr[j] == -1) {
                    new_num_arr[j] = num_arr[i];
                    break;
                }
            }
        }
        else continue;
    }
}
 
void find(int *new_num_arr, int size) {
    int x, flag;
    cout << "찾고자 하는 숫자 입력 : ";
    cin >>  x;
    
    for(int i=0; i<size; i++) // 이원탐색트리 배열의 모든 원소 출력 
    cout << "arr[" << i << "] : " << new_num_arr[i] << endl;
        
    for(int i=0; i<size; i++){
        if(new_num_arr[i] == x) {
            cout << "index : " << i;
            flag = true;
            break;
        }
        else
            flag = false;
    }
    if(!flag) // flag가 false이면 찾고자 하는 숫자가 없다고 출력
        cout << "찾고자 하는 숫자 없음\n"; 
}
 
int main() {
    int num_arr[] = {50, 40, 55, 30, 45, 54, 53, 1, 60, 301, 2};
    int num_arr_size = sizeof(num_arr)/sizeof(num_arr[0]);
    int *new_num_arr = new int [num_arr_size + 20]; // 이원탐색트리 배열 공간 생성 
    
    newBinarySearchTree(num_arr, num_arr_size, new_num_arr);
    find(new_num_arr, num_arr_size + 20); 
}

 

설명 :

간단하게 구현하기 위해 입력 데이터로 숫자 배열을 만들어 넣어주고, 이원 탐색 트리 배열의 크기도 임의로 적당히 지정했습니다.

위의 코드의 경우 배열의 크기를 동적으로 할당받지 않았으므로 최악의 입력 데이터가 들어올 경우 오버플로우가 일어날 수 있으니 작성할 때 주의하셔서 수정하시면 됩니다.