起因
二叉树简直是面试过程中必问的知识点，大多数形容过程都是通过C、C++、JAVA、python等语言实现，这里用js语言实现下一下相似的性能，前端、nodejs方向和全栈方向的同学能够作为参考。
示例
以下所有实现都是基于以下二叉树示例：
如图所示，建设过程应用binarytree这个库，代码如下：
const BinaryTree = require('binarytree');let binaryTree = new BinaryTree('F');let bNode = binaryTree.insert('B', 'left', binaryTree.root);let aNode = binaryTree.insert('A', 'left', bNode);let dNode = binaryTree.insert('D', 'right', bNode);let cNode = binaryTree.insert('C', 'left', dNode);let eNode = binaryTree.insert('E', 'right', dNode);let gNode = binaryTree.insert('G', 'right', binaryTree.root);let iNode = binaryTree.insert('I', 'right', gNode);let hNode = binaryTree.insert('H', 'left', iNode);DFS
深度遍历有前序、中序以及后序三种遍历办法，递归办法十分易懂，代码如下：
前序遍历：根结点 ---> 左子树 ---> 右子树
function preorderDFS(root) { const nodeList = []; preorder(root, nodeList) return nodeList; function preorder(root, nodeList) { if (root !== null) { nodeList.push(root.data) preorder(root.left, nodeList); preorder(root.right, nodeList); } }}中序遍历：左子树 ---> 根结点 ---> 右子树
function inorderDFS(root) { const nodeList = []; inorder(root, nodeList); return nodeList; function inorder(root, nodeList) { if (root !== null) { inorder(root.left, nodeList); nodeList.push(root.data); inorder(root.right, nodeList); } }}后序遍历：左子树 ---> 右子树 ---> 根结点
function postorderDFS(root) { const nodeList = []; postorder(root, nodeList); return nodeList; function postorder(root, nodeList) { if (root !== null) { postorder(root.left, nodeList); postorder(root.right, nodeList); nodeList.push(root.data) } }}BFS
按档次遍历就能够，须要一个队列，根节点先退出队列。队列执行出队操作，出队元素有左孩子入队，没有则不论，有右孩子入队，没有则不论。而后持续以上操作，直到队列为空。
function BFS(root) { const q = [root]; const nodeList = []; while (q.length > 0) { const node = q.pop(); nodeList.push(node.data); if (node.left !== null) q.unshift(node.left); if (node.right !== null) q.unshift(node.right); } return nodeList;}蛇形打印
打印程序如图所示：
相似BFS，然而又不同，能够用BFS的思维去思考。
前一层先打印的节点其孩子在下一层后打印，依照这个思路那么其孩子节点须要用栈进行存储。
前后两层，左右孩子的打印程序是相同的，因而咱们须要两个盏实现，一个盏存储奇数层节点入栈程序为先左孩子后右孩子，另一个盏存储偶数层节点入盏程序为先右孩子后左孩子。
假如lrStack存储奇数层节点，rlStack存储偶数层节点：
- 根节点F为第一层，奇数层，因而，lrStack盏入盏F
- lrStack出盏所有元素，即F出盏，同时因为下一层为偶数层，因而依照右孩子、左孩子的程序入盏rlStack
- rlStack出盏所有元素 B ---> G ，因为下一层为奇数层，因而依照左孩子、右孩子的程序入盏lrStack
- lrStack出盏所有元素I ---> D ---> A，因为下一层为偶数层，因而依照右孩子、左孩子的程序入盏rlStack
- rlStack出盏所有元素 C ---> E ---> H ，因为下一层曾经没有数据，完结
依照思路，代码如下：
function printBintryTree(root) { const lrStack = []; const rlStack = []; lrStack.push(root); while(lrStack.length > 0 || rlStack.length > 0) { if (lrStack.length > 0 && rlStack.length === 0) { while (lrStack.length > 0) { const tNode = lrStack.pop(); console.log(tNode.data); if (tNode.right !== null) { rlStack.push(tNode.right); } if (tNode.left !== null) { rlStack.push(tNode.left); } } } if (rlStack.length > 0 && lrStack.length === 0) { while (rlStack.length > 0) { const tNode = rlStack.pop(); console.log(tNode.data); if (tNode.left !== null) { lrStack.push(tNode.left); } if (tNode.right !== null) { lrStack.push(tNode.right); } } } }}示例调用
// 蛇形打印printBintryTree(binaryTree.root); // F B G I D A C E H// 广度遍历console.log(BFS(binaryTree.root)); // ['F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'H']// 深度遍历console.log(preorderDFS(binaryTree.root)); // ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']console.log(inorderDFS(binaryTree.root)); // ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']console.log(postorderDFS(binaryTree.root)); // ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'];