Binary Search Tree Test File

main.cpp

#include <iostream>
#include <cassert>
#include <ctime>
#include <cassert>
#include <vector>
#include "vendor.h"
#include "BST.h"

using namespace std;

void shuffle( vector<int>& vec ){

    srand( time(NULL) );
    for( int i = vec.size()-1 ; i >= 0 ; i -- ){
        int x = rand()%(i+1);
        swap( vec[i] , vec[x] );
    }
}

int main() {
//    int n = 1000;
//    int* arr = new int[n];
//    for( int i = 0 ; i < n ; i ++ )
//        arr[i] = i;
//    for( int i = 0 ; i < 2*n ; i ++ ){
//        int v = bin_search<int>(arr, n, i);
//        if( i < n )
//            assert( v == i );
//        else
//            assert( v == -1 );
//    }

//    int a[] = {1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 5, 5, 5, 6, 6, 6};
//    int n = sizeof(a)/sizeof(int);
//    for( int i = 0 ; i <= 8 ; i ++ ){
//
//        int floorIndex = floor(a, n, i);
//        cout<<"the floor index of "<<i<<" is "<<floorIndex<<".";
//        if( floorIndex >= 0 && floorIndex < n )
//            cout<<"The value is "<<a[floorIndex]<<".";
//        cout<<endl;
//
//        int ceilIndex = ceil(a, sizeof(a)/sizeof(int), i);
//        cout<<"the ceil index of "<<i<<" is "<<ceilIndex<<".";
//        if( ceilIndex >= 0 && ceilIndex < n )
//            cout<<"The value is "<<a[ceilIndex]<<".";
//        cout<<endl;
//
//        cout<<endl;
//    }
    BST<int,int> bst;

    //将[0, N)之间的偶数保存在nums中
    int N = 1000;
    vector<int> nums;
    for( int i = 0 ; i < N ; i += 2)
        nums.push_back(i);
    int minNum = nums[0];
    int maxNum = nums[nums.size()-1];

    // 将nums乱序处理
    shuffle(nums);

    // 向二分搜索树中插入[0, N)之间的所有偶数
    for(int i = 0 ; i < nums.size() ; i ++ )
        bst.insert(nums[i], nums[i]);

    // 对[0...N]区间里的N+1个数, 调用二分搜索树的floor和ceil, 查看其结果
    for( int i = 0 ; i <= N ; i ++ ){

        // 测试floor
        int* floorKey = bst.floor(i);
        if(i % 2 == 0){
            if(i >= 0 && i < N) assert(*floorKey == i);
            else if(i < 0)      assert(floorKey == NULL);
            else                assert(*floorKey == maxNum);
        }
        else {
            if(i - 1 >= 0 && i - 1 < N) assert(*floorKey == i - 1);
            else if(i - 1 < 0)          assert(floorKey == NULL);
            else                        assert(*floorKey == maxNum);
        }

        cout<<"the floor of "<<i<<" is ";
        if( floorKey == NULL )
            cout<<"NULL"<<endl;
        else
            cout<<*floorKey<<endl;


        // 测试ceil
        int* ceilKey = bst.ceil(i);
        if(i % 2 == 0) {
            if(i >= 0 && i < N) assert(*ceilKey == i);
            else if(i < 0)      assert(*ceilKey == minNum);
            else                assert(ceilKey == NULL);
        }
        else {
            if(i + 1 >= 0 && i + 1 < N) assert(*ceilKey == i + 1);
            else if(i + 1 < 0)          assert(*ceilKey == minNum);
            else                        assert(ceilKey == NULL);
        }

        cout<<"the ceil of "<<i<<" is ";
        if( ceilKey == NULL )
            cout<<"NULL"<<endl;
        else
            cout<<*ceilKey<<endl;


        cout<<endl;
    }

    return 0;
}