本文實例講述了JS實現(xiàn)的二叉樹算法。分享給大家供大家參考，具體如下：
<!DOCTYPE HTML><head> <title>20130328BinaryTree</title> <metahttp-equiv="Content-Type" content="text/html; charset=utf-8" /></head><html><body><script> //今天學習了下二叉樹算法，總結在這里 //1全局變量 binary Tree =bt //1.1 node function Node() { //bt節(jié)點 this.text = ''; //節(jié)點的文本 this.leftChild = null; //節(jié)點的左孩子引用 this.rightild = null; //節(jié)點右孩子引用 } //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 ; //數(shù)組的長度 var nodes = new Array(); //創(chuàng)建一個臨時數(shù)組，用于存放二叉樹節(jié)點 //循環(huán)創(chuàng)建二叉樹節(jié)點存放到數(shù)組中 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(); //存放棧的數(shù)組 //壓棧 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); //現(xiàn)在棧中有一個元素 stack.isEmpty(); //false , 棧不為空 //alert(stack.pop()); //出棧, 打印1 stack.isEmpty(); //true, 此時棧為空，因為在調用了stack.pop()之后元素出棧了，所以為空 //2.1遞歸實現(xiàn)： function buildBt1(node, i) { var leftIndex = 2*i+1, //左孩子節(jié)點的索引 rightIndex = 2*i+2; //右孩子節(jié)點的索引 if(leftIndex < charecters.length) { //判斷索引的長度是否超過了charecters數(shù)組的大小 var childNode = new Node(); //創(chuàng)建一個新的節(jié)點對象 childNode.text = charecters[leftIndex]; //給節(jié)點賦值 node.leftChild = childNode; //給當前節(jié)點node加入左孩子節(jié)點 buildBt1(childNode, leftIndex); //遞歸創(chuàng)建左孩子 } if(rightIndex < charecters.length) { //同上 var childNode = new Node(); childNode.text = charecters[rightIndex]; node.rightChild = childNode; buildBt1(childNode, rightIndex); } } //2.2非遞歸實現(xiàn) function buildBt2() { index = 0; //索引從0開始 //循環(huán)建立二叉樹子節(jié)點的引用 while(index < len) { var leftIndex = 2*index+1, //當前節(jié)點左孩子索引 rightIndex = 2*index+2; //當前節(jié)點右孩子索引 //給當前節(jié)點添加左孩子 nodes[index].leftChild = nodes[leftIndex]; //給當前節(jié)點添加右孩子 nodes[index].rightChild = nodes[rightIndex]; index++; } } //3遍歷 //3.1.1先序遞歸遍歷 function firstIteration(node) { if(node.leftChild) { //判斷當前節(jié)點是否有左孩子 firstIteration(node.leftChild); //遞歸左孩子 } if(node.rightChild) { //判斷當前節(jié)點是否有右孩子 firstIteration(node.rightChild); //遞歸右孩子 } } //遞歸遍歷二叉樹 firstIteration(root); //3.1.2先序普通遍歷 function notFirstIteration(node) { var stack = new Stack(), //開辟一個新的棧對象 resultText = ''; //存放非遞歸遍歷之后的字母順序 stack.push(root); //這個root在上面非遞歸方式構建二叉樹的時候已經(jīng)構建好的 var node = root; resultText += node.text; while(!stack.isEmpty()) { while(node.leftChild) { //判斷當前節(jié)點是否有左孩子節(jié)點 node = node.leftChild; //取當前節(jié)點的左孩子節(jié)點 resultText += node.text; //訪問當前節(jié)點 stack.push(node); //將當前節(jié)點壓入棧中 } stack.pop(); //出棧 node = stack.pop().rightChild; //訪問當前節(jié)點的兄弟節(jié)點（右孩子節(jié)點） if(node) { //當前節(jié)點的兄弟節(jié)點不為空 resultText += node.text; //訪問當前節(jié)點 stack.push(node); //將當前節(jié)點壓入棧中 } else { //當前節(jié)點的兄弟節(jié)點為空 node = stack.pop(); //在回溯到上一層 } } } //非遞歸先序遍歷 // notFirstIteration(root); //3.2.1中序遞歸遍歷 function btIteration21(node) { //訪問左節(jié)點 if(node.leftChild) { if(node.leftChild.leftChild) { btIteration21(node.leftChild); } else { strText += node.leftChild.text; } } //訪問根節(jié)點 strText += node.text; //訪問右節(jié)點 if(node.rightChild) { if(node.rightChild.leftChild) { btIteration21(node.rightChild); } else { strText += node.rightChild.text; } } } //測試區(qū) //2.1.1測試遞歸實現(xiàn) var node = new Node(); node.text = charecters[0]; buildBt1(node, 0); //索引i是從0開始構建 btIteration21(node); alert(strText);</script></body></html>更多關于JavaScript相關內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結構與算法技巧總結》、《JavaScript數(shù)學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答
