二叉樹是數(shù)據(jù)結(jié)構(gòu)中很重要的一個部分，也是程序猿們必備的知識點(diǎn)廓潜。也許我們在平時的業(yè)務(wù)開發(fā)中不會用到這類“泛泛而談”的算法阱佛，而且就算是數(shù)據(jù)庫，文件系統(tǒng)這類對檢索排序性能要求很高的系統(tǒng)耍缴，也一般使用更復(fù)雜的樹結(jié)構(gòu)（特別是B樹）砾肺，但作為最基本最典型的排序樹，二叉樹是我們學(xué)習(xí)編程思想防嗡，深入算法的一條重要途徑变汪。
廢話不多說，這里將展示JS實(shí)現(xiàn)二叉樹的深度優(yōu)先（前序蚁趁，中序裙盾，后序）遍歷和廣度優(yōu)先遍歷算法，每種遍歷法都有遞歸和非遞歸兩種思路荣德。若對二叉樹的概念和特性還不是特別了解闷煤，可以參考：
二叉樹的幾種遍歷方式
-
深度優(yōu)先搜索(Depth First Search)，深度優(yōu)先遍歷又分為以下三種方式：
- 前序遍歷(Preorder Traversal 亦稱（先序遍歷））：訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前涮瞻。
- 中序遍歷(Inorder Traversal)：訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）鲤拿。
- 后序遍歷(Postorder Traversal)：訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。
-
廣度優(yōu)先搜索(Breadth First Search)：按照樹的層次署咽，每層從左至右依次遍歷
二叉樹結(jié)構(gòu).jpg
如上圖所示近顷，根據(jù)幾種遍歷方式生音，遍歷結(jié)果如下：
- 前序遍歷：1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 7
- 中序遍歷：8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 3, 7
- 后序遍歷：8, 9, 4, 10, 11, 5, 2, 12, 6, 7, 3, 1
- 廣度優(yōu)先遍歷：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
根據(jù)上圖所示的二叉樹結(jié)構(gòu)，先寫出JS的對象形式：
const tree = {
data: 1,
left: {
data: 2,
left: {
data: 4,
left: {
data: 8,
},
right: {
data: 9
}
},
right: {
data: 5,
left: {
data: 10,
},
right: {
data: 11
}
}
},
right: {
data: 3,
left: {
data: 6,
left: {
data: 12
}
},
right: {
data: 7
}
}
}
接下來解析每種遍歷方式的算法窒升，每種遍歷方式都給出了遞歸和非遞歸兩種形式缀遍。為了便于解釋，先定義一個“節(jié)點(diǎn)組合”：一個根節(jié)點(diǎn)與其左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的組合饱须。（以下解析中域醇，“訪問”是一次touch，不會讀取出節(jié)點(diǎn)的值蓉媳，不同于“搜索”或“讀取”）譬挚。
前序遍歷
一、 遞歸算法
思路：每開始訪問一個節(jié)點(diǎn)組合的時候酪呻，總是先讀取其根節(jié)點(diǎn)的值减宣，再訪問其左子節(jié)點(diǎn)樹，最后訪問其右子節(jié)點(diǎn)樹玩荠。于是設(shè)想：每個節(jié)點(diǎn)組合的遍歷作為一次遞歸漆腌，不斷按照此規(guī)律進(jìn)行遍歷，直至所有節(jié)點(diǎn)遍歷完成阶冈。
/**
* 遞歸法前序遍歷
*/
function dfsPreorderByRcs(tree) {
const output = [];
const visitLoop = (node) => {
if (node) {
// 先搜索出根節(jié)點(diǎn)的值闷尿，push進(jìn)結(jié)果列表
output.push(node.data);
// 訪問左子節(jié)點(diǎn)樹，左子節(jié)點(diǎn)開始作為根節(jié)點(diǎn)進(jìn)行下一輪遞歸
visitLoop(node.left);
// 同上述女坑，遞歸遍歷右子節(jié)點(diǎn)
visitLoop(node.right);
}
}
visitLoop(tree);
return output;
}
console.log('遞歸法DFS(前序): ', dfsPreorderByRcs(tree));
// 遞歸法DFS(前序): [ 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 7 ]
二悠砚、非遞歸算法
思路：不用遞歸，那就肯定要用循環(huán)了堂飞，但如何保證搜索的順序呢？可以用數(shù)組來記錄訪問順序绑咱，并且每次從這個順序數(shù)組中依次取出節(jié)點(diǎn)對象進(jìn)行搜索绰筛，這樣只要保證數(shù)組中要搜索的節(jié)點(diǎn)順序是正常的就完成了。那又如何正確的記錄順序呢描融？每訪問一個節(jié)點(diǎn)組合铝噩，總是搜索其根節(jié)點(diǎn)值，然后將其左子節(jié)點(diǎn)樹push進(jìn)順序數(shù)組中窿克，再將其右子節(jié)點(diǎn)樹push進(jìn)順序數(shù)組中骏庸，但是最后push進(jìn)的節(jié)點(diǎn)需要先讀取出來，這樣就是一個先進(jìn)后出的棧結(jié)構(gòu)了年叮。
既然是棧結(jié)構(gòu)具被，為了方便記錄，那就用數(shù)組構(gòu)造一個棧吧：
/**
* 簡單構(gòu)造個棧結(jié)構(gòu)
*/
class Stack {
constructor() {
this.stackArr = [];
}
push(data) {
this.stackArr.unshift(data);
return this.stackArr.length;
}
pop() {
const popData = this.stackArr.shift();
return popData;
}
getItem(index) {
return this.stackArr[index];
}
clear() {
this.stackArr = [];
}
get isEmpty() {
return this.stackArr.length <= 0;
}
}
遍歷算法：
/**
* 非遞歸法前序遍歷
* 由于遍歷過程是先進(jìn)后出只损，所以使用棧結(jié)構(gòu)
*/
function dfsPreorderNonRcs(tree) {
const stack = new Stack();
const output = [];
stack.push(tree);
while (!stack.isEmpty) {
const pop = stack.pop();
if (pop) {
output.push(pop.data);
if (pop.right) {
stack.push(pop.right);
}
if (pop.left) {
stack.push(pop.left);
}
}
}
return output;
}
console.log('非遞歸DFS(前序): ', dfsPreorderNonRcs(tree));
// 非遞歸DFS(前序): [ 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 7 ]
中序遍歷
一一姿、遞歸算法
思路：和前序遞歸遍歷思路差不多七咧，但是順序上有點(diǎn)改變，先要搜索的是一個節(jié)點(diǎn)組合的左子節(jié)點(diǎn)叮叹，再搜索其根節(jié)點(diǎn)艾栋，最后是右子節(jié)點(diǎn)。
/**
* 遞歸法中序遍歷
*/
function dfsInorderByRcs(tree) {
const output = [];
const visitLoop = (node) => {
if (node) {
if (node.left) {
visitLoop(node.left);
}
output.push(node.data);
if (node.right) {
visitLoop(node.right);
}
}
};
visitLoop(tree);
return output;
}
console.log('遞歸法DFS(中序): ', dfsInorderByRcs(tree));
// 遞歸法DFS(中序): [ 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 3, 7 ]
二蛉顽、非遞歸算法
思路：和前序的非遞歸算法一樣的是蝗砾，需要一個棧結(jié)構(gòu)記錄遍歷的順序，但現(xiàn)在麻煩的一點(diǎn)是不能每次訪問一個節(jié)點(diǎn)組合的時候立馬讀取根節(jié)點(diǎn)的值携冤，然后按照讀取順序依次將節(jié)點(diǎn)push進(jìn)棧中了悼粮。這里有用到一種“回溯思想”。
步驟1：用一個變量存放當(dāng)前訪問的節(jié)點(diǎn)噪叙，若此節(jié)點(diǎn)存在左子節(jié)點(diǎn)矮锈，則將此節(jié)點(diǎn)對象push進(jìn)棧中，且將左子節(jié)點(diǎn)作為當(dāng)前訪問節(jié)點(diǎn)進(jìn)行下一輪循環(huán)
步驟2：若當(dāng)前訪問節(jié)點(diǎn)不存在左子節(jié)點(diǎn)睁蕾，則從棧中pop出這個節(jié)點(diǎn)苞笨，讀取這個節(jié)點(diǎn)的值，并且如果其存在右子節(jié)點(diǎn)子眶，則將右子節(jié)點(diǎn)作為當(dāng)前訪問節(jié)點(diǎn)進(jìn)行下一輪循環(huán)瀑凝。若左右子節(jié)點(diǎn)都不存在，則從棧中pop出其父節(jié)點(diǎn)臭杰，開始讀取父節(jié)點(diǎn)的右子節(jié)點(diǎn)粤咪。
/**
* 非遞歸法中序遍歷
*/
function dfsInorderNonRcs(tree) {
const output = [];
const stack = new Stack();
let node = tree;
while (!stack.isEmpty || node) {
if (node) {
stack.push(node);
node = node.left;
} else {
const pop = stack.pop();
output.push(pop.data);
if (pop.right) {
node = pop.right;
}
}
}
return output;
}
console.log('非遞歸法DFS(中序): ', dfsInorderNonRcs(tree));
// 非遞歸法DFS(中序): [ 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 3, 7 ]
后序遍歷
一、遞歸算法
思路：和前序及中序一樣渴杆，但先要搜索的是一個節(jié)點(diǎn)組合的左子節(jié)點(diǎn)寥枝，再搜索右子節(jié)點(diǎn)，最后才是根節(jié)點(diǎn)
/**
* 遞歸法后序遍歷
*/
function dfsPostorderByRcs(tree) {
const output = [];
const visitLoop = (node) => {
if (node) {
if (node.left) {
visitLoop(node.left);
}
if (node.right) {
visitLoop(node.right);
}
output.push(node.data);
}
};
visitLoop(tree);
return output;
}
console.log('遞歸法DFS(后序): ', dfsPostorderByRcs(tree));
// 遞歸法DFS(后序): [ 8, 9, 4, 10, 11, 5, 2, 12, 6, 7, 3, 1 ]
二磁奖、非遞歸算法
思路：對當(dāng)前訪問的節(jié)點(diǎn)增加一個touched屬性囊拜，用來標(biāo)志這個節(jié)點(diǎn)是否被訪問過其左子節(jié)點(diǎn)和右子節(jié)點(diǎn)了，判斷：
1比搭、當(dāng)左子節(jié)點(diǎn)未被訪問過冠跷，則將左子節(jié)點(diǎn)壓入棧中，并且左子節(jié)點(diǎn)作為當(dāng)前訪問節(jié)點(diǎn)身诺，開始下一輪循環(huán)判斷蜜托；
2、當(dāng)左子節(jié)點(diǎn)已被訪問霉赡，而右子節(jié)點(diǎn)未被訪問橄务，則將右子節(jié)點(diǎn)壓入棧中，并且右子節(jié)點(diǎn)作為當(dāng)前訪問節(jié)點(diǎn)同廉，開始下一輪循環(huán)判斷仪糖；
3柑司、當(dāng)左右子節(jié)點(diǎn)都被訪問過了，則讀取其值锅劝，然后從棧中取出其父節(jié)點(diǎn)攒驰，從步驟2開始判斷父節(jié)點(diǎn)是否可以被讀取值了（因?yàn)榛厮莸礁腹?jié)點(diǎn)了，那么父節(jié)點(diǎn)的左子節(jié)點(diǎn)肯定被搜索過了故爵，只是判斷當(dāng)前節(jié)點(diǎn)是否是父節(jié)點(diǎn)的右子節(jié)點(diǎn)玻粪，若是，則可以直接讀取父節(jié)點(diǎn)的值了）诬垂；
4劲室、如上述三個步驟，直至棧為空结窘。
/**
* 非遞歸法后序遍歷
*/
function dfsPostorderNonRcs(tree) {
const output = [];
const stack = new Stack();
let node = tree;
stack.push(tree);
while (!stack.isEmpty) {
if (node.left && !node.touched) {
node.touched = 'left';
node = node.left;
stack.push(node);
continue;
}
if (node.right && node.touched !== 'right') {
node.touched = 'right';
node = node.right;
stack.push(node);
continue;
}
const pop = stack.pop();
output.push(pop.data);
// 當(dāng)前訪問節(jié)點(diǎn)要改成父節(jié)點(diǎn)了很洋，所以從棧中取出父節(jié)點(diǎn)
// 但由于還沒確定是否可以讀取父節(jié)點(diǎn)的值，所以不能用pop
node = stack.getItem(0);
delete pop.touched;
}
return output;
}
console.log('非遞歸法DFS(后序): ', dfsPostorderNonRcs(tree));
// 非遞歸法DFS(后序): [ 8, 9, 4, 10, 11, 5, 2, 12, 6, 7, 3, 1 ]
廣度優(yōu)先遍歷
一隧枫、遞歸算法
思路：由于是一層一層從左至右訪問并直接讀取節(jié)點(diǎn)值喉磁，同一層中讀取了某個節(jié)點(diǎn)的值后，其右邊的節(jié)點(diǎn)并不一定與其有共同的父節(jié)點(diǎn)官脓，所以必須用一個順序結(jié)構(gòu)來記錄訪問的順序协怒，可以推出是個先進(jìn)先出的隊列結(jié)構(gòu)。
/**
* 遞歸法廣度優(yōu)先遍歷
*/
function bfsByRcs(tree) {
const queue = [];
const output = [];
const visitLoop = (node) => {
if (node) {
output.push(node.data);
if (node.left) {
queue.unshift(node.left);
}
if (node.right) {
queue.unshift(node.right);
}
visitLoop(queue.pop());
}
}
visitLoop(tree);
return output;
}
console.log('遞歸法BFS: ', bfsByRcs(tree));
// 遞歸法BFS: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]
二卑笨、非遞歸算法
思路：和遞歸法思路差不多孕暇，只是用while循環(huán)去替代遞歸就行了
/**
* 非遞歸法廣度優(yōu)先遍歷
*/
function bfsNonRcs(tree) {
const queue = [];
const output = [];
queue.push(tree);
while (queue.length > 0) {
const pop = queue.pop();
if (pop) {
output.push(pop.data);
if (pop.left) {
queue.unshift(pop.left);
}
if (pop.right) {
queue.unshift(pop.right);
}
}
}
return output;
}
console.log('非遞歸法BFS: ', bfsNonRcs(tree));
// 非遞歸法BFS: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]
求二叉樹的深度
二叉樹深度定義：從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑赤兴，最長路徑的長度為樹的深度妖滔。（其實(shí)就是二叉樹的最深層次），上述我們用的例子中的深度為4（一共有4層）桶良。
思路：分別計算左子樹的深度和右字?jǐn)?shù)的深度铛楣，然后選出兩個值中的較大值。
/**
* 獲取二叉樹深度
*/
function getTreeDepth(tree) {
const depthCount = (node) => {
let leftDepth = 0;
let rightDepth = 0;
if (node.left) {
leftDepth = depthCount(node.left);
}
if (node.right) {
rightDepth = depthCount(node.right);
}
return Math.max(leftDepth, rightDepth) + 1;
};
return depthCount(tree);
}
console.log('二叉樹深度: ', getTreeDepth(tree));
// 二叉樹深度: 4
求二叉樹的寬度
二叉樹寬度定義：二叉樹各層結(jié)點(diǎn)個數(shù)的最大值
思路：在每個節(jié)點(diǎn)中添加個屬性floor艺普，用來記錄這個節(jié)點(diǎn)是在第幾層，然后計算floor相同情況最多的個數(shù)就行了鉴竭。
/**
* 獲取二叉樹寬度
*/
function getTreeWidth(tree) {
const widthArr = []; // 每層的節(jié)點(diǎn)個數(shù)數(shù)組
const queue = []; // 遍歷樹用到的隊列結(jié)構(gòu)
tree.floor = 0;
queue.push(tree);
while (queue.length > 0) {
const pop = queue.shift();
// widthArr中的index對應(yīng)層數(shù)floor
// 每訪問一個節(jié)點(diǎn)歧譬，在對應(yīng)層數(shù)的widthArr索引里+1
widthArr[pop.floor] = (widthArr[pop.floor] || 0) + 1;
const nextFloor = pop.floor + 1;
if (pop.left) {
pop.left.floor = nextFloor;
queue.push(pop.left);
}
if (pop.right) {
pop.right.floor = nextFloor;
queue.push(pop.right);
}
delete pop.floor;
}
return Math.max(...widthArr);
}
console.log('二叉樹寬度: ', getTreeWidth(tree));
// 二叉樹寬度: 5
