数据结构和算法(树Tree)

简介: 树概述:树:是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。二叉树:是一种更为典型的树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。树的遍历 前序遍历前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。中序遍历中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。我们可以通过中序遍历得到一个递增的有序序列后序遍历后序遍历是先遍历左子树,然后遍历右子树,最后访

概述:

树:

是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。

二叉树:

是一种更为典型的树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。

树的遍历

前序遍历

前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。

中序遍历

中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。

我们可以通过中序遍历得到一个递增的有序序列

后序遍历

后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。

值得注意的是,当你删除树中的节点时,删除过程将按照后序遍历的顺序进行。 也就是说,当你删除一个节点时,你将首先删除它的左节点和它的右边的节点,然后再删除节点本身。另外,后序在数学表达中被广泛使用。 编写程序来解析后缀表示法更为容易.


层序遍历

层序遍历就是逐层遍历树结构。

广度优先搜索

是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。 该算法从一个根节点开始,首先访问节点本身。 然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推。

当我们在树中进行广度优先搜索时,我们访问的节点的顺序是按照层序遍历顺序的。



运用递归解决树的问题

树可以以递归的方式定义为一个节点(根节点),它包括一个值和一个指向其他节点指针的列表。 递归是树的特性之一。 因此,许多树问题可以通过递归的方式来解决。 对于每个递归层级,我们只能关注单个节点内的问题,并通过递归调用函数来解决其子节点问题。

“自顶向下” 的解决方案

可以被认为是一种前序遍历“自顶向下” 意味着在每个递归层级,我们将首先访问节点来计算一些值,并在递归调用函数时将这些值传递到子节点。

“自底向上” 的解决方案

“自底向上” 是另一种递归方法。 在每个递归层次上,我们首先对所有子节点递归地调用函数,然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历


总结

总结

了解递归并利用递归解决问题并不容易。

当遇到树问题时,请先思考一下两个问题:

你能确定一些参数,从该节点自身解决出发寻找答案吗?

你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗?

如果答案都是肯定的,那么请尝试使用 “自顶向下” 的递归来解决此问题。

或者你可以这样思考:对于树中的任意一个节点,如果你知道它子节点的答案,你能计算出该节点的答案吗? 如果答案是肯定的,那么 “自底向上” 的递归可能是一个不错的解决方法。


相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
70 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
17天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
60 16
|
13天前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
22 2
|
1月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
33 4
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
22 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
1月前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
29 0
|
1月前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
28天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
5天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。

热门文章

最新文章

下一篇
无影云桌面