情報アイランド

「情報を制する者は世界を制す」をモットーに様々な情報を提供することを目指すブログです。現在はプログラミング関連情報が多めですが、投資関連情報も取り扱っていきたいです。

Node.jsで二分探索木を使用する

二分探索木を使用するにはBucketsパッケージのbuckets-jsモジュールのBSTreeクラスを使用します。

このクラスは二分探索木の実装であり、下のような関数を提供します。

  • add・・・要素を追加します。第1引数に追加する要素を指定します。
  • clear・・・全ての要素を削除します。
  • contains・・・要素が含まれているか調べます。第1引数に要素を指定します。
  • equals・・・別の二分探索木と内容が同一であるか調べます。第1引数に二分探索木を指定します。
  • forEach・・・それぞれの要素に対して処理を行います。第1引数に実行する処理を関数として指定します。
  • height・・・木の高さを取得します。
  • inorderTraversal・・・それぞれの要素に対してin-orderで処理を行います。第1引数に実行する処理を関数として指定します。
  • isEmpty・・・空の二分探索木であるか調べます。
  • levelTraversal・・・それぞれの要素に対してlevel-orderで処理を行います。第1引数に実行する処理を関数として指定します。
  • maximum・・・最大の要素を取得します。
  • minimum・・・最小の要素を取得します。
  • postorderTraversal・・・それぞれの要素に対してpost-orderで処理を行います。第1引数に実行する処理を関数として指定します。
  • preorderTraversal・・・それぞれの要素に対してpre-orderで処理を行います。第1引数に実行する処理を関数として指定します。
  • remove・・・要素を削除します。第1引数に削除する要素を指定します。
  • size・・・要素の数を取得します。
  • toArray・・・全ての要素から成る配列を取得します。

サンプルコード1

BSTreeクラスの関数の使用例です。

buckets-js-bstree.js

var bucketsJs = require('buckets-js');

var b = new bucketsJs.BSTree();

print(b);

b.add(0);
b.add(1);
b.add(2);
b.add(3);
b.add(4);
b.add(5);
b.add(6);
b.add(7);

print(b);

console.log(b.isEmpty());

console.log(b.size());

console.log(b.height());
console.log(b.maximum());
console.log(b.minimum());

console.log(b.contains(0));
console.log(b.contains(10));

b.inorderTraversal(function (e) {
    console.log(e);
});
b.postorderTraversal(function (e) {
    console.log(e);
});
b.preorderTraversal(function (e) {
    console.log(e);
});
b.levelTraversal(function (e) {
    console.log(e);
});

b.remove(2);
b.remove(5);

print(b);

b.clear();

print(b);

console.log(b.isEmpty());

console.log(b.size());

console.log(b.height());
console.log(b.maximum());
console.log(b.minimum());

function print(b) {
    b.forEach(function (e) {
        console.log(e);
    });
}

使用パッケージ

  • Buckets
    npm install buckets-jsでインストールします。

実行結果

C:\work\node>node buckets-js-bstree.js
0
1
2
3
4
5
6
7
false
8
7
7
0
true
false
0
1
2
3
4
5
6
7
7
6
5
4
3
2
1
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
3
4
6
7
true
0
-1
undefined
undefined

関連

pizyumi
プログラミング歴19年のベテランプログラマー。業務システム全般何でも作れます。現在はWeb系の技術を勉強中。
スポンサーリンク

-Node.js