算法系列-二叉树构建

简介: 在内卷潮流的席卷下,身为算法小白的我不得不问自己,是否得踏上征程,征服这座巍巍高山。从零开始,终点不知何方,取决于自己可以坚持多久。希望你可以和我一样,克服恐惧,哪怕毫无基础,哪怕天生愚钝,依然选择直面困难。

在内卷潮流的席卷下,身为算法小白的我不得不问自己,是否得踏上征程,征服这座巍巍高山。

从零开始,终点不知何方,取决于自己可以坚持多久。

希望你可以和我一样,克服恐惧,哪怕毫无基础,哪怕天生愚钝,依然选择直面困难。

分类

  • 递归
  • 二叉树

前言

前两篇文章我们学习了在已有二叉树的情况下,遍历二叉树节点。

二叉树的遍历是二叉树里面最简单的算法了吧,特别是递归遍历。

今天我们来学习,如何通过遍历出的二叉树节点,反向生成二叉树。

二叉树的生成

我们在前面的文章分析了二叉树的遍历,分别有

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历

我们现在通过我们遍历的结果来生成二叉树。

首先要知道的是,通过单一的遍历结果是无法生成二叉树的,必须通过两个以上的遍历顺序。

以前序遍历举例子,我们可以知道第一个是根节点,但是后面的部分到底属于左子树还是右子树就无法得知了。

我们下面的示例还是使用我们之前文章的例子


90.png


前序遍历+中序遍历=二叉树

  • 前序遍历:A -> B -> D -> E -> C -> F -> G
  • 中序遍历:D -> B -> E -> A -> F -> C -> G
const preorderList = ['A', 'B', 'D', 'E', 'C', 'F', 'G']
const inOrderList = ['D', 'B', 'E', 'A', 'F', 'C', 'G']
class Node {
  constructor(data) {
    this.data = data;
  }
}
const buildTree = (preOrder, inOrder) => {
  // 前序的第一个节点即根节点
  const data = preOrder[0]
  const node = new Node(data)
  // 根据中序可以很方便得到左右子树及各自中序
  const rootInOrder = inOrder.indexOf(data)
  const leftInOrder = inOrder.slice(0, rootInOrder)
  const rightInOrder = inOrder.slice(rootInOrder + 1, inOrder.length)
  // 观察前序和中序的特点
  // 可以发现左子树的前序和右子树前序的分界点在中序根节点的上一个节点
  let lastLeftInOrder = rootInOrder - 1;
  let leftPreOrder = []
  let rightPreOrder = []
  // 通过分界点可以很快得到左右子树前序
  if (lastLeftInOrder >= 0) {
    const lastLeftPreOrder = preOrder.indexOf(inOrder[lastLeftInOrder])
    leftPreOrder = preOrder.slice(1, lastLeftPreOrder + 1)
    rightPreOrder = preOrder.slice(lastLeftPreOrder + 1, preOrder.length)
  }
  // 通过左右子树的序列递归构建左右子节点
  node.left = leftPreOrder.length ? buildTree(leftPreOrder, leftInOrder) : null
  node.right = rightPreOrder.length ? buildTree(rightPreOrder, rightInOrder) : null
  return node
}
复制代码

算法解析的过程在代码中应该注释的算比较清楚的了,主要原理就是通过递归分别构建根节点及左右子节点。中序是个很关键的序列,我们可以通过其分析出左右子树。

中序遍历+后序遍历=二叉树

  • 中序遍历:D -> B -> E -> A -> F -> C -> G
  • 后序遍历:D -> E -> B -> F -> G -> C -> A
const inOrderList = ['D', 'B', 'E', 'A', 'F', 'C', 'G']
const postorderList = ['D', 'E', 'B', 'F', 'G', 'C', 'A']
class Node {
  constructor(data) {
    this.data = data;
  }
}
const buildTree = (inOrder, postOrder) => {
  // 根据后序得到根节点
  const data = postOrder[postOrder.length - 1]
  const node = new Node(data)
  // 观察前序和中序的特点
  // 可以发现左子树的前序和右子树前序的分界点在中序根节点的下一个节点
  const rootInOrder = inOrder.indexOf(data)
  const leftInOrder = inOrder.slice(0, rootInOrder)
  const rightInOrder = inOrder.slice(rootInOrder + 1, inOrder.length)
  // 通过分界点可以很快得到左右子树后序
  let firstRighttInOrder = rootInOrder + 1;
  let leftPostOrder = []
  let rightPostOrder = []
  // 通过左右子树的序列递归构建左右子节点
  if (firstRighttInOrder < inOrder.length) {
    const firstRighttPostOrder = postOrder.indexOf(inOrder[firstRighttInOrder])
    leftPostOrder = postOrder.slice(0, firstRighttPostOrder)
    rightPostOrder = postOrder.slice(firstRighttPostOrder, postOrder.length - 1)
  }
  node.left = leftPostOrder.length ? buildTree2(leftInOrder, leftPostOrder) : null
  node.right = rightPostOrder.length ? buildTree2(rightInOrder, rightPostOrder) : null
  return node
}
复制代码

原理和前一个算法差不多,都是通过前序或者后序来确定根节点,再分别确定左右子树序列,通过递归生成左右子节点。

前序遍历+后序遍历=?

通过前序和后序是无法生成唯一二叉树的,我们在前面通过两种序列组合生成二叉树的关键都在于通过前后序来确定根节点,再通过中序序列来确定左右子树。

如果仅提供前后序列的话,我们只能确定根节点,而无法区分左右子树。

举个例子,下面的两个树的前后遍历序列是完全相同的

91.png

92.png


中序遍历+层次遍历=?


层次遍历可以确定根节点,中序遍历可以确定左右子树,所以中序遍历和层次遍历组合应该是可以构建唯一树的。


但是层次遍历有个特点,其左右子树并不是连续的,所以无法找到其临界点来分离左右子树,只能通过中序遍历得到的左右子树来筛选了。

因为没有看到相关的题,今天就先不实现了


总结


通过递归实现了二叉树的构建,其关键点在于通过当前序列分析出左节点和右节点的序列,以此实现递归构建节点。





相关文章
|
3月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
73 0
|
4月前
|
存储 机器学习/深度学习 监控
公司电脑上网监控中滑动窗口算法的理论构建与工程实现
本文提出一种基于滑动窗口算法的实时网络流量监控框架,旨在强化企业信息安全防护体系。系统采用分层架构设计,包含数据采集、处理与分析决策三大模块,通过 Java 实现核心功能。利用滑动窗口技术动态分析流量模式,结合阈值检测与机器学习模型识别异常行为。实验表明,该方案在保证高检测准确率的同时支持大规模并发处理,为企业数字化转型提供可靠保障。
92 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
189 10
 算法系列之数据结构-二叉树
|
7月前
|
JavaScript 算法 前端开发
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
11月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
266 64
|
9月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
261 3
|
10月前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
151 5
|
11月前
|
机器学习/深度学习 算法 Python
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。本文详细介绍了随机森林的工作原理、性能优势、影响因素及调优方法,并提供了Python实现示例。适用于分类、回归及特征选择等多种应用场景。
580 7
|
11月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
269 5
|
11月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
487 0

热门文章

最新文章