利⽤JS实现⼆叉树遍历算法实例代码
⽬录
前⾔
⼀、⼆叉树
1.1、遍历⼆叉树
1.2、⽤js表⽰⼆叉树
1.3、前序遍历算法
1.4、中序遍历算法
1.5、后序遍历算法
1.6、按层遍历算法
⼆、算法题
1.1、⼆叉树的最⼤深度
1.2、⼆叉树的所有路径
总结
前⾔
在计算机科学中, 树(tree) 是⼀种⼴泛使⽤的抽象数据类型(ADT)，是⼀类⾮线性数据结构。树在计算机领域得到⼴泛应⽤，尤其⼆叉树最为常⽤。
树的相关概念：
结点：每个元素称为结点
树根：根节点
度：⼀个结点含有的⼦结点的个数称为该结点的度
叶⼦节点：度为0的节点
⼀、⼆叉树
概念：每个节点最多含有两个⼦树的树称为⼆叉树。
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: '+',
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); // 打印出来代表访问这个节点
preOrder(treeNode.left);
preOrder(treeNode.right);
}
}
算法思路很简单，先遍历根节点，然后递归遍历左⼦树，左⼦树遍历结束后，递归右⼦树。
第⼆种⾮递归遍历
function preOrder(treeNode) {
if(treeNode) {
var stack = [treeNode]; //将⼆叉树压⼊栈
while (stack.length !== 0) {
treeNode = stack.pop(); // 取栈顶
if(treeNode.right) stack.push(treeNode.right); // 把右⼦树⼊栈
if(treeNode.left) stack.push(treeNode.left); // 把左⼦树⼊栈
}
}
}
第⼆种是使⽤栈的思想，我们都知道，栈是先进后出的⼀种数据结构，我们先把根节点⼊栈，然后取栈顶，访问根节点，分别把右左⼦树⼊栈，这边必须右边先⼊栈，因为我们是要先从左边开始访问的，所以右⼦树先⼊栈，然后就循环取出栈，直到栈空。
1.4、中序遍历算法
中序递归算法：
function InOrder(treeNode) {
if(treeNode) {
InOrder(treeNode.left);
InOrder(treeNode.right);
}
}
和前序递归算法同样的思路，只是访问节点位置不同
function InOrder(node) {
if(node) {
var stack = []; // 建空栈
//如果栈不为空或结点不为空，则循环遍历
while (stack.length !== 0 || node) {
if (node) { //如果结点不为空
stack.push(node); //将结点压⼊栈
node = node.left; //将左⼦树作为当前结点
} else { //左⼦树为空，即没有左⼦树的情况
node = stack.pop(); //将结点取出来
node = node.right; //将右结点作为当前结点
}
}
}
}
⾮递归中序算法的思想就是，把当前节点⼊栈，然后遍历左⼦树，如果左⼦树存在就⼀直⼊栈，直到左⼦树为空，访问但前节点，然后让右⼦树⼊栈。
1.5、后序遍历算法
第⼀种：递归遍历算法
function postOrder(node) {
if (node) { //判断⼆叉树是否为空
postOrder(node.left); //递归遍历左⼦树
postOrder(node.right); //递归遍历右⼦树
}
}
第⼆种：⾮递归遍历算法
function postOrder(node) {
if (node) { //判断⼆叉树是否为空
var stack = [node]; //将⼆叉树压⼊栈
var tmp = null; //定义缓存变量
while (stack.length !== 0) { //如果栈不为空，则循环遍历
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 {
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(); //从队列中取出⼀个结点
if (node.left) que.push(node.left); //如果存在左⼦树，将左⼦树放⼊队列
if (node.right) que.push(node.right); //如果存在右⼦树，将右⼦树放⼊队列
}
}
}
使⽤数组模拟队列，⾸先将根结点归⼊队列。当队列不为空时，执⾏循环：取出队列的⼀个结点，如果该节点有左⼦树，则将该节点的左⼦树存⼊队列；如果该节点有右⼦树，则将该节点的右⼦树存⼊队列。
⼆、算法题
1.1、⼆叉树的最⼤深度
给定⼀个⼆叉树，出其最⼤深度。
⼆叉树的深度为根节点到最远叶⼦节点的最长路径上的节点数。
⽐如下⾯这个⼆叉树，返回深度3。
3
/ \
9 20
/ \
15 7
const 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、⼆叉树的所有路径
给定⼀个⼆叉树，返回所有从根节点到叶⼦节点的路径。
⽐如：
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实现⼆叉树遍历算法的⽂章就介绍到这了，更多相关JS⼆叉树遍历算法内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论