M.Hiroi's Home Page

JavaScript Programming

お気楽 TypeScript 超入門


Copyright (C) 2017-2025 Makoto Hiroi
All rights reserved.

簡単なプログラム

●連結リスト (mutable)

片方向の「連結リスト (singly-linked list)」です。詳しい説明は拙作のページ「Algorithms with Python: 連結リスト」をお読みください。なお、連結リストは要素数を N とすると、要素のアクセスは O(N) に比例する時間がかかります。配列のようにランダムアクセスする用途には向きません。ご注意くださいませ。

表 : 連結リストのメソッド
メソッド機能
new LinekdList<T>()コンストラクタ
lenght: number要素数を格納するプロパティ
add(n: number, x: T): Tリストの n 番目に x を挿入する
get(n: number): Tリストの n 番目の要素を返す
set(n: number, x: T): Tリストの n 番目の要素を x に書き換える
delete(n: number): Tリストの n 番目の要素を削除する
toArray(): Array<T>リストを配列に変換する
toString(): stringリストを文字列に変換する
isEmpty(): booleanリストが空ならば true を返す
clear(): voidリストを空にする
*[Symbol.iterator](): IterableIterator<T>ジェネレータ
 
リスト : 連結リスト (mutable)

// コンスセルの終端は null 
// --strictNullChecks を指定してもコンパイルできる

// 共用型
type XCell<T> = null | Cell<T>;

// コンスセル
class Cell<T> {
    constructor(private _item: T, private _next: XCell<T>) { }
    get item(): T { return this._item; }
    set item(x: T) { this._item = x; }
    get next(): XCell<T> { return this._next; }
    set next(x: XCell<T>) { this._next = x; }
}

// 連結リスト
class LinkedList<T> {
    private topCell: XCell<T> = null;
    private size: number = 0;
    constructor() { }

    // 作業用メソッド
    // n 番目のセルを求める
    private nthCell(n: number): XCell<T> {
        let xs = this.topCell;
        while (n-- > 0) {
            if (xs === null) {
                return null;
            } else {
                xs = xs.next;
            }
        }
        return xs;
    }

    // 要素数を求める
    get length(): number { return this.size; }

    // n 番目の値を求める
    get(n: number): T {
        const xs = this.nthCell(n);
        if (xs === null) {
            throw new Error("LinkedList.nth out of range");
        } else {
            return xs.item;
        }
    }

    // n 番目の値を更新する
    set(n: number, x: T): T {
        const xs = this.nthCell(n);
        if (xs === null) {
            throw new Error("LinkedList.update: out of range");
        } else {
            xs.item = x;
            return x;
        }
    }

    // データの挿入
    add(n: number, x: T): T {
        if (n == 0) {
            this.topCell = new Cell(x, this.topCell);
            this.size++;
            return x;
        } else {
            const xs = this.nthCell(n - 1);
            if (xs === null) {
                throw new Error("LinkedList.insert: out of range");
            } else {
                xs.next = new Cell<T>(x, xs.next);
                this.size++;
                return x;
            }
        }
    }

    // データの削除
    delete(n: number): T {
        if (n == 0) {
            if (this.topCell === null) {
                throw new Error("LinkedList.delete: out of range");
            } else {
                const x = this.topCell.item;
                this.topCell = this.topCell.next;
                this.size--;
                return x;
            }
        } else {
            const xs = this.nthCell(n - 1);
            if (xs === null || xs.next === null) {
                throw new Error("LinkeList.delete: out of range");
            } else {
                const x = xs.next.item;
                xs.next = xs.next.next;
                this.size--;
                return x;
            }
        }
    }

    // ジェネレータ
    // 実行中にリストを変更したときの動作は保証しない
    *[Symbol.iterator](): IterableIterator<T> {
        let xs = this.topCell;
        while (xs !== null) {
            yield xs.item;
            xs = xs.next;
        }
    }

    // 配列に変換
    toArray(): Array<T> {
        const xs:Array<T> = [];
        for (let x of this) xs.push(x);
        return xs;
    }

    // 文字列に変換
    toString(): string {
        let s ="(";
        for (let x of this) {
            s += x.toString() + " ";
        }
        return s.trim() + ")";
    }

    // 空リストか？
    isEmpty(): boolean { return this.size == 0; }

    // 空にする
    clear(): void { 
        this.size = 0;
        this.topCell == null;
    }

    // node.js 用
    inspect(): string { return this.toString(); }
}


// 簡単なテスト
const ls = new LinkedList();
console.log('%s', ls);         // ()
console.log(ls.isEmpty());     // true
console.log(ls.length);        // 0
try {
    console.log(ls.add(1, 1));
} catch(err) {
    console.log(err);
}
console.log(ls.add(0, 1));     // 1
console.log(ls.isEmpty());     // false
console.log(ls.length);        // 1
console.log(ls.get(0));        // 1
console.log(ls.set(0, 10));    // 10
console.log('%s', ls);         // (10)
try {
    console.log(ls.delete(1));
} catch(err) {
    console.log(err);
}
console.log(ls.delete(0));     // 10
console.log(ls.isEmpty());     // true

for (let i = 0; i < 8; i++) {
    ls.add(i, i + 1);
}
console.log('%s', ls);         // (1 2 3 4 5 6 7 8)
console.log(ls.toArray());     // [1,2,3,4,5,6,7,8]
console.log(ls.length);        // 8
for (let i = 0; i < 8; i++) {
    ls.set(i, ls.get(i) * 10);
}
console.log('%s', ls);         // (10 20 30 40 50 60 70 80)
while (!ls.isEmpty()) {
    console.log(ls.delete(0));
    console.log('%s', ls);
    console.log(ls.length);
}

$ tsc -t es2015 linkedlist.ts
$ node linkedlist.js
()
true
0
Error: LinkedList.insert: out of range
    ... 略 ...

1
false
1
1
10
(10)
Error: LinkeList.delete: out of range
    ... 略 ...

10
true
(1 2 3 4 5 6 7 8)
[
  1, 2, 3, 4,
  5, 6, 7, 8
]
8
(10 20 30 40 50 60 70 80)
10
(20 30 40 50 60 70 80)
7
20
(30 40 50 60 70 80)
6
30
(40 50 60 70 80)
5
40
(50 60 70 80)
4
50
(60 70 80)
3
60
(70 80)
2
70
(80)
1
80
()
0

●連結リスト (Lisp ライク)

Lisp ライクな連結リストです。クラス Nil が空リスト、クラス Cons<T> がコンスセルを表します。そして、連結リスト List<T> を type で次のように定義しています。 

type List<T> = Nil | Cons<T>;

リストの操作関数は一部を除いてジェネリック関数として定義しています。たとえば、length は Nil と Cons<T> のプロパティとして定義していますが、Cons<T> のほうはリストの長さを求める関数を呼び出しているので、リストが長くなると時間がかかることに注意してください。

表 : 連結リストの操作関数 (1)
名前機能
Nil.empty(): NilNil のオブジェクト (シングルトン) を返す
lenght: number要素数を格納するプロパティ
cons<T>(x: T, xs: List<T>): List<T>コンスセルの生成
list<T>(...args: T[]): List<T>引数 args を格納したリストを生成する
nth(n: number, xs: List<T>): Tリストの n 番目の要素を返す
reverse<T>(xs: List<T>): List<T>リストを反転する
nreverse<T>(xs: List<T>): List<T>リストを破壊的に反転する
append<T>(xs: List<T>, ys: List<T>): List<T>リストを連結する
map<T, U>(func: (x: T) => U, xs: List<T>): List<U>マッピング
filter<T>(pred: (x: T) => boolean, xs: List<T>): List<T>フィルター
reduce<T, U>(func: (acc: U, x: T) => U), a: U, xs: List<T>): U畳み込み
forEach<T>(func: (x: T) => void, xs: List<T>): voidリストの巡回

表 : 連結リストの操作関数 (2)
名前機能
member<T>(x: T, xs: List<T>): List<T>リスト xs から x を探す
indexOf<T>(x: T, xs: List<T>): numberx と等しい要素の位置を求める
count<T>(x: T, xs: List<T>): numberx と等しい要素の個数を求める
iterList<T>(xs: List<T>): IterableIterator<T>ジェネレータ
xs.isEmpty(): booleanリスト xs が空ならば true を返す
 
リスト : 連結リスト (Lisp ライク)

// 空リスト (シングルトン)
class Nil {
    private static obj: Nil | null = null;
    private constructor() { }
    static empty(): Nil {
        if (Nil.obj === null) {
            Nil.obj = new Nil();
        }
        return Nil.obj;
    }
    get first(): never { throw new Error("empty list"); }
    get rest(): never { throw new Error("empty list"); }
    set first(x: never) { throw new Error("empty list"); }
    set rest(x: never) { throw new Error("empty list"); }
    get length(): number { return 0; }
    isEmpty(): boolean { return true; }
    toString(): string { return "()"; }

    // 表示 (Node.js 用)
    inspect(depth: number): string { return this.toString(); }
}

// 連結リスト
type List<T> = Nil | Cons<T>;

// コンスセル
class Cons<T> {
    constructor(private _first: T, private _rest: List<T>) { }
    get first(): T { return this._first; }
    get rest(): List<T> { return this._rest; }
    set first(x: T) { this._first = x; }
    set rest(x: List<T>) { this._rest = x; }
    isEmpty(): boolean { return false; }
    toString(): string {
        let xs:List<T> = this, s = "(";
        while (!xs.isEmpty()) {
            s += xs.first.toString();
            if (!xs.rest.isEmpty()) s += " ";
            xs = xs.rest;
        }
        s += ")";
        return s;
    }

    // 要素数を求める
    private len(): number {
        let c = 0;
        for (let x of iterList(this)) c++;
        return c;
    }
    get length(): number { return this.len(); }

    // 表示 (Node.js 用)
    inspect(depth: number): string { return this.toString(); }
}

// ジェネレータ
function* iterList<T>(xs: List<T>): IterableIterator<T> {
    while (!xs.isEmpty()) {
        yield xs.first;
        xs = xs.rest;
    }
}

// 終端
const nil = Nil.empty();

// リストの生成
function cons<T>(x: T, xs: List<T>): List<T> {
    return new Cons(x, xs);
}

function list<T>(...args: T[]): List<T> {
    let xs:List<T> = nil;
    for (let i = args.length - 1; i >= 0; i--) {
        xs = cons(args[i], xs);
    }
    return xs;
}

// 反転
function reverse<T>(xs: List<T>): List<T> {
    let ys: List<T> = nil;
    for (let x of iterList(xs)) ys = cons(x, ys);
    return ys;
}

// 破壊的反転
function nreverse<T>(xs: List<T>): List<T> {
    let ys: List<T> = nil;
    while (!xs.isEmpty()) {
        const zs = xs.rest;
        xs.rest = ys;
        ys = xs;
        xs = zs;
    }
    return ys;
}

// 連結
function append<T>(xs: List<T>, ys: List<T>): List<T> {
    const zs1 = reverse(xs),
          zs2 = nreverse(zs1);
    zs1.rest = ys;
    return zs2; 
}


// 参照
function nth<T>(n: number, xs: List<T>): T {
    for (let x of iterList(xs)) {
        if (n-- == 0) return x;
    }
    throw new Error("nth: out of range");
}

// マッピング
function map<T, U>(func: (x: T) => U, xs: List<T>): List<U> {
    let ys: List<U> = nil;
    for (let x of iterList(xs)) {
        ys = cons(func(xs.first), ys);
    }
    return nreverse(ys);
}

// フィルター
function filter<T>(pred: (x: T) => boolean, xs: List<T>): List<T> {
    let ys: List<T> = nil;
    for (let x of iterList(xs)) {
        if (pred(x)) ys = cons(x, ys);
    }
    return nreverse(ys);
}

// 畳み込み
function reduce<T, U>(func: (acc: U, x: T) => U, a: U, xs: List<T>): U {
    for (let x of iterList(xs)) a = func(a, x);
    return a;
}

// 巡回
function forEach<T>(func: (x: T) => void, xs: List<T>): void {
    for (let x of iterList(xs)) func(x);
}

// 探索
function member<T>(x: T, xs: List<T>): List<T> {
    while (!xs.isEmpty()) {
        if (xs.first == x) break;
        xs = xs.rest;
    }
    return xs;
}

function indexOf<T>(x: T, xs: List<T>): number {
    let i = 0;
    for (let y of iterList(xs)) {
        if (x == y) return i;
        i++;
    }
    return -1;
}

function count<T>(x: T, xs: List<T>): number {
    let c = 0;
    for (let y of iterList(xs)) {
        if (x == y) c++;
    }
    return c;
}

// 簡単なテスト
console.log('%s', nil);
console.log(nil.length);
const is0 = cons<number>(0, nil);
console.log('%s', is0);
const is1 = list(1,2,3,4,5);
console.log('%s', is1);
console.log(is1.length);
for (let i = 0; i < 5; i++) console.log(nth(i, is1));
console.log('%s', reverse(is1));
const is2 = append(is1, list(6,7,8,9,10));
console.log('%s', is2);
console.log('%s', map(x => x * x, is2));
console.log('%s', filter(x => x % 2 == 0, is2));
console.log(reduce((a, x) => a + x, 0, is2));
forEach(console.log, is2);
console.log('%s', member(1, is2));
console.log('%s', member(10, is2));
console.log('%s', member(11, is2));
console.log(indexOf(1, is2));
console.log(indexOf(10, is2));
console.log(indexOf(11, is2));
const is3 = list(1,1,2,1,2,3,1,2,3,4);
for (let i = 0; i < 5; i++) console.log(count(i, is3));

$ tsc -t es2015 list.ts
$ node list.js
()
0
(0)
(1 2 3 4 5)
5
1
2
3
4
5
(5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10)
(1 1 1 1 1 1 1 1 1 1)
(2 4 6 8 10)
55
1
2
3
4
5
6
7
8
9
10
(1 2 3 4 5 6 7 8 9 10)
(10)
()
0
9
-1
0
4
3
2
1

●抽象クラスを使った連結リスト

ご参考までに抽象クラスを使った連結リストの実装を示します。TypeScript (ver 2.3.2) の場合、static なフィールドやメソッドはクラスの型パラメータを参照することができません。このため、空リストを返す emtpy() やリストを生成する cons(), list() はジェネリック関数として定義しています。

他のプログラミング言語、たとえば Java や C# の場合、これらの関数は static メソッドとして定義することが可能です。興味のある方は拙作のページ「続・お気楽Java プログラミング入門: immutable な連結リスト」や「C# 超入門: immutable な連結リスト」をお読みくださいませ。 

リスト : 抽象クラス List<T> を使った Lisp ライクな連結リスト

// 抽象クラス
abstract class List<T> {
    abstract get first(): T;
    abstract get rest(): List<T>;
    abstract set first(x: T);
    abstract set rest(x: List<T>);
    abstract isEmpty(): boolean;

    //
    // メソッドの定義
    //

    // 長さ
    private len(): number {
        let k = 0;
        for (let x of this) k++;
        return k;
    }
    get length(): number { return this.len(); }

    // ジェネレータ
    *[Symbol.iterator](): IterableIterator<T> {
        let xs: List<T> = this;
        while (!xs.isEmpty()) {
            yield xs.first;
            xs = xs.rest;
        }
    }

    // 参照
    nth(n: number): T {
        for (let x of this) {
            if (n-- == 0) return x;
        }
        throw new Error("List: out of range");
    }

    // 反転
    reverse(): List<T> {
        let ys = empty<T>();
        for (let x of this) ys = cons(x, ys);
        return ys;
    }

    // 破壊的反転
    nreverse(): List<T> {
        let xs: List<T> = this, ys = empty<T>();
        while (!xs.isEmpty()) {
            const zs = xs.rest;
            xs.rest = ys;
            ys = xs;
            xs = zs;
        }
        return ys;
    }

    // 連結
    append(zs: List<T>): List<T> {
        const xs: List<T> = this.reverse(),
              ys = xs.nreverse();
        xs.rest = zs;
        return ys;
    }

    // マッピング
    map<U>(func: (x: T) => U): List<U> {
        let ys = empty<U>();
        for (let x of this) ys = cons(func(x), ys);
        return ys.nreverse();
    }

    // フィルター
    filter(pred: (x: T) => boolean): List<T> {
        let ys = empty<T>();
        for (let x of this) {
            if (pred(x)) ys = cons(x, ys);
        }
        return ys.nreverse();
    }

    // 畳み込み
    reduce<U>(func: (acc: U, x: T) => U, a: U): U {
        for (let x of this) a = func(a, x);
        return a;
    }

    // 巡回
    forEach(func: (x: T) => void): void {
        for (let x of this) func(x);
    }

    //
    // 探索
    //
    member(x: T): List<T> {
        let xs: List<T> = this;
        while (!xs.isEmpty()) {
            if (xs.first == x) break;
            xs = xs.rest;
        }
        return xs;
    }

    indexOf(x: T): number {
        let i = 0;
        for (let y of this) {
            if (y == x) return i;
            i++;
        } 
        return -1;
    }
    
    count(x: T): number {
        let c = 0;
        for (let y of this) {
            if (x == y) c++;
        }
        return c;
    }
    
    // 文字列
    toString(): string {
        let s = "(";
        for (let x of this) s += x.toString() + " ";
        return s.trim() + ")";
    }

    // 表示
    inspect(): string { return this.toString(); }
}

// コンスセル
class Cons<T> extends List<T> {
    constructor(private _first: T, private _rest: List<T>) { super(); }
    get first(): T { return this._first; }
    set first(x: T) { this._first = x; }
    get rest(): List<T> { return this._rest; }
    set rest(x: List<T>) { this._rest = x; }
    isEmpty(): boolean { return false; }
}

// 空リスト (シングルトン)
class Nil extends List<never> {
    private static obj: Nil | null = null; 
    private constructor() { super(); }
    get first(): never { throw new Error("empty List"); }
    set first(x: never) { throw new Error("empty List"); }
    get rest(): never { throw new Error("empty List"); }
    set rest(x: never) { throw new Error("empty List"); }
    isEmpty(): boolean { return true; }

    static make(): Nil {
        if (Nil.obj == null) {
            Nil.obj = new Nil();
        }
        return Nil.obj;
    }
}

// 空リスト
function empty<T>(): List<T> { return Nil.make(); }

// リストの生成
function cons<T>(x: T, xs: List<T>): List<T> { return new Cons(x, xs); }

function list<T>(...args: T[]): List<T> {
    let xs: List<T> = empty<T>();
    for (let i = args.length - 1; i >= 0; i--) {
        xs = new Cons(args[i], xs);
    }
    return xs;
}

// 簡単なテスト
const nil = empty<number>();
console.log('%s', nil);
console.log(nil.length);
const is0 = cons<number>(0, nil);
console.log('%s', is0);
const is1 = list(1,2,3,4,5);
console.log('%s', is1);
console.log(is1.length);
for (let i = 0; i < 5; i++) console.log(is1.nth(i));
console.log('%s', is1.reverse());
const is2 = is1.append(list(6,7,8,9,10));
console.log('%s', is2);
console.log('%s', is2.map(x => x * x));
console.log('%s', is2.filter(x => x % 2 == 0));
console.log(is2.reduce((a, x) => a + x, 0));
is2.forEach(console.log);
console.log('%s', is2.member(1));
console.log('%s', is2.member(10));
console.log('%s', is2.member(11));
console.log(is2.indexOf(1));
console.log(is2.indexOf(10));
console.log(is2.indexOf(11));
const is3 = list(1,1,2,1,2,3,1,2,3,4);
for (let i = 0; i < 5; i++) console.log(is3.count(i));

●二分木 (mutable)

mutable な二分木です。二分木の説明は拙作のページ「Algorithms with Python: 二分木とヒープ」をお読みください。

表 : 二分木 Tree<T> のメソッド
名前機能
new Tree<T>()コンストラクタ
has(x: T): boolean二分木から x を探す
add(x: T): void二分木に x を追加する
delete(x: T): void二分木から x を削除する
isEmpty(): boolean二分木が空ならば true を返す
clear(): void二分木を空にする
toString(): string文字列に変換する
*[Symbol.inspect](): IterableIterator<T>ジェネレータ
 
リスト : 二分木 (mutable)

// 節
type XNode<T> = null | TNode<T>;

class TNode<T> {
    constructor(private _item: T, private _left: XNode<T>, private _right: XNode<T>) { }
    get item(): T { return this._item; }
    set item(x: T) { this._item = x; }
    get left(): XNode<T> { return this._left; }
    set left(x: XNode<T>) { this._left = x; }
    get right(): XNode<T> { return this._right; }
    set right(x: XNode<T>) { this._right = x; }
}

// 作業用関数
// 本来ならばモジュールなどに格納して外部には公開しない

// 探索
function search<T>(x: T, xs: XNode<T>): boolean {
    while (xs != null) {
        if (xs.item == x) return true;
        if (xs.item > x) {
            xs = xs.left;
        } else {
            xs = xs.right;
        }
    }
    return false;
}

// 挿入
function insert<T>(x: T, xs: XNode<T>): XNode<T> {
    if (xs == null) {
        return new TNode(x, null, null);
    } else if (xs.item > x) {
        xs.left = insert(x, xs.left);
    } else if (xs.item < x) {
        xs.right = insert(x, xs.right);
    }
    return xs;
}

// 最小値の探索
function searchMin<T>(xs: TNode<T>): T {
    while (xs.left != null) xs = xs.left;
    return xs.item;
}

// 最小値の節を削除
function removeMin<T>(xs: TNode<T>): XNode<T> {
    if (xs.left == null) return xs.right;
    xs.left = removeMin(xs.left);
    return xs;
}

// 削除
function remove<T>(x: T, xs: XNode<T>): XNode<T> {
    if (xs == null) return xs;
    if (xs.item == x) {
        if (xs.left == null) return xs.right;
        if (xs.right == null) return xs.left;
        xs.item = searchMin(xs.right);
        xs.right = removeMin(xs.right);
    } else if (xs.item > x) {
        xs.left = remove(x, xs.left);
    } else {
        xs.right = remove(x, xs.right);
    }
    return xs;
}

// 巡回
function* traverse<T>(xs: XNode<T>): IterableIterator<T> {
    if (xs != null) {
        yield* traverse(xs.left);
        yield xs.item;
        yield* traverse(xs.right);
    }
}

// 単純な二分木 (公開用クラス)
class Tree<T> {
    constructor(private _root: XNode<T> = null) { }
    get root(): XNode<T> { return this._root; }
    set root(x: XNode<T>) { this._root = x; }

    has(x: T): boolean { return search<T>(x, this.root); }
    add(x: T): void {
        this.root = insert(x, this.root);
    }
    delete(x: T): void {
        this.root = remove(x, this.root);
    }

    // 空の木か？
    isEmpty(): boolean { return this.root == null; }

    // 空にする
    clear(): void { this.root = null; }

    // ジェネレータ
    *[Symbol.iterator](): IterableIterator<T> { yield* traverse(this.root); }

    // 文字列
    toString(): string {
        let s = "(";
        for (let x of this) {
            s += x.toString() + " ";
        }
        return s.trim() + ")";
    }

    inspect(): string {
        return this.toString();
    }
}

// 簡単なテスト
const tree = new Tree<number>();
console.log(tree.isEmpty());
for (let x of [5,3,7,2,4,6,8,1,9]) {
    tree.add(x);
}
console.log('%s', tree);
console.log(tree.isEmpty());
for (let x = 0; x <= 10; x++) console.log(tree.has(x));
for (let x = 0; x <= 10; x++) {
    tree.delete(x);
    console.log('%s', tree)
}
console.log(tree.isEmpty());

$ tsc -t es2015 tree.ts
$ node tree.js
true
(1 2 3 4 5 6 7 8 9)
false
false
true
true
true
true
true
true
true
true
true
false
(1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9)
(3 4 5 6 7 8 9)
(4 5 6 7 8 9)
(5 6 7 8 9)
(6 7 8 9)
(7 8 9)
(8 9)
(9)
()
()
true

●二分木 (immutable)

immutable な二分木です。クラス TNil が空の木 (終端)、クラス ImNode<T> が節を表します。そして、二分木 ImTree<T> を type で次のように定義しています。 

type ImTree<T> = TNil | ImNode<T>;

二分木の操作関数は一部を除いてジェネリック関数として定義しています。

表 : 二分木 ImTree<T> の操作関数
名前機能
TNil.empty(): TNil空の木を返す
hasTree<T>(x: T, xs: ImTree<T>): boolean二分木 xs から x を探す
addTree<T>(x: T, xs: ImTree<T>): ImTree<T>二分木 xs に x を追加する
deleteTree<T>(x: T, xs: ImTree<T>): ImTree<T>二分木 xs から x を削除する
forEachTree<T>((x: T) => void, xs: ImTree<T>): void二分木を巡回する
iterTree<T>(xs: ImTree<T>): IterableIterator<T>ジェネレータ
xs.isEmpty(): boolean二分木 xs が空ならば true を返す
xs.toString(): string二分木 xs を文字列に変換する
 
リスト : 二分木 (immutable)

// 終端 (シングルトン)
class TNil {
    private static obj: TNil | null = null;
    private constructor() { }
    get item(): never { throw new Error("empty tree"); }
    get left(): never { throw new Error("empty tree"); }
    get right(): never { throw new Error("empty tree"); }
    isEmpty(): boolean { return true; }
    toString(): string { return "()"; }
    inspect(): string { return this.toString(); }

    // 空の木 (終端)
    static empty(): TNil {
        if (TNil.obj === null) {
            TNil.obj = new TNil();
        }
        return TNil.obj;
    }
}

// 終端の作成
const tNil = TNil.empty();

// 二分木
type ImTree<T> = TNil | ImNode<T>;

// 節
class ImNode<T> {
    constructor(private _item: T, private _left: ImTree<T>, private _right: ImTree<T>) { }
    get item(): T { return this._item; }
    get left(): ImTree<T> { return this._left; }
    get right(): ImTree<T> { return this._right; }
    isEmpty(): boolean { return false; }
    toString(): string {
        let s = "(";
        for (let x of iterTree(this)) {
            s += x.toString() + " ";
        }
        return s.trim() + ")";
    }
    inspect(): string { return this.toString(); }
}

// ジェネレータ
function* iterTree<T>(xs: ImTree<T>): IterableIterator<T> {
    if (!xs.isEmpty()) {
        yield* iterTree(xs.left);
        yield xs.item;
        yield* iterTree(xs.right);
    }
}

// 探索
function hasTree<T>(x: T, xs: ImTree<T>): boolean {
    while (!xs.isEmpty()) {
        if (xs.item == x) return true;
        if (xs.item > x) {
            xs = xs.left;
        } else {
            xs = xs.right;
        }
    }
    return false;
}

// 挿入
function addTree<T>(x: T, xs: ImTree<T>): ImTree<T> {
    if (xs.isEmpty()) return new ImNode<T>(x, tNil, tNil);
    if (xs.item > x) {
        return new ImNode<T>(xs.item, addTree(x, xs.left), xs.right);
    } else if (xs.item < x) {
        return new ImNode<T>(xs.item, xs.left, addTree(x, xs.right));
    }
    return xs;
}

// 最小値の探索
function searchMinTree<T>(xs: ImTree<T>): T {
    while (!xs.left.isEmpty()) xs = xs.left;
    return xs.item;
}

// 最小値の節を削除
function deleteMinTree<T>(xs: ImTree<T>): ImTree<T> {
    if (xs.left.isEmpty()) return xs.right;
    return new ImNode(xs.item, deleteMinTree(xs.left), xs.right);
}

// 削除
function deleteTree<T>(x: T, xs: ImTree<T>): ImTree<T> {
    if (xs.isEmpty()) return xs;
    if (xs.item == x) {
        if (xs.left.isEmpty()) return xs.right;
        if (xs.right.isEmpty()) return xs.left;
        return new ImNode(searchMinTree(xs.right), xs.left, deleteMinTree(xs.right));
    } else if (xs.item > x) {
        return new ImNode<T>(xs.item, deleteTree(x, xs.left), xs.right);
    } else {
        return new ImNode<T>(xs.item, xs.left, deleteTree(x, xs.right));
    }
}

// 高階関数
function forEachTree<T>(func: (x: T) => void, xs: ImTree<T>): void {
    if (!xs.isEmpty()) {
        forEachTree(func, xs.left);
        func(xs.item);
        forEachTree(func, xs.right);
    }
}

// 簡単なテスト
let imTree: ImTree<number> = tNil;
console.log('%s', imTree);
console.log(imTree.isEmpty());
for (let x of [5,2,8,1,3,6,9,4,7]) {
    imTree = addTree(x, imTree);
}
console.log('%s', imTree);
forEachTree(console.log, imTree);
for (let x = 0; x <= 10; x++) console.log(hasTree(x, imTree));
for (let x = 0; x <= 10; x++) {
    imTree = deleteTree(x, imTree);
    console.log('%s', imTree);
}
console.log(imTree.isEmpty());

$ tsc -t es2015 tree.ts
$ node tree.js
()
true
(1 2 3 4 5 6 7 8 9)
1
2
3
4
5
6
7
8
9
false
true
true
true
true
true
true
true
true
true
false
(1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9)
(3 4 5 6 7 8 9)
(4 5 6 7 8 9)
(5 6 7 8 9)
(6 7 8 9)
(7 8 9)
(8 9)
(9)
()
()
true

●抽象クラスを使った二分木

ご参考までに抽象クラスを使った二分木の実装を示します。 

リスト : 抽象クラスを使った二分木の実装

// 抽象クラス
abstract class ImTree<T> {
    abstract get item(): T;
    abstract get left(): ImTree<T>;
    abstract get right(): ImTree<T>;
    abstract isEmpty(): boolean;

    //
    // メソッド
    //
    
    // 探索
    has(x: T): boolean {
        let xs: ImTree<T> = this;
        while (!xs.isEmpty()) {
            if (xs.item == x) return true;
            if (xs.item > x) {
                xs = xs.left;
            } else {
                xs = xs.right;
            }
        }
        return false;
    }

    // 挿入
    add(x: T): ImTree<T> {
        let xs: ImTree<T> = this;
        if (xs.isEmpty()) {
            return new TNode(x, TNil.empty(), TNil.empty());
        }
        if (xs.item == x) return xs;
        if (xs.item > x) {
            return new TNode(xs.item, xs.left.add(x), xs.right);
        } else {
            return new TNode(xs.item, xs.left, xs.right.add(x));
        }
    }

    // 最小値を探す
    searchMin(): T {
        let xs: ImTree<T> = this;
        if (xs.isEmpty()) throw new Error("empty tree");
        while (!xs.left.isEmpty()) xs = xs.left;
        return xs.item;
    }

    // 最小値を削除
    deleteMin(): ImTree<T> {
        let xs: ImTree<T> = this;
        if (xs.isEmpty()) throw new Error("empty tree");
        if (xs.left.isEmpty()) {
            return xs.right;
        }
        return new TNode(xs.item, xs.left.deleteMin(), xs.right);
    }

    // 削除
    delete(x: T): ImTree<T> {
        let xs: ImTree<T> = this;
        if (xs.isEmpty()) return xs;
        if (xs.item == x) {
            if (xs.left.isEmpty()) return xs.right;
            if (xs.right.isEmpty()) return xs.left;
            return new TNode(xs.right.searchMin(), xs.left, xs.right.deleteMin());
        } else if (xs.item > x) {
            return new TNode(xs.item, xs.left.delete(x), xs.right);
        } else {
            return new TNode(xs.item, xs.left, xs.right.deleteMin());
        }
    }

    // 巡回
    forEach(func: (x: T) => void): void {
        if (!this.isEmpty()) {
            this.left.forEach(func);
            func(this.item);
            this.right.forEach(func);
        }
    }

    // ジェネレータ
    *[Symbol.iterator](): IterableIterator<T> {
        if (!this.isEmpty()) {
            yield* (this.left)[Symbol.iterator]();
            yield this.item;
            yield* (this.right)[Symbol.iterator]();
        }
    }

    // 文字列
    toString(): string {
        let s = "(";
        for (let x of this) {
            s += x.toString() + " ";
        }
        return s.trim() + ")";
    }

    // node.js 用
    inspect(): string { return this.toString(); }
}

// 空の木 (シングルトン)
class TNil extends ImTree<never> {
    private static obj: TNil | null = null;
    private constructor() { super(); }
    get item(): never { throw new Error("empty tree"); }
    get left(): never { throw new Error("empty tree"); }
    get right(): never { throw new Error("empty tree"); }
    isEmpty(): boolean { return true; }

    static empty(): TNil {
        if (TNil.obj === null) {
            TNil.obj = new TNil();
        }
        return TNil.obj;
    }
}

// 節
class TNode<T> extends ImTree<T> {
    constructor(private _item: T, private _left: ImTree<T>, private _right: ImTree<T>) {
        super();
    }
    get item(): T { return this._item; }
    get left(): ImTree<T> { return this._left; }
    get right(): ImTree<T> { return this._right; }
    isEmpty(): boolean { return false; }
}

// 簡単なテスト
let imTree: ImTree<number> = TNil.empty();
console.log('%s', imTree);
console.log(imTree.isEmpty());
for (let x of [5,2,8,1,3,6,9,4,7]) {
    imTree = imTree.add(x);
}
console.log('%s', imTree);
imTree.forEach(console.log);
for (let x of imTree) console.log(x);
for (let x = 0; x <= 10; x++) console.log(imTree.has(x));
for (let x = 0; x <= 10; x++) {
    imTree = imTree.delete(x);
    console.log('%s', imTree);
}
console.log(imTree.isEmpty());

$ tsc -t es2015 tree1.ts
$ node tree1.js
()
true
(1 2 3 4 5 6 7 8 9)
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
false
true
true
true
true
true
true
true
true
true
false
(1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9)
(3 4 5 6 7 8 9)
(4 5 6 7 8 9)
(5 6 7 8 9)
(6 7 8 9)
(7 8 9)
(8 9)
(9)
()
()
true
初版 2017 年 6 月 17 日
改訂 2025 年 1 月 9 日