Binary Search Tree (BST) in Array C++

 Binary Search Tree in Array C++

 

Binary Search Tree in Array C++ 

 

 

Source code:

 

 /* 
bineary search tree algorithms
in increasing ordr

    ---psuedo code----
    1. step1 - intialize array[], start, end, mid;
            start = array[0]; end = sizeof(array[n]);
 mid = (start + end)/2;
             **** optimize mid = (start - (end - start)/2)
            searchingkey;
    2. step2 - while(start >= end) {

        
        if(mid == searchingkey){
            return mid;
        }
        if(searchingkey > mid){
            start = mid +1;
        }
        else{
          end =  mid -1; 
        }

        mid = start + (end - start)/2;


    }
    3.step3 repeat until step2 when start >= true;

 */

 #include <iostream>
 using namespace std;

    // Binary search Tree Algorithm for searchin element in A Array.
    //parameter as 1. array_name, 2. array_size, 3. search_key_element
    int bstAlgo(int array_name[], int array_size, int search_key){
        // start indexing array with 0 (zero), end = last index of element
        // mid = mean of last and first index number
        int start = 0, end, mid;
       // last element index nth position number in array
        end = array_size;
        // here mid = start + end /2;

        mid = start + (end - start)/2;

// when to start <= end is true then 
//working while loop otherwise exit from loop
        while(start <= end){

            // here to compare search key and mid position value 
            // if true return mid position number

            if(search_key == array_name[mid]){
                return mid;
            }

            if(search_key > array_name[mid]){
                start = mid +1;
            }
            else {
                end = mid -1;
            }

            mid = start + (end - start)/2;

        }
        return -1;
    }


    void printArray(int arrayname[], int size){
        for(int i =0; i < size; i++){
            cout << arrayname[i] << " ";
        }
        cout << endl;
    }

    // code driver with main function
 int main(){
     int n, key, arraysize;
     cout 	<< "Enter the number of element in array" <<endl;
// take input from user number of elemet in array
     cin >>n;
     cout 	<< "Enter the " 	<< n	<< " element of value"	<<endl;

     int bstarray[n];
     // array element take input from users
     for(int i =0; i< n; i++){
         cin >> bstarray[i];
     }
     arraysize = sizeof(bstarray) / sizeof(bstarray[0]);

     cout 	<< " Print Original Array" 	<< endl;

     printArray(bstarray, arraysize);

     cout 	<< "searching element in bst algo"	<< endl;

     cout 	<< "Enter searching element value  " 	<< endl;
     cin >>key;

     int index = bstAlgo(bstarray, arraysize, key );

     cout 	<< "element "	<< key 	<< " found at index of "	<< index;



 }
// -- end binary search algorithm 

output

Enter the number of element in array
5
Enter the 5 element of value
1
2
3
4
5
 Print Original Array
1 2 3 4 5
searching element in bst algo  
Enter searching element value  

3
element 3 found at index of 2