aptoro.jp

ずぼら人間のブログ.技術系ブログにしたかった何か

二分探索木

twitterで,二分探索木をどう書くか,という話があったので書いてみた.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <fstream>

using namespace std;

ofstream ofs("result.csv", ios::app);

int bST(int ans, int min, int max)
{
    int result = (max + min) / 2;
    ofs << "Result," << result << "\n";

    if (result == ans)
    {
        return result;
    }
    else if(result > ans)
    {
        return bST(ans, min, result);
    }
    else
    {
        return bST(ans, result, max);
    }
}

int main()
{
    std::cout << "Start Binary Search Tree.\n";
    
    srand(time(NULL));
    int max = rand();
    int ans = rand() % max;

    ofs << "Answer," << ans << "\n";
    int result = bST(ans, 0, max);

    ofs << "\n";
}

csvに出力して,値の遷移をグラフにしてみた.

f:id:aptorojp:20191214183049p:plain
bst

なんか大学1年生辺りが読む教科書に載ってそうなコードになったけど動いたからヨシ!