Graphvizで二分探索木を描画する

Graphvizという便利なツールがあることを知った。
AT&T研究所が開発したオープンソースのグラフ描画ツールである。とりあえず動かして遊んでみようということで、二分探索木を描画してみた。

インストール

Ubuntuマシンにインストール。

$ sudo apt-get install graphviz

二分木を作るプログラム

まず、20個の乱数を二分探索木に格納する。
その後、Graphvizに読み込ませるDOT言語のスクリプトをdump関数で出力する。

#include <iostream>
#include <cstdlib>

using namespace std;

struct node {
    int x;
    node *lch, *rch;

    node (int x) : x(x), lch(NULL), rch(NULL) {}
};

node *insert(node *v, int x) {
    if (v == NULL)
        return new node(x);
    if (x < v->x) 
        v->lch = insert(v->lch, x);
    if (x > v->x) 
        v->rch = insert(v->rch, x);
    return v;
}

void dump(node *v, node *par = NULL) {
    if (v == NULL)
        return;

    if (par == NULL) {
        cout << "digraph G{" << endl;
        cout << "  graph [ordering=\"out\"];" << endl;
    }
    else {
        cout << "  " << par->x << " -> " << v->x;
        if (v->x > par->x)
            cout << " [style = dotted]";
        cout << ";" << endl;
    }

    dump(v->lch, v);
    dump(v->rch, v);

    if (par == NULL)
        cout << "}" << endl;
}

int main(int argc, char **argv) {

    srand(time(NULL));
    node *root = NULL;

    for (int i = 0; i < 20; i++)
        root = insert(root, rand() % 100);

    dump(root);

    return 0;
}

上のソースはbst.cppという名前で保存しているとする。

以下を実行。

$ g++ bst.cpp -o bst
$ ./bst >sample.dot
$ dot -Tpng sample.dot -o sample.png
$ xdg-open sample.png 

すると、以下の画像が表示される。実戦が左の子への辺、破線が右の子への辺である。

これで木の回転をして遊んだり、平衡二分木を自分で実装したり、などなどするときに動作確認がしやすくなる。