资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/js遍历二叉树和多叉树结构

js遍历二叉树和多叉树结构

junbaor / 1777人阅读

摘要：二叉树的层级遍历创建一个二叉树输出函数先访问左子树，再访问自身，再访问右子树先访问自身，再访问左子树，再访问右子树先访问左子树，再访问右子树再访问自身层级遍历多叉树的层级遍历创建一个多叉树输出函数递归遍历每个节点方法方法方法层级遍历每

1、二叉树的层级遍历

创建一个二叉树

</>复制代码 
  1. class Binary{
  2.   constructor(data,left,right){
  3.   this.data = data
  4.   this.left = left
  5.   this.right = right
  6.  }
  7. }

输出函数

</>复制代码 
  1. function Output(){
  2.   const left = new Binary(1, new Binary(2),new Binary(3))
  3.   const right = new Binary(4,new Binary(5),new Binary(6))
  4.   const root = new Binary(0,left,right)
  5. //console.log(root) 
  6. /*
  7.        0
  8.      /  
  9.     1    4
  10.    /   / 
  11.   2  3  5  6
  12.  */
  13.  inOrder(root) // 2 1 3 0 5 4 6
  14.  preOrder(root) //0 1 2 3 4 5 6
  15.  postOrder(root) //2,3,1,5,6,4,0
  16.  levelOrder(root) // 0,1,4,2,3,5,6
  17. }()

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

</>复制代码 
  1. function inOrder(root){
  2.  if(root){
  3.    inOrder(root.left)
  4.    console.log(root.data)
  5.    inOrder(root.right)
  6.  }
  7. }

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

</>复制代码 
  1. function preOrder(root){
  2.  if(root){
  3.   console.log(root.data)
  4.   preOrder(root.left)
  5.   preOrder(root.right)
  6.  }
  7. }

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

</>复制代码 
  1. function postOrder(root){
  2.  if(root){
  3.    postOrder(root.left)
  4.    postOrder(root.right)
  5.    console.log(root.data)
  6.  }
  7. }

层级遍历

</>复制代码 
  1. function levelOrder(root){
  2.    var queue = []
  3.    queue.unshift(root)
  4.    while(queue.length){
  5.      var current = queue.pop()
  6.      console.log(current.data)
  7.      if(current.left){
  8.        queue.unshift(current.left)
  9.      }
  10.      if(current.right){
  11.        queue.unshift(current.right)
  12.      }
  13.    }
  14. }
2、多叉树的层级遍历

创建一个多叉树

</>复制代码 
  1. class TreeNode {
  2.   constructor(data){
  3.     this.data = data
  4.     this.children = []
  5.   }
  6. }

输出函数

</>复制代码 
  1. function main(){
  2.  const root = new TreeNode(0)
  3.  const node2 = new TreeNode(2)
  4.  cosnt node2.children.push(new TreeNode(7))
  5.  const node2.chilfren.push(new TreeNode(8))
  6.  const node2.children.push(new TreeNode(9))
  7.  const node4 = new TreeNode(4)
  8.  const node3 = new TreeNode(3)
  9.  const node3.children.push(new TreeNode(6))
  10.  const node3.children.push(new TreeNode(5))
  11.  root.children.push(node2)
  12.  root.children.push(node4)
  13.  root.children.push(node3)
  14. //console.log(root)
  15. /*
  16.                         0
  17.                    /    |    
  18.                   2     4     3
  19.                /  |         /  
  20.               7   8   9     6    5  
  21. */
  22. traverse1(root)
  23. traverse2(traverse2[root])
  24. var result = []
  25. traverse3([root],result)
  26. console.log(result)
  27. levelOrder(root)
  28. }()
递归遍历每个节点

方法1

</>复制代码 
  1. function traverse1(node){
  2.  if(!node){
  3.   return []
  4.  }
  5. var result = []
  6. result.push(node.data)
  7. if(node.children){
  8. for(var i = 0;i<=node.children.length-1;i++){
  9.   result = result.concat(traverse1(node.children[i]))
  10. }
  11.  return result
  12. }
  13. }

方法2

</>复制代码 
  1. function tranverse2(nodeList){
  2. if(!nodeList){
  3. return []
  4. }
  5. var result = []
  6. for(var i=0;i<=nodeList.length-1;i++){
  7.  result.push(nodeList[i].data)
  8.   if(nodeList[i].children){
  9.     result = result.concat(traverse2(nodeList[i].children))
  10.   }
  11.  }
  12. return result
  13. }

方法3

</>复制代码 
  1. function traverse3(nodeList,result){
  2.   if(!nodeList){
  3.     return false
  4.   }
  5.  for(var i=0;i<=nodeList.length-1;i++){
  6.   resule.push(nodeList[i].data)
  7.   if(nodeList[i].childern){
  8.     traverse3(nodeList[i].children,result)
  9.   }
  10.  }
  11. }
层级遍历每个节点 
</>复制代码 
  1. funciton levelOrder(root){
  2.  var queue = []
  3.  queue.unshift(root)
  4. var result = []
  5. while(quue.length){
  6.  var current  = queue.pop()
  7.  result.push(current.data)
  8.  for(var i =0;i<=current.children.length-1;i++){
  9.    if(current.children[i]){
  10.     queue.unshift(current.children[i])
  11.     }
  12.   }
  13.  }
  14. console.log(result)
  15. }
云服务器 GPU云服务器 JS二叉树遍历 二叉树遍历 二叉树的遍历 非递归二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109904.html

相关文章

  • 树及其外部存储

    摘要：切记，红黑树在旋转和颜色变换的过程中，必须遵守红黑树的几条规则。树的外部存储磁盘布局计算机中的机械磁盘是由磁头和圆盘组成，每个圆盘上划分为多个磁道，每个磁道又划分为多个扇区。 术语 showImg(https://segmentfault.com/img/bVbai3r?w=643&h=407); 根     树最顶端的节点称为根，一棵树只有一个根 父节点     每个节...

    _Dreams 评论0 收藏0

  • 一篇文章学会二叉树和二叉查找树

    摘要：二叉树和二叉查找树一个父节点的两个子节点分别称为左节点和右节点。下图展示了一颗二叉树当考虑某种特殊的二叉树，比如二叉查找树时，确定子节点非常重要。实现二叉查找树定义对象。现在可以创建一个类来表示二叉查找树。因此二叉查找树也被叫做二叉排序树。 树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。 树被用来存储具有层级关系的数据，比如文件系统中的文件。 ...

    BaronZhang 评论0 收藏0

  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

    摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

    ghnor 评论0 收藏0

  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

    摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

    FuisonDesign 评论0 收藏0

发表评论

登陆后可评论

0条评论

junbaor

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<