Java教程

【金秋打卡】第14天 JavaScript版数据结构与算法-树形结构概念(二叉树的遍历)

本文主要是介绍【金秋打卡】第14天 JavaScript版数据结构与算法-树形结构概念(二叉树的遍历),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

课程名称: JavaScript版数据结构与算法
课程章节:第8章 数据结构之“树”
课程讲师: lewis
课程内容:前端JS的算法基础
课程介绍:
8-1 树简介
8-2 深度与广度优先遍历
8-3 二叉树的先中后序遍历
8-4 二叉树的先中后序遍历(非递归版)
8-5 LeetCode:104. 二叉树的最大深度
8-6 LeetCode:111. 二叉树的最小深度
8-7 LeetCode:102. 二叉树的层序遍历
8-8 LeetCode:94. 二叉树的中序遍历
8-9 LeetCode:112. 路径总和
8-10 前端与树:遍历 JSON 的所有节点值


二叉树的遍历

不管是深度优先遍历还是广度优先遍历,都可以用递归算法或者非递归算法来实现,一般情况下递归算法比较容易实现,并且看起来直观,但是由于涉及到层层的函数栈调用,性能不高,而非递归算法有着比较好的性能。文章下面对深度优先遍历和广度优先遍历都做了算法描述和递归/非递归实现

首先我们定义这样的一个二叉树结构:

var nodes = {
  node: 6,
  left: {
    node: 5, 
    left: { 
      node: 4 
    }, 
    right: { 
      node: 3 
    }
  },
  right: { 
    node: 2, 
    right: { 
      node: 1 
    } 
  }
}

下面所有的代码都将对上述数据结构进行遍历。

1.1 深度优先遍历二叉树。

图片描述

1.1.1 先序遍历(DLR)的算法:

递归算法
若二叉树为空,则算法结束,否则:
访问根结点;
前序遍历根结点的左子树;
前序遍历根结点的右子树。

var result = []
var dfs = function(nodes) {
  if(nodes.node) {
    result.push(nodes.node)
    nodes.left && dfs(nodes.left)
    nodes.right && dfs(nodes.right)
  }
}
dfs(nodes)
console.log(result)
// [6, 5, 4, 3, 2, 1]

非递归算法
初始化一个栈,将根节点压入栈中;
当栈为非空时,循环执行步骤3到4,否则执行结束;
出队列取得一个结点,访问该结点;
若该结点的右子树为非空,则将该结点的右子树入栈,若该结点的左子树为非空,则将该结点的左子树入栈;

var dfs = function(nodes) {
  var result = []
  var stack = []
  stack.push(nodes)
  while (stack.length) {
    var item = stack.pop()
    result.push(item.node)
    item.right && stack.push(item.right)
    item.left && stack.push(item.left)
  }
  return result
}
console.log(dfs(nodes))
// [6, 5, 4, 3, 2, 1]

1.1.2 中序遍历(LDR)的算法:

递归算法
若二叉树为空,则算法结束;否则:
中序遍历根结点的左子树;
访问根结点;
中序遍历根结点的右子树;

var result = []
var dfs = function(nodes) {
  if(nodes.node) {
    nodes.left && dfs(nodes.left)
    result.push(nodes.node)
    nodes.right && dfs(nodes.right)
  }
}
dfs(nodes)
console.log(result)
// [4, 5, 3, 6, 2, 1]

非递归算法
初始化一个栈,将根节点压入栈中,并标记为当前节点(item);
当栈为非空时,执行步骤3,否则执行结束;
如果当前节点(item)有左子树且没有被 touched,则执行4,否则执行5;
对当前节点(item)标记 touched,将当前节点的左子树赋值给当前节点(item=item.left) 并将当前节点(item)压入栈中,回到3;
清理当前节点(item)的 touched 标记,取出栈中的一个节点标记为当前节点(item),并访问,若当前节点(item)的右子树为非空,则将该结点的右子树入栈,回到3;

var dfs = function(nodes) {
  var result = []
  var stack = []
  var item = nodes
  stack.push(nodes)
  while (stack.length) {
    if(item.left && !item.touched) {
      item.touched = true
      item = item.left
      stack.push(item)
      continue
    }
    item.touched && delete item.touched // 清理标记
    item = stack.pop()
    result.push(item.node)
    item.right && stack.push(item.right)
  }
  return result
}
console.log(dfs(nodes))
// [4, 5, 3, 6, 2, 1]

1.1.3 后序遍历(LRD)的算法:

递归算法:
若二叉树为空,则算法结束,否则:
后序遍历根结点的左子树;
后序遍历根结点的右子树;
访问根结点。

var result = []
var dfs = function(nodes) {
  if(nodes.node) {
    nodes.left && dfs(nodes.left)
    nodes.right && dfs(nodes.right)
    result.push(nodes.node)
  }
}
dfs(nodes)
console.log(result)
// [4, 3, 5, 1, 2, 6]

非递归算法:
初始化一个栈,将根节点压入栈中,并标记为当前节点(item);
当栈为非空时,执行步骤3,否则执行结束;
如果当前节点(item)有左子树且没有被 touched,则执行4,如果被 touched left 但没有被 touched right 则执行5 否则执行6;
对当前节点(item)标记 touched left,将当前节点的左子树赋值给当前节点(item=item.left) 并将当前节点(item)压入栈中,回到3;
对当前节点(item)标记 touched right,将当前节点的右子树赋值给当前节点(item=item.right) 并将当前节点(item)压入栈中,回到3;
清理当前节点(item)的 touched 标记,弹出栈中的一个节点并访问,然后再将栈顶节点标记为当前节点(item),回到3;

var dfs = function(nodes) {
  var result = []
  var stack = []
  var item = nodes
  stack.push(nodes)
  while (stack.length) {
    if(item.left && !item.touched) {
      item.touched = 'left'
      item = item.left
      stack.push(item)
      continue
    }
    if(item.right && item.touched !== 'right') {
      item.touched = 'right'
      item = item.right
      stack.push(item)
      continue
    }
    var out = stack.pop()
    out.touched && delete out.touched // 清理标记
    result.push(out.node)
    item = stack.length ? stack[stack.length - 1] : null
  }
  return result
}
console.log(dfs(nodes))
// [4, 3, 5, 1, 2, 6]

1.2 广度优先遍历二叉树:

广度优先遍历二叉树(层序遍历)是用队列来实现的,从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。
图片描述

按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。步骤:

初始化一个队列,并把根结点入列队;
当队列为非空时,循环执行步骤3到4,否则执行结束;
出队列取得一个结点,访问该结点;
若该结点的左子树为非空,则将该结点的左子树入队列,若该结点的右子树为非空,则将该结点的右子树入队列;
递归算法:

var result = []
var queue = [nodes]
var bfs = function(count) {
  count = count || 0
  if(queue[count]) {
    result.push(queue[count].node)
    var left = queue[count].left
    var right = queue[count].right
    if(left) {
      queue.push(left)
    }
    if(right) {
      queue.push(right)
    }
    bfs(++count)
  }
}
bfs()
console.log(result)
// [6, 5, 2, 4, 3, 1]

非递归算法

var bfs = function(nodes) {
  var result = []
  var queue = []
  var pointer = 0
  queue.push(nodes)
  while(pointer < queue.length) {
    var item = queue[pointer++] // 这里不使用 shift 方法(复杂度高),用一个指针代替
    result.push(item.node)
    console.log(item.node)
    item.left && queue.push(item.left)
    item.right && queue.push(item.right)
  }
  return result
}
console.log(bfs(nodes))
// [6, 5, 2, 4, 3, 1]

二、总结

在实际生产过程中尽量避免递归的调用,应为其时间复杂度,树和图是数据结构中最基础和最重要的组成部分,其经典应用还有红黑树,平衡二叉树等经典问题。
图片描述

这篇关于【金秋打卡】第14天 JavaScript版数据结构与算法-树形结构概念(二叉树的遍历)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!