树型数据结构的应用

为什么是树？ 与线性数据结构的数组和链表不同，树是分层（或非线性）数据结构。

1. 使用树的一个原因可能是，您希望存储自然形成层次结构的信息。例如，计算机上的文件系统：

   文件系统 ———–

     /   <-- root  /      ...        home      /             ugrad        course    /          /    |      ...        cs101 cs112 cs113

1. 如果我们以树的形式组织键（具有一些顺序，例如BST），我们可以在中等时间内搜索给定的键（比链表快，比数组慢）。 自平衡搜索树 喜欢 AVL 和 红黑树 保证搜索的上限为O（Logn）。
2. 我们可以在中等时间内插入/删除键（比数组快，比无序链表慢）。 自平衡搜索树 喜欢 AVL 和 红黑树 保证插入/删除的上限为O（Logn）。
3. 与链表和数组不同，树的指针实现对节点数没有上限，因为节点是使用指针链接的。

其他应用程序：

1. 存储分层数据，如文件夹结构、组织结构、XML/HTML数据。
2. 二叉搜索树 是一种允许快速搜索、插入、删除已排序数据的树。它还允许查找最近的项目
3. 堆 是一种树状数据结构，使用数组实现，用于实现优先级队列。
4. B-树 和 B+树 ：它们用于在数据库中实现索引。
5. 语法树 ：在编译器设计中扫描、解析、生成代码和计算算术表达式。
6. K-D树： 用于在K维空间中组织点的空间分区树。
7. 崔 ：用于实现带有前缀查找的词典。
8. 后缀树 ：用于在固定文本中快速搜索图案。
9. 生成树 最短路径树分别用于计算机网络中的路由器和网桥
10. 作为合成数字图像以获得视觉效果的工作流。
11. 决策树。
12. 大型组织的组织结构图。

参考资料： http://www.cs.bu.edu/teaching/c/tree/binary/ http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Common_uses

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。