本文转载自微信公众号《JS日报》，作者灰灰。转载本文请联系JS每日一问公众号。1.这是什么？在计算机领域，树数据结构是一类重要的非线性数据结构，它可以表示数据之间的一对多关系。树和二叉树是最常用的。直观上，树是由满足以下两个条件的分支关系定义的层次二叉树：是有序树。树中包含的每个节点的度数不能超过2，即只能为0、1或2如下图，左边的是二叉树，右边的不是属于二叉树，因为头节点的子节点超过2：同时二叉树可以继续分类，分为满二叉树和完全二叉树：满二叉树：如果度二叉树中除叶子节点外每个节点的个数都是2，完成二叉树：如果将二叉树的最后一层节点去掉，则二叉树是满的，最后一层的节点从左开始分布依次向右。2、关于二叉树遍历的操作常见的二叉树遍历有：前序遍历、中序遍历、后序遍历、层序遍历、前序遍历。获取当前节点的右孩子根据遍历特性，递归版本用代码表示如下：constpreOrder=(root)=>{if(!root){return}console.log(root)preOrder(root.left)preOrder(root.right)}如果不使用递归版本，可以使用栈的先进后出特性。先将根节点压入栈中，然后分别将右节点和左节点压入栈中，直到栈中没有元素，如下：constpreOrder=(root)=>{if(!root){return}conststack=[root]while(stack.length){constn=stack.pop()console.log(n.val)if(n.right){stack.push(n.right)}if(n.left){stack.push(n.left)}}}中序遍历前序遍历的实现思路是：访问当前节点的左子树，访问根节点，递归访问当前节点的右孩子版本很容易理解，并且代码表示如下：constinOrder=(root)=>{if(!root){return}inOrder(root.left)console.log(root.val)inOrder(root.right)}非递归版本也是基于栈的先进后出特性。它总是可以先推送节点的左侧元素。当左边的节点没有了，会开始入栈操作，压入右边的节点，然后依次压入左边的节点，如下：constinOrder=(root)=>{if(!root){return}conststack=[root]letp=rootwhile(stack.length||p){while(p){stack.push(p)p=p.left}constn=stack.pop()console.log(n.val)p=n.right}}后序遍历和前序遍历的实现思路是：访问当前节点的左子树，访问当前节点的右子树节点，访问根节点的递归版本，用代码表示如下：constpostOrder=(root)=>{if(!root){return}postOrder(root.left)postOrder(root.right)console.log(n.val)}非递归版本的后序遍历其实是按照全序遍历是一种逆序关系，可以再创建一个栈输出，如下：constpreOrder=(root)=>{if(!root){return}conststack=[root]constoutPut=[]while(stack.length){constn=stack.pop()outPut.push(n.val)if(n.right){stack.push(n.right)}if(n.left){stack.push(n.left)}}while(outPut.length){constn=outPut.pop()console.log(n.val)}}层序遍历遍历每一层的节点从左到钻机ht根据二叉树中的级别。从树的根节点开始，依次将其左孩子和右孩子入队然后每次队列中的一个节点出队时，它的左孩子和右孩子都会入队，直到树中的所有节点都出队。出队节点的顺序是层次遍历的最终结果。代码如下：constlevelOrder=(root)=>{if(!root){return[]}constqueue=[[root,0]]constres=[]while(queue.length){constn=queue.shift()const[node,leval]=nif(!res[leval]){res[leval]=[node.val]}else{res[leval].push(node.val)}if(node.left){queue.push([node.left,leval+1])}if(node.right){queue.push([node.right,leval+1])}}returnres};3.总结树是一种很重要的非线性结构，其中二叉树Binarytrees最为常见，二叉树的遍历方法分为前序遍历、中序遍历和后序遍历顺序遍历。同时二叉树又分为完全二叉树和满二叉树参考https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91http:///data.biancheng.net/view/27.html
