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
すると、以下の画像が表示される。実戦が左の子への辺、破線が右の子への辺である。
これで木の回転をして遊んだり、平衡二分木を自分で実装したり、などなどするときに動作確認がしやすくなる。
0 件のコメント:
コメントを投稿