<div id="div24"><h3> 24，js实现二叉树遍历（前序，后序，中序，层次）递归与迭代实现 </font><h3></div> [参考blog](https://blog.csdn.net/liusaint1992/article/details/80310918) [参考blog](https://www.jianshu.com/p/3f3fed4b1b69) A：根节点、B：左节点、C：右节点， - 前序顺序是ABC（根节点排最先，然后同级先左后右）； - 中序顺序是BAC(先左后根最后右）； - 后序顺序是BCA（先左后右最后根） ``` function Node(val){ // 数据结构 this.left = this.right = null; this.val = val; } // 先定义一棵树。node1是根节点。 var node4 = {left: null, right: null, val: 4 }; var node5 = {left: null, right: null, val: 5 }; var node6 = {left: null, right: null, val: 6 }; var node7 = {left: null, right: null, val: 7 }; var node3 = {left: node6, right: node7, val: 3 }; var node2 = {left: node4, right: node5, val: 2 }; var node1 = {left: node2, right: node3, val: 1 }; // 1 // /\ // 2 3 // /\ /\ // 4 5 6 7 ``` ## 前序遍历 ``` // 前序遍历: 递归实现 function preorderTraversal(root) { if (!root) { return; } console.log(root.val); root.left && preorderTraversal(root.left); root.right && preorderTraversal(root.right); } preorderTraversal(node1); //1 2 4 5 3 6 7 // 前序遍历: 迭代实现 function preorderTraversal1(root) { if (!root) { return; } var stack = [root]; while (stack.length > 0) { var item = stack.shift(); //取第一个。 // shift() 移除数组的第一项，返回移除项 ; // -- unshift() 在数组添加一个或多个元素，返回长度 console.log(item.val); if (item.right) { stack.unshift(item.right); } if (item.left) { stack.unshift(item.left); } } } preorderTraversal1(node1); //1 2 4 5 3 6 7 ``` ## 中序遍历 ```javascript // 中序遍历: 递归实现 function inorderTraversal(root) { if (!root) { return; } root.left && inorderTraversal(root.left); console.log(root.val); root.right && inorderTraversal(root.right); } console.log(inorderTraversal(node1)); //4 2 5 1 6 3 7 // 中序遍历: 迭代实现 function inorderTraversal1(root) { if (!root) { return; } var stack = [root]; while (stack.length > 0) { var item = stack[stack.length - 1]; if (!item.left || (item.left && item.left.isOk)) { stack.pop(); // push() 尾添加 ----pop()移除数组的最后一项，返回移除的项 item.isOk = true; console.log(item.val); item.right && stack.push(item.right); } else if (item.left && !item.left.isOk) { stack.push(item.left); } } } inorderTraversal1(node1); //4 2 5 1 6 3 7 ``` ## 后序遍历 ``` // 后序遍历: 递归实现 function postorderTraversal(root) { if (!root) { return; } root.left && postorderTraversal(root.left); root.right && postorderTraversal(root.right); console.log(root.val); } postorderTraversal(node1);//4 5 2 6 7 3 1 // 后序遍历: 迭代实现 function postorderTraversal1(root) { if (!root) { return; } var stack = [root]; while (stack.length > 0) { var item = stack[stack.length - 1]; //满足这些就可以直接输出它了。它是叶子节点。或它的子节点都ok了。 if ((item.left == null && item.right == null) || + (item.left && item.left.isOk && item.right && item.right.isOk) || + (item.left && item.left.isOk && item.right == null) || + (item.left == null && item.right && item.right.isOk)) { item.isOk = true; console.log(item.val); stack.pop(); } else if (item.left && !item.left.isOk) { // 如果左边的没ok，就把左边的入栈 stack.push(item.left); } else if (item.right && !item.right.isOk) { //如果右边的没ok就把右边的入栈。 stack.push(item.right); } } } postorderTraversal1(node1);//4 5 2 6 7 3 1 ``` ## 层次遍历 ``` // 层次遍历。 从上往下，从左往右，一层一层的遍历。 var levelOrder = function(root) { if(!root){ return; } var checkArr = [root]; while (checkArr.length > 0) { var newCheckArr = []; for (var i = 0; i < checkArr.length; i++) { var item = checkArr[i]; console.log(item.val); item.left && newCheckArr.push(item.left); item.right && newCheckArr.push(item.right); } checkArr = newCheckArr; } }; levelOrder(node1);//1 2 3 4 5 6 7 ``` **深度优先与广度优先** - 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。 - 深度优先对每一个可能的分支路径深入到不能再深入为止,先序遍历、中序遍历、后序遍历属于深度优先。 - 广度优先又叫层次遍历，从上往下，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。