数据结构与算法中,树一般会应用在哪些方面?为什么

发布网友发布时间：2022-04-28 18:29

共2个回答

热心网友时间：2022-04-27 11:24

数据结构就不多说了，树以递归性质这一对计算机而言最普遍的描述结构简直贯穿始终。查找树字典树四叉树哪个都是树的实际应用。除了低维结构不用树描述（其实一维结构也可以看成是退化后的树）。

算法层面，树基本上到处都是（当然有些时候是隐性的）。计算机执行指令是线性的，程序代码也是顺序的，是个一维结构，一旦需要解决高维问题，利用栈、队列等一维基础结构所能做到的只有树，而树则可以用来描述高维逻辑，起到了个桥梁作用。

算法举例如下。
状态空间遍历类：DFS、BFS

决策类：各种自动机（特例还有退化为一位情况的KMP）、贪心、分治、动态规划（同属状态空间遍历）、匹配
图与流：寻路（最短路）、生成树

应用举例就更多了，例如XML、DOM树、编译器中的模式识别和语法树、JSON数据传递、磁盘路径结构……

树的普遍取决于它的结构与通常解决问题的算法的一致性和结构简单严谨：递归定义、拓扑有序（无环）、实现简单。当面临高维状态时，其它结构的处理方式几乎一定不如转化为树来的简单，所以就成为了组织一维实现与高维逻辑中的桥梁。

热心网友时间：2022-04-27 12:42

首先，有一些实际场景中的数据，天然地就是树结构。凡是符合每个对象有一个上级，多个下级的性质，就可以用树建模。比如管理树（老板和员工），家族树（父亲和孩子），文件系统树（文件夹和文件）。另外，二叉搜索树（BST）可以比较高效地对数据进行排序。如果需要维护动态增减且要保持顺序的一组数据，就可以用BST。