JavaScript - Binary Trees and Binary Search Trees(counting the number of edges)

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 2.(No. 6428)を解いてみる。

Exercises 2.(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;

Node = function (data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
};
Node.prototype = {
    constructor: Node,
    show:function () {
        return this.data;
    }
};
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 = 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;
    }
};

var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log(nums.edges(nums.root));

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample2.js

sample2.js is OK.
$ node sample2.js
4
$