利用JS實現(xiàn)二叉樹遍歷算法實例代碼
前言
在計算機科學(xué)中, 樹(tree) 是一種廣泛使用的抽象數(shù)據(jù)類型(ADT)，是一類非線性數(shù)據(jù)結(jié)構(gòu)。樹在計算機領(lǐng)域得到廣泛應(yīng)用，尤其二叉樹最為常用。
樹的相關(guān)概念：
- 結(jié)點：每個元素稱為結(jié)點
- 樹根：根節(jié)點
- 度：一個結(jié)點含有的子結(jié)點的個數(shù)稱為該結(jié)點的度
- 葉子節(jié)點：度為0的節(jié)點
一、二叉樹
概念：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹。
1.1、遍歷二叉樹
二叉樹有兩種遍歷深度遍歷和廣度遍歷，其中深度遍歷有前序、 中序和后序三種遍歷方法。 廣度遍歷就是層次遍歷，按層的順序一層一層遍歷。
四種遍歷的主要思想：
- 前序：先訪問根，然后訪問左子樹，最后訪問右子樹，DLR。
- 中序：先訪問左子樹，然后訪問根，最后訪問右子樹，LDR。
- 后序：先后訪問左子樹，然后訪問右子樹，最后訪問根，LRD。
- 廣度：按層的順序一層一層遍歷。
例如a+b*(c-d)-e/f,該表達(dá)式用二叉樹表示：
對他分別進(jìn)行遍歷：
- 前序：-+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é)點，然后遞歸遍歷左子樹，左子樹遍歷結(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); // 把左子樹入棧
}
}
}
第二種是使用棧的思想，我們都知道，棧是先進(jìn)后出的一種數(shù)據(jù)結(jié)構(gòu)，我們先把根節(jié)點入棧，然后取棧頂，訪問根節(jié)點，分別把右左子樹入棧，這邊必須右邊先入棧，因為我們是要先從左邊開始訪問的，所以右子樹先入棧，然后就循環(huán)取出棧，直到?？铡?/p>
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 = []; // 建空棧
//如果棧不為空或結(jié)點不為空，則循環(huán)遍歷
while (stack.length !== 0 || node) {
if (node) { //如果結(jié)點不為空
stack.push(node); //將結(jié)點壓入棧
node = node.left; //將左子樹作為當(dāng)前結(jié)點
} else { //左子樹為空，即沒有左子樹的情況
node = stack.pop(); //將結(jié)點取出來
document.getElementById('text').appendChild(document.createTextNode(node.value));
node = node.right; //將右結(jié)點作為當(dāng)前結(jié)點
}
}
}
}
非遞歸中序算法的思想就是，把當(dāng)前節(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]; //將棧頂?shù)闹当４嬖趖mp中
if (tmp.left && node !== tmp.left && node !== tmp.right) { //如果存在左子樹,node !== tmp.left && node !== tmp.righ 是為了避免重復(fù)將左右子樹入棧
stack.push(tmp.left); //將左子樹結(jié)點壓入棧
} else if (tmp.right && node !== tmp.right) { //如果結(jié)點存在右子樹
stack.push(tmp.right); //將右子樹壓入棧中
} else {
document.getElementById('text').appendChild(document.createTextNode(stack.pop().value));
node = tmp;
}
}
}
}
這里使用了一個tmp變量來記錄上一次出棧、入棧的結(jié)點。思路是先把根結(jié)點和左樹推入棧，然后取出左樹，再推入右樹，取出，最后取根結(jié)點。
下面是用這個算法遍歷前面那個二叉樹的過程
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輪： - - -結(jié)果：abcd-*+ef/-
1.6、按層遍歷算法
function breadthTraversal(node) {
if (node) { //判斷二叉樹是否為空
var que = [node]; //將二叉樹放入隊列
while (que.length !== 0) { //判斷隊列是否為空
node = que.shift(); //從隊列中取出一個結(jié)點
document.getElementById('text').appendChild(document.createTextNode(node.value)); //將取出結(jié)點的值保存到數(shù)組
if (node.left) que.push(node.left); //如果存在左子樹，將左子樹放入隊列
if (node.right) que.push(node.right); //如果存在右子樹，將右子樹放入隊列
}
}
}
使用數(shù)組模擬隊列，首先將根結(jié)點歸入隊列。當(dāng)隊列不為空時，執(zhí)行循環(huán)：取出隊列的一個結(jié)點，如果該節(jié)點有左子樹，則將該節(jié)點的左子樹存入隊列；如果該節(jié)點有右子樹，則將該節(jié)點的右子樹存入隊列。
二、算法題
1.1、二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點到最遠(yuǎn)葉子節(jié)點的最長路徑上的節(jié)點數(shù)。
比如下面這個二叉樹，返回深度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;
};
總結(jié)
到此這篇關(guān)于利用JS實現(xiàn)二叉樹遍歷算法的文章就介紹到這了,更多相關(guān)JS二叉樹遍歷算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
js數(shù)組的基本用法及數(shù)組根據(jù)下標(biāo)(數(shù)值或字符)移除元素
js數(shù)組的用法包括創(chuàng)建、取值賦值、添加以及根據(jù)下標(biāo)(數(shù)值或字符)移除元素等等，在本文將為大家詳細(xì)介紹下，感興趣的朋友可以參考下2013-10-10
實現(xiàn)一個五子棋游戲, 簡要分析其原理, 頁面并沒有很花哨, 原理搞懂了, 后面的就是很輕松的事了,本文給大家介紹了如何用純JS實現(xiàn)一個五子棋游戲,文中通過代碼示例給大家介紹的非常詳細(xì),具有一定的參考價值,需要的朋友可以參考下2023-12-12
點擊按鈕怎么跳轉(zhuǎn)到另外一個頁面呢？點擊圖片要跳轉(zhuǎn)到新的頁面時，怎么做到呢？可以使用onclick=window.location=新頁面來實現(xiàn)2014-10-10
Bootstrap 輪播（Carousel）插件是一種靈活的響應(yīng)式的向站點添加滑塊的方式。這篇文章主要介紹了使用BootStrap進(jìn)行輪播圖的制作的相關(guān)資料,需要的朋友可以參考下2017-01-01
這篇文章主要為大家詳細(xì)介紹了JavaScript實現(xiàn)拖拽功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了axios請求參數(shù)的三種方式,本文結(jié)合實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-07-07
這篇文章給大家介紹了greenbrower用到的function.js代碼集合，感興趣的朋友一起看看吧2007-12-12
這篇文章主要介紹了如何利用JavaScript?實現(xiàn)繼承，JavaScript?在編程語言界是個特殊種類，它和其他編程語言很不一樣，JavaScript可以在運行的時候動態(tài)地改變某個變量的類型,下面小編將繼續(xù)介紹JavaScript如何實現(xiàn)繼承,需要的朋友可以參考下2022-02-02
這篇文章主要為大家分享了關(guān)于javascript實現(xiàn)上周、上個月的處理方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-02-02
uniapp使用u-upload組件來實現(xiàn)圖片上傳功能
最近在用uniapp開發(fā)微信小程序,下面這篇文章主要給大家介紹了關(guān)于uniapp使用u-upload組件來實現(xiàn)圖片上傳功能的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01