JavaScript实现二叉树的遍历
二叉树是数据结构中很重要的一个部分，也是程序猿们必备的知识点。也许我们在平时的业务开发中不会用到这类“泛泛而谈”的算法，而且就算是数据库，文件系统这类对检索排序性能要求很高的系统，也一般使用更复杂的树结构（特别是B树），但作为最基本最典型的排序树，二叉树是我们学习编程思想，深入算法的一条重要途径。
废话不多说，这里将展示JS实现二叉树的深度优先（前序，中序，后序）遍历和广度优先遍历算法，每种遍历法都有递归和非递归两种思路。若对二叉树的概念和特性还不是特别了解，可以参考：
二叉树的几种遍历方式
-
深度优先搜索(Depth First Search)，深度优先遍历又分为以下三种方式：
- 前序遍历(Preorder Traversal 亦称（先序遍历））：访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后。
-
广度优先搜索(Breadth First Search)：按照树的层次，每层从左至右依次遍历
二叉树结构.jpg
如上图所示，根据几种遍历方式，遍历结果如下：
- 前序遍历：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
- 广度优先遍历：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
根据上图所示的二叉树结构，先写出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
}
}
}
接下来解析每种遍历方式的算法，每种遍历方式都给出了递归和非递归两种形式。为了便于解释，先定义一个“节点组合”：一个根节点与其左子节点和右子节点的组合。（以下解析中，“访问”是一次touch，不会读取出节点的值，不同于“搜索”或“读取”）。
前序遍历
一、 递归算法
思路：每开始访问一个节点组合的时候，总是先读取其根节点的值，再访问其左子节点树，最后访问其右子节点树。于是设想：每个节点组合的遍历作为一次递归，不断按照此规律进行遍历，直至所有节点遍历完成。
/**
* 递归法前序遍历
*/
function dfsPreorderByRcs(tree) {
const output = [];
const visitLoop = (node) => {
if (node) {
// 先搜索出根节点的值，push进结果列表
output.push(node.data);
// 访问左子节点树，左子节点开始作为根节点进行下一轮递归
visitLoop(node.left);
// 同上述，递归遍历右子节点
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 ]
二、非递归算法
思路：不用递归，那就肯定要用循环了，但如何保证搜索的顺序呢？可以用数组来记录访问顺序，并且每次从这个顺序数组中依次取出节点对象进行搜索，这样只要保证数组中要搜索的节点顺序是正常的就完成了。那又如何正确的记录顺序呢？每访问一个节点组合，总是搜索其根节点值，然后将其左子节点树push进顺序数组中，再将其右子节点树push进顺序数组中，但是最后push进的节点需要先读取出来，这样就是一个先进后出的栈结构了。
既然是栈结构，为了方便记录，那就用数组构造一个栈吧：
/**
* 简单构造个栈结构
*/
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;
}
}
遍历算法：
/**
* 非递归法前序遍历
* 由于遍历过程是先进后出，所以使用栈结构
*/
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 ]
中序遍历
一、递归算法
思路：和前序递归遍历思路差不多，但是顺序上有点改变，先要搜索的是一个节点组合的左子节点，再搜索其根节点，最后是右子节点。
/**
* 递归法中序遍历
*/
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 ]
二、非递归算法
思路：和前序的非递归算法一样的是，需要一个栈结构记录遍历的顺序，但现在麻烦的一点是不能每次访问一个节点组合的时候立马读取根节点的值，然后按照读取顺序依次将节点push进栈中了。这里有用到一种“回溯思想”。
步骤1：用一个变量存放当前访问的节点，若此节点存在左子节点，则将此节点对象push进栈中，且将左子节点作为当前访问节点进行下一轮循环
步骤2：若当前访问节点不存在左子节点，则从栈中pop出这个节点，读取这个节点的值，并且如果其存在右子节点，则将右子节点作为当前访问节点进行下一轮循环。若左右子节点都不存在，则从栈中pop出其父节点，开始读取父节点的右子节点。
/**
* 非递归法中序遍历
*/
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 ]
后序遍历
一、递归算法
思路：和前序及中序一样，但先要搜索的是一个节点组合的左子节点，再搜索右子节点，最后才是根节点
/**
* 递归法后序遍历
*/
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 ]
二、非递归算法
思路：对当前访问的节点增加一个touched属性，用来标志这个节点是否被访问过其左子节点和右子节点了，判断：
1、当左子节点未被访问过，则将左子节点压入栈中，并且左子节点作为当前访问节点，开始下一轮循环判断；
2、当左子节点已被访问，而右子节点未被访问，则将右子节点压入栈中，并且右子节点作为当前访问节点，开始下一轮循环判断；
3、当左右子节点都被访问过了，则读取其值，然后从栈中取出其父节点，从步骤2开始判断父节点是否可以被读取值了（因为回溯到父节点了，那么父节点的左子节点肯定被搜索过了，只是判断当前节点是否是父节点的右子节点，若是，则可以直接读取父节点的值了）；
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);
// 当前访问节点要改成父节点了，所以从栈中取出父节点
// 但由于还没确定是否可以读取父节点的值，所以不能用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 ]
广度优先遍历
一、递归算法
思路：由于是一层一层从左至右访问并直接读取节点值，同一层中读取了某个节点的值后，其右边的节点并不一定与其有共同的父节点，所以必须用一个顺序结构来记录访问的顺序，可以推出是个先进先出的队列结构。
/**
* 递归法广度优先遍历
*/
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循环去替代递归就行了
/**
* 非递归法广度优先遍历
*/
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 ]
求二叉树的深度
二叉树深度定义：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。（其实就是二叉树的最深层次），上述我们用的例子中的深度为4（一共有4层）。
思路：分别计算左子树的深度和右字数的深度，然后选出两个值中的较大值。
/**
* 获取二叉树深度
*/
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
求二叉树的宽度
二叉树宽度定义：二叉树各层结点个数的最大值
思路：在每个节点中添加个属性floor，用来记录这个节点是在第几层，然后计算floor相同情况最多的个数就行了。
/**
* 获取二叉树宽度
*/
function getTreeWidth(tree) {
const widthArr = []; // 每层的节点个数数组
const queue = []; // 遍历树用到的队列结构
tree.floor = 0;
queue.push(tree);
while (queue.length > 0) {
const pop = queue.shift();
// widthArr中的index对应层数floor
// 每访问一个节点，在对应层数的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
