溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關(guān)JS如何實現(xiàn)的二叉樹算法的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
具體如下：
<!DOCTYPE HTML>
<head>
<title>20130328BinaryTree</title>
<metahttp-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<html>
<body>
<script>
//今天學(xué)習(xí)了下二叉樹算法，總結(jié)在這里
//1全局變量 binary Tree =bt
//1.1 node
function Node() { //bt節(jié)點(diǎn)
this.text = ''; //節(jié)點(diǎn)的文本
this.leftChild = null; //節(jié)點(diǎn)的左孩子引用
this.rightild = null; //節(jié)點(diǎn)右孩子引用
}
//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é)點(diǎn)
//循環(huán)創(chuàng)建二叉樹節(jié)點(diǎn)存放到數(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, 此時棧為空，因為在調(diào)用了stack.pop()之后元素出棧了，所以為空
//2.1遞歸實現(xiàn)：
function buildBt1(node, i) {
var leftIndex = 2*i+1, //左孩子節(jié)點(diǎn)的索引
rightIndex = 2*i+2; //右孩子節(jié)點(diǎn)的索引
if(leftIndex < charecters.length) { //判斷索引的長度是否超過了charecters數(shù)組的大小
var childNode = new Node(); //創(chuàng)建一個新的節(jié)點(diǎn)對象
childNode.text = charecters[leftIndex]; //給節(jié)點(diǎn)賦值
node.leftChild = childNode; //給當(dāng)前節(jié)點(diǎn)node加入左孩子節(jié)點(diǎn)
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é)點(diǎn)的引用
while(index < len) {
var leftIndex = 2*index+1, //當(dāng)前節(jié)點(diǎn)左孩子索引
rightIndex = 2*index+2; //當(dāng)前節(jié)點(diǎn)右孩子索引
//給當(dāng)前節(jié)點(diǎn)添加左孩子
nodes[index].leftChild = nodes[leftIndex];
//給當(dāng)前節(jié)點(diǎn)添加右孩子
nodes[index].rightChild = nodes[rightIndex];
index++;
}
}
//3遍歷
//3.1.1先序遞歸遍歷
function firstIteration(node) {
if(node.leftChild) { //判斷當(dāng)前節(jié)點(diǎn)是否有左孩子
firstIteration(node.leftChild); //遞歸左孩子
}
if(node.rightChild) { //判斷當(dāng)前節(jié)點(diǎn)是否有右孩子
firstIteration(node.rightChild); //遞歸右孩子
}
}
//遞歸遍歷二叉樹
firstIteration(root);
//3.1.2先序普通遍歷
function notFirstIteration(node) {
var stack = new Stack(), //開辟一個新的棧對象
resultText = ''; //存放非遞歸遍歷之后的字母順序
stack.push(root); //這個root在上面非遞歸方式構(gòu)建二叉樹的時候已經(jīng)構(gòu)建好的
var node = root;
resultText += node.text;
while(!stack.isEmpty()) {
while(node.leftChild) { //判斷當(dāng)前節(jié)點(diǎn)是否有左孩子節(jié)點(diǎn)
node = node.leftChild; //取當(dāng)前節(jié)點(diǎn)的左孩子節(jié)點(diǎn)
resultText += node.text; //訪問當(dāng)前節(jié)點(diǎn)
stack.push(node); //將當(dāng)前節(jié)點(diǎn)壓入棧中
}
stack.pop(); //出棧
node = stack.pop().rightChild; //訪問當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)（右孩子節(jié)點(diǎn)）
if(node) { //當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)不為空
resultText += node.text; //訪問當(dāng)前節(jié)點(diǎn)
stack.push(node); //將當(dāng)前節(jié)點(diǎn)壓入棧中
}
else { //當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為空
node = stack.pop(); //在回溯到上一層
}
}
}
//非遞歸先序遍歷
// notFirstIteration(root);
//3.2.1中序遞歸遍歷
function btIteration21(node) {
//訪問左節(jié)點(diǎn)
if(node.leftChild) {
if(node.leftChild.leftChild) {
btIteration21(node.leftChild);
}
else {
strText += node.leftChild.text;
}
}
//訪問根節(jié)點(diǎn)
strText += node.text;
//訪問右節(jié)點(diǎn)
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開始構(gòu)建
btIteration21(node);
alert(strText);
</script>
</body>
</html>感謝各位的閱讀！關(guān)于“JS如何實現(xiàn)的二叉樹算法”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼