2rever的前端小站

js二叉树遍历方法

Word count: 442 / Reading time: 2 min
2018/10/23 Share

深度优先遍历

  • 二叉树前序遍历
1
2
3
4
5
6
7
8
//二叉树前序遍历
function preOrderTraverse(root,action = console.log){
  if (root) {
    action(root.val)
    preOrderTraverse(root.left,action)
    preOrderTraverse(root.right,action)
  }
}
  • 二叉树后序遍历
1
2
3
4
5
6
7
8
//二叉树后序遍历
function postOrderTraverse(root,action = console.log){
  if (root) {
    postOrderTraverse(root.left,action)
    postOrderTraverse(root.right,action)
    action(root.val)
  }
}
  • 二叉树中序遍历
1
2
3
4
5
6
7
8
//二叉树中序遍历
function midOrderTraverse(root,action = console.log){
  if (root) {
    midOrderTraverse(root.left,action)
    action(root.val)
    midOrderTraverse(root.right,action)
  }
}

广度优先遍历

  • 广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。
    实现： 使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。
    （描述有点不清楚，直接看代码吧。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//按层遍历1 两个数组
function levelOrderTraverse(root) {
    if (!root) {
      return
    }

    var currRow = [root]
    var nextRow = []

    while(currRow.length) {
      for(var i = 0; i<currRow.length; i++) {
        console.log(currRow[i].obj)
        currRow[i].left && nextRow.push(currRow[i].left)
        currRow[i].right && nextRow.push(currRow[i].right)
      }
      console.log('--------')
      currRow = nextRow
      nextRow = []
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//按层遍历2 一个数组
function levelOrderTraverse2(root) {
  if (!root) {
    return
  }

  var row = [root]

  while(row.length) {
    var l = row.length
    for(var i = 0; i < l; i++) {
      console.log(row[i].obj)
      row[i].left && row.push(row[i].left)
      row[i].right && row.push(row[i].right)
    }
    row.splice(0, l)
    console.log('--------')
  }
}

原文作者: 2rever

原文链接: https://2rever.cn/2018/10/23/js二叉树遍历方法/

发表日期: October 23rd 2018, 10:32:55 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 深度优先遍历
  2. 2. 广度优先遍历
Total : 24
2019
2018