JavaScript - Binary Trees and Binary Search Trees(counting occurences)

Data Structures and Algorithms With Javascript
(O'Reilly Media)
Michael McMillan(著)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• SpiderMonkey, Node.js(V8) (JavaScript engine)

Data Structures and Algorithms With Javascript (Michael McMillan(著)、O'Reilly Media)のChapter 10(Binary Trees and Binary Search Trees)、Exercises 5.(No. 6428)を解いてみる。

Exercises 5.(No. 6428)

JavaScript(Emacs)

/*jslint         browser : true, continue : true,
  devel  : true, indent  : 4,    maxerr   : 50,
  newcap : true, nomen   : true, plusplus : false,
  regexp : true, sloppy  : true, vars     : false,
  white  : true
*/

/*global console*/
var Node,
    BST,
    fs = require('fs'),
    words;

Node = function (data, left, right) {
    this.data = data;
    this.count = 1;
    this.left = left;    
    this.right = right;
};
Node.prototype = {
    constructor: Node,
    show:function () {
        return this.data + ': ' + this.count;
    }
};
BST = function () {
    this.root = null;
};
BST.prototype = {
    constructor: BST,
    insert: function (data) {
        var n = new Node(data, null, null),
            current,
            parent;

        if (this.root === null) {
            this.root = n;
        } else {
            current = this.root;
            while (true) {
                parent = current;
                if (data === current.data) {
                    current.count += 1;
                    break;
                }
                if (data < current.data) {
                    current = current.left;
                    if (current === null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if (current === null) {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    },
    inOrder: function (node) {
        if (node !== null) {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    },
    count: function (node) {
        var num = 0;
        if (node !== null) {
            num += 1;
            num += this.count(node.left);
            num += this.count(node.right);
        }
        return num;
    },
    edges: function (node) {
        var num = 0;
        if (node !== null) {
            if (node.left === null && node.right === null) {
                num += 1;
            }
            num += this.edges(node.left);
            num += this.edges(node.right);
        }
        return num;
    },
    max: function () {
        var current = this.root;

        if (current === null) {
            return current;
        }
        while (current.right !== null) {
            current = current.right;
        }
        return current.data;
    },
    min: function () {
        var current = this.root;

        if (current === null) {
            return current;
        }
        while (current.left !== null) {
            current = current.left;
        }
        return current.data;
    }
};

words = new BST();

fs.readFile('sample5.js', function(err, data) {
    if (err) {
        console.log(err);
    } else {
        data.toString().split(/\s+/).forEach(function (word) {
            words.insert(word);
        });
        words.inOrder(words.root);
    }
});

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample5.js

sample5.js is OK.
$ node sample5.js
: 1
!==: 5
&&: 1
': 1
':: 1
(): 4
(current: 4
(current.left: 1
(current.right: 1
(data: 2
(data): 1
(data,: 1
(err): 1
(node: 3
(node): 3
(node.left: 1
(this.root: 1
(true): 1
(word): 1
*/: 1
+: 2
+=: 7
/*global: 1
/*jslint: 1
0;: 2
1;: 4
4,: 1
50,: 1
:: 12
<: 1
=: 25
===: 8
BST: 1
BST();: 1
BST,: 2
BST.prototype: 1
Node: 1
Node(data,: 1
Node,: 2
Node.prototype: 1
break;: 3
browser: 1
console*/: 1
console.log(err);: 1
console.log(node.show());: 1
constructor:: 2
continue: 1
count:: 1
current: 7
current,: 1
current.count: 1
current.data): 2
current.data;: 2
current.left;: 2
current.right;: 2
current;: 3
data): 1
data.toString().split(/\s+/).forEach(function: 1
data;: 1
devel: 1
edges:: 1
else: 3
false,: 2
fs: 1
fs.readFile('sample5.js',: 1
function: 8
function(err,: 1
if: 12
inOrder:: 1
indent: 1
insert:: 1
left,: 1
left;: 1
max:: 1
maxerr: 1
min:: 1
n: 1
n;: 3
new: 2
newcap: 1
node.right: 1
nomen: 1
null: 1
null): 11
null),: 1
null,: 1
null;: 1
num: 8
num;: 2
parent: 1
parent.left: 1
parent.right: 1
parent;: 1
plusplus: 1
regexp: 1
require('fs'),: 1
return: 7
right): 1
right;: 1
show:function: 1
sloppy: 1
this.count: 1
this.count(node.left);: 1
this.count(node.right);: 1
this.count;: 1
this.data: 2
this.edges(node.left);: 1
this.edges(node.right);: 1
this.inOrder(node.left);: 1
this.inOrder(node.right);: 1
this.left: 1
this.right: 1
this.root: 2
this.root;: 3
true: 1
true,: 7
var: 6
vars: 1
while: 3
white: 1
words: 1
words.inOrder(words.root);: 1
words.insert(word);: 1
words;: 1
{: 31
}: 20
});: 2
},: 5
};: 4
$