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

junbaor 发布于2019-08-26 13:58 / 1701人阅读

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

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)
}

GPU云服务器云服务器 JS二叉树遍历二叉树遍历二叉树的遍历非递归二叉树遍历

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

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

树及其外部存储

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

_Dreams 2019-08-15 15:58 评论0 收藏0
一篇文章学会二叉树和二叉查找树

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

BaronZhang 2019-08-26 13:46 评论0 收藏0
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

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

ghnor 2019-08-23 16:19 评论0 收藏0
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

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

FuisonDesign 2019-08-16 16:04 评论0 收藏0