JS実装のツリーアルゴリズムの完全な例
5706 ワード
この例では,JS実装のツリーアルゴリズムについて述べる.皆さんの参考にしてください.具体的には以下の通りです.
JavaScriptに関する詳細について興味のある読者は、「JavaScriptデータ構造とアルゴリズムテクニック総括」、「JavaScript数学演算用法総括」、「JavaScriptソートアルゴリズム総括」、「JavaScript遍歴アルゴリズムとテクニック総括」、「JavaScript検索アルゴリズムテクニック総括」および「JavaScriptエラーとデバッグテクニック総括」のトピックを参照してください.
JavaScriptプログラムの設計に役立つことを願っています.
20130328BinaryTree
// ,
//1 binary Tree =bt
//1.1 node
function Node() { //bt
this.text = ''; //
this.leftChild = null; //
this.rightild = null; //
}
//1.2
var strText = "";
var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
var len = charecters.length ; //
var nodes = new Array(); // ,
//
for (var i = 0 ; i < len ; i++) {
var node = new Node();
node.text = charecters[i];
nodes.push(node);
}
var root = nodes[0];
//1.3
function Stack() {
var stack = new Array(); //
//
this.push = function(o) {
stack.push(o);
};
//
this.pop = function() {
var o = stack[stack.length-1];
stack.splice(stack.length-1, 1);
return o;
};
//
this.isEmpty = function() {
if(stack.length <= 0) {
return true;
}
else {
return false;
}
};
}
//
var stack = new Stack();
stack.push(1); //
stack.isEmpty(); //false ,
//alert(stack.pop()); // , 1
stack.isEmpty(); //true, , stack.pop() ,
//2.1 :
function buildBt1(node, i) {
var leftIndex = 2*i+1, //
rightIndex = 2*i+2; //
if(leftIndex < charecters.length) { // charecters
var childNode = new Node(); //
childNode.text = charecters[leftIndex]; //
node.leftChild = childNode; // node
buildBt1(childNode, leftIndex); //
}
if(rightIndex < charecters.length) { //
var childNode = new Node();
childNode.text = charecters[rightIndex];
node.rightChild = childNode;
buildBt1(childNode, rightIndex);
}
}
//2.2
function buildBt2() {
index = 0; // 0
//
while(index < len) {
var leftIndex = 2*index+1, //
rightIndex = 2*index+2; //
//
nodes[index].leftChild = nodes[leftIndex];
//
nodes[index].rightChild = nodes[rightIndex];
index++;
}
}
//3
//3.1.1
function firstIteration(node) {
if(node.leftChild) { //
firstIteration(node.leftChild); //
}
if(node.rightChild) { //
firstIteration(node.rightChild); //
}
}
//
firstIteration(root);
//3.1.2
function notFirstIteration(node) {
var stack = new Stack(), //
resultText = ''; //
stack.push(root); // root
var node = root;
resultText += node.text;
while(!stack.isEmpty()) {
while(node.leftChild) { //
node = node.leftChild; //
resultText += node.text; //
stack.push(node); //
}
stack.pop(); //
node = stack.pop().rightChild; // ( )
if(node) { //
resultText += node.text; //
stack.push(node); //
}
else { //
node = stack.pop(); //
}
}
}
//
// notFirstIteration(root);
//3.2.1
function btIteration21(node) {
//
if(node.leftChild) {
if(node.leftChild.leftChild) {
btIteration21(node.leftChild);
}
else {
strText += node.leftChild.text;
}
}
//
strText += node.text;
//
if(node.rightChild) {
if(node.rightChild.leftChild) {
btIteration21(node.rightChild);
}
else {
strText += node.rightChild.text;
}
}
}
//
//2.1.1
var node = new Node();
node.text = charecters[0];
buildBt1(node, 0); // i 0
btIteration21(node);
alert(strText);
JavaScriptに関する詳細について興味のある読者は、「JavaScriptデータ構造とアルゴリズムテクニック総括」、「JavaScript数学演算用法総括」、「JavaScriptソートアルゴリズム総括」、「JavaScript遍歴アルゴリズムとテクニック総括」、「JavaScript検索アルゴリズムテクニック総括」および「JavaScriptエラーとデバッグテクニック総括」のトピックを参照してください.
JavaScriptプログラムの設計に役立つことを願っています.