開発環境
- 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 3.(No. 6428)を解いてみる。
Exercises 3.(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;
},
max: function () {
var current = this.root;
if (current === null) {
return current;
}
while (current.right !== null) {
current = current.right;
}
return current.data;
}
};
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.max());
出力結果(Terminal, shell, SpiderMonkey)
$ jslint sample3.js
sample3.js is OK.
$ node sample3.js
99
$
0 コメント:
コメントを投稿