利用JS實現(xiàn)二叉樹遍歷算法實例代碼
前言
在計算機科學中, 樹(tree) 是一種廣泛使用的抽象數據類型(ADT)，是一類非線性數據結構。樹在計算機領域得到廣泛應用，尤其二叉樹最為常用。
樹的相關概念：
- 結點：每個元素稱為結點
- 樹根：根節(jié)點
- 度：一個結點含有的子結點的個數稱為該結點的度
- 葉子節(jié)點：度為0的節(jié)點
一、二叉樹
概念：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹。
1.1、遍歷二叉樹
二叉樹有兩種遍歷深度遍歷和廣度遍歷，其中深度遍歷有前序、 中序和后序三種遍歷方法。 廣度遍歷就是層次遍歷，按層的順序一層一層遍歷。
四種遍歷的主要思想：
- 前序：先訪問根，然后訪問左子樹，最后訪問右子樹，DLR。
- 中序：先訪問左子樹，然后訪問根，最后訪問右子樹，LDR。
- 后序：先后訪問左子樹，然后訪問右子樹，最后訪問根，LRD。
- 廣度：按層的順序一層一層遍歷。
例如a+b*(c-d)-e/f,該表達式用二叉樹表示：
對他分別進行遍歷：
- 前序：-+a*b-cd/ef
- 中序：a+b*c-d-e/f
- 后序：abcd-*+ef/-
- 廣度：-+/a*efb-cd
1.2、用js表示二叉樹
我們用js的對象來表示二叉樹，對象擁有三個屬性，left、value、right,分別是左子樹，值和右子樹，上面a+b*(c-d)-e/f的例子我們用js可以這樣表示。
var tree = {
value: '-',
left: {
value: '+',
left: {
value: 'a'
},
right: {
value: '*',
left: {
value: 'b'
},
right: {
value: '-',
left: {
value: 'c'
},
right: {
value: 'd'
}
}
}
},
right: {
value: '/',
left: {
value: 'e'
},
right: {
value: 'd'
}
}
}
1.3、前序遍歷算法
前序：有兩種方法，第一種很簡單就是直接使用遞歸的辦法。
function preOrder(treeNode) {
if(treeNode) {
console.log(treeNode.value); // 打印出來代表訪問這個節(jié)點
preOrder(treeNode.left);
preOrder(treeNode.right);
}
}
算法思路很簡單，先遍歷根節(jié)點，然后遞歸遍歷左子樹，左子樹遍歷結束后，遞歸右子樹。
第二種非遞歸遍歷
function preOrder(treeNode) {
if(treeNode) {
var stack = [treeNode]; //將二叉樹壓入棧
while (stack.length !== 0) {
treeNode = stack.pop(); // 取棧頂
document.getElementById('text').appendChild(document.createTextNode(treeNode.value)); // 訪問節(jié)點
if(treeNode.right) stack.push(treeNode.right); // 把右子樹入棧
if(treeNode.left) stack.push(treeNode.left); // 把左子樹入棧
}
}
}
第二種是使用棧的思想，我們都知道，棧是先進后出的一種數據結構，我們先把根節(jié)點入棧，然后取棧頂，訪問根節(jié)點，分別把右左子樹入棧，這邊必須右邊先入棧，因為我們是要先從左邊開始訪問的，所以右子樹先入棧，然后就循環(huán)取出棧，直到棧空。
1.4、中序遍歷算法
中序遞歸算法：
function InOrder(treeNode) {
if(treeNode) {
InOrder(treeNode.left);
document.getElementById('text').appendChild(document.createTextNode(treeNode.value));
InOrder(treeNode.right);
}
}
和前序遞歸算法同樣的思路，只是訪問節(jié)點位置不同
第二種：
function InOrder(node) {
if(node) {
var stack = []; // 建空棧
//如果棧不為空或結點不為空，則循環(huán)遍歷
while (stack.length !== 0 || node) {
if (node) { //如果結點不為空
stack.push(node); //將結點壓入棧
node = node.left; //將左子樹作為當前結點
} else { //左子樹為空，即沒有左子樹的情況
node = stack.pop(); //將結點取出來
document.getElementById('text').appendChild(document.createTextNode(node.value));
node = node.right; //將右結點作為當前結點
}
}
}
}
非遞歸中序算法的思想就是，把當前節(jié)點入棧，然后遍歷左子樹，如果左子樹存在就一直入棧，直到左子樹為空，訪問但前節(jié)點，然后讓右子樹入棧。
1.5、后序遍歷算法
第一種：遞歸遍歷算法
function postOrder(node) {
if (node) { //判斷二叉樹是否為空
postOrder(node.left); //遞歸遍歷左子樹
postOrder(node.right); //遞歸遍歷右子樹
document.getElementById('text').appendChild(document.createTextNode(node.value));
}
}
第二種：非遞歸遍歷算法
function postOrder(node) {
if (node) { //判斷二叉樹是否為空
var stack = [node]; //將二叉樹壓入棧
var tmp = null; //定義緩存變量
while (stack.length !== 0) { //如果棧不為空，則循環(huán)遍歷
tmp = stack[stack.length - 1]; //將棧頂的值保存在tmp中
if (tmp.left && node !== tmp.left && node !== tmp.right) { //如果存在左子樹,node !== tmp.left && node !== tmp.righ 是為了避免重復將左右子樹入棧
stack.push(tmp.left); //將左子樹結點壓入棧
} else if (tmp.right && node !== tmp.right) { //如果結點存在右子樹
stack.push(tmp.right); //將右子樹壓入棧中
} else {
document.getElementById('text').appendChild(document.createTextNode(stack.pop().value));
node = tmp;
}
}
}
}
這里使用了一個tmp變量來記錄上一次出棧、入棧的結點。思路是先把根結點和左樹推入棧，然后取出左樹，再推入右樹，取出，最后取根結點。
下面是用這個算法遍歷前面那個二叉樹的過程
stack tmp node 打印
初始 ： - null -
第1輪： -+ - -
第2輪： -+a + -
第3輪： -+ a a a
第4輪： -+* + a
第5輪： -+*b * a
第6輪： -+* b b b
第7輪： -+*- * b
第8輪： -+*-c - b
第9輪： -+*- c c c
第10輪： -+*-d - c
第11輪： -+*- d d d
第12輪： -+* - - -
第13輪： -+ * * *
第14輪： - + + +
第15輪： -/ - +
第16輪： -/e / +
第17輪： -/ e e e
第18輪： -/f / e
第19輪： -/ f f f
第20輪： - / / /
第21輪： - - -結果：abcd-*+ef/-
1.6、按層遍歷算法
function breadthTraversal(node) {
if (node) { //判斷二叉樹是否為空
var que = [node]; //將二叉樹放入隊列
while (que.length !== 0) { //判斷隊列是否為空
node = que.shift(); //從隊列中取出一個結點
document.getElementById('text').appendChild(document.createTextNode(node.value)); //將取出結點的值保存到數組
if (node.left) que.push(node.left); //如果存在左子樹，將左子樹放入隊列
if (node.right) que.push(node.right); //如果存在右子樹，將右子樹放入隊列
}
}
}
使用數組模擬隊列，首先將根結點歸入隊列。當隊列不為空時，執(zhí)行循環(huán)：取出隊列的一個結點，如果該節(jié)點有左子樹，則將該節(jié)點的左子樹存入隊列；如果該節(jié)點有右子樹，則將該節(jié)點的右子樹存入隊列。
二、算法題
1.1、二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數。
比如下面這個二叉樹，返回深度3。
3
/ \
9 20
/ \
15 7const tree = {
value: 3,
left: {
value: 9
},
right: {
value: 20,
left: { value: 15 },
right: { value: 9 }
}
}
遞歸算法：遞歸算法的思路很簡單，先拿到左子樹最深層，再拿到右子樹最深層，取他們最大值就是樹的深度。
var maxDepth = function(root) {
if (!root) {
return 0;
}
const leftDeep = maxDepth(root.left) + 1;
const rightDeep = maxDepth(root.right) + 1;
return Math.max(leftDeep, rightDeep);
};
/*
maxDepth(root) = maxDepth(root.left) + 1 = 2
maxDepth(root.left) = maxDepth(root.left.left) + 1 = 1
maxDepth(root.left.left) = 0;
maxDepth(root) = maxDepth(root.right) + 1 = 3
maxDepth(root.right) = maxDepth(root.right.right) + 1 = 2
maxDepth(root.right.right) = maxDepth(root.right.right.right) + 1 = 1
maxDepth(root.right.right.right) = 0
*/
1.2、二叉樹的所有路徑
給定一個二叉樹，返回所有從根節(jié)點到葉子節(jié)點的路徑。
比如：
3
/ \
9 20
/ \
15 7
返回：['3->9', '3->20->15', '3->20->7']
使用遞歸的方法：
var binaryTreePaths = function(root) {
if (!root) return [];
const res = [];
function dfs(curNode, curPath) {
if(!curNode.left && !curNode.right) {
res.push(curPath);
}
if(curNode.left) {
dfs(curNode.left, `${curPath}->${curNode.left.value}`)
}
if(curNode.right) {
dfs(curNode.right, `${curPath}->${curNode.right.value}`)
}
}
dfs(root, `${root.value}`);
return res;
};
總結
到此這篇關于利用JS實現(xiàn)二叉樹遍歷算法的文章就介紹到這了,更多相關JS二叉樹遍歷算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文主要分享了Js數組返回去重后的數據的實例代碼。具有一定的參考價值，下面跟著小編一起來看下吧2017-01-01
這篇文章主要幫助大家理解javascript定時器中的單線程，感興趣的小伙伴們可以參考一下2016-02-02
這篇文章主要介紹了js function定義函數的幾種方法,需要的朋友可以參考下2014-02-02
響應式網站設計(Responsive?Web?design)是一種網絡頁面設計布局,是目前比較流行的一種網頁設計,下面這篇文章主要給大家介紹了關于three.js響應式設計的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-04-04
這篇文章主要為大家詳細介紹了js HTML5 Canvas繪制轉盤抽獎，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-08-08
這篇文章主要介紹了js數組相減,結合簡單示例形式分析了JavaScript刪除a數組所有與b數組相同元素相關個遍歷、判斷、刪除等相關操作技巧,需要的朋友可以參考下2020-03-03
重載toString實現(xiàn)JS HashMap分析
用過Java的都知道，里面有個功能強大的數據結構——HashMap，它能提供鍵與值的對應訪問。不過熟悉JS的朋友也會說，JS里面到處都是hashmap，因為每個對象都提供了map[key]的訪問形式。2011-03-03
本文為大家介紹下js如何獲取IP和PcName在IE下測試，代碼如下，有需要的朋友可以參考下，希望對大家有所幫助2013-08-08
Javascript 判斷是否存在函數，此功能如何實現(xiàn)，接下來為您介紹解決方法，需要了解的朋友可以參考下2013-01-01
這篇文章主要為大家詳細介紹了原生JS實現(xiàn)滑動按鈕效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11