1、二叉树的层级遍历

• 创建一个二叉树

class Binary{  constructor(data,left,right){  this.data = data  this.left = left  this.right = right }}

• 输出函数

function Output(){  const left = new Binary(1, new Binary(2),new Binary(3))  const right = new Binary(4,new Binary(5),new Binary(6))  const root = new Binary(0,left,right)//console.log(root) /*       0     /  \    1    4   / \  / \  2  3  5  6 */ inOrder(root) // 2 1 3 0 5 4 6 preOrder(root) //0 1 2 3 4 5 6 postOrder(root) //2,3,1,5,6,4,0 levelOrder(root) // 0,1,4,2,3,5,6}()

• 先访问左子树，再访问自身，再访问右子树

function inOrder(root){ if(root){   inOrder(root.left)   console.log(root.data)   inOrder(root.right) }}

• 先访问自身，再访问左子树，再访问右子树

function preOrder(root){ if(root){  console.log(root.data)  preOrder(root.left)  preOrder(root.right) }}

• 先访问左子树，再访问右子树再访问自身

function postOrder(root){ if(root){   postOrder(root.left)   postOrder(root.right)   console.log(root.data) }}

• 层级遍历

function levelOrder(root){   var queue = []   queue.unshift(root)   while(queue.length){     var current = queue.pop()     console.log(current.data)     if(current.left){       queue.unshift(current.left)     }     if(current.right){       queue.unshift(current.right)     }   }}

2、多叉树的层级遍历

• 创建一个多叉树

class TreeNode {  constructor(data){    this.data = data    this.children = []  }}

• 输出函数

function main(){ const root = new TreeNode(0) const node2 = new TreeNode(2) cosnt node2.children.push(new TreeNode(7)) const node2.chilfren.push(new TreeNode(8)) const node2.children.push(new TreeNode(9)) const node4 = new TreeNode(4) const node3 = new TreeNode(3) const node3.children.push(new TreeNode(6)) const node3.children.push(new TreeNode(5)) root.children.push(node2) root.children.push(node4) root.children.push(node3)//console.log(root)/*                        0                   /    |    \                  2     4     3               /  |  \       /  \              7   8   9     6    5  */traverse1(root)traverse2(traverse2[root])var result = []traverse3([root],result)console.log(result)levelOrder(root)}()

递归遍历每个节点

• 方法1

function traverse1(node){ if(!node){  return [] }var result = []result.push(node.data)if(node.children){for(var i = 0;i<=node.children.length-1;i++){  result = result.concat(traverse1(node.children[i]))} return result}}

• 方法2

function tranverse2(nodeList){if(!nodeList){return []}var result = []for(var i=0;i<=nodeList.length-1;i++){ result.push(nodeList[i].data)  if(nodeList[i].children){    result = result.concat(traverse2(nodeList[i].children))  } }return result}

• 方法3

function traverse3(nodeList,result){  if(!nodeList){    return false  } for(var i=0;i<=nodeList.length-1;i++){  resule.push(nodeList[i].data)  if(nodeList[i].childern){    traverse3(nodeList[i].children,result)  } }}

层级遍历每个节点

funciton levelOrder(root){ var queue = [] queue.unshift(root)var result = []while(quue.length){ var current  = queue.pop() result.push(current.data) for(var i =0;i<=current.children.length-1;i++){   if(current.children[i]){    queue.unshift(current.children[i])    }  } }console.log(result)}