溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關JS如何實現的二叉樹算法的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
具體如下：
<!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節點
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);
</script>
</body>
</html>感謝各位的閱讀！關于“JS如何實現的二叉樹算法”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
