上查看所有课程
树是一种非线性分层数据结构，由连接边（edges）的节点（nodes）组成。
为什么需要树数据结构？
数组、链表、栈和队列等其他数据结构是线性数据结构，它们按顺序存储数据。为了在线性数据结构中执行任何操作，时间复杂度随着数据量的增加而增加。但在当今的计算世界中，这是不可接受的。
不同的树数据结构允许更快、更方便地访问数据，因为它是一种非线性数据结构。
树术语
节点
节点是一个包含键或值以及指向其子节点的指针的实体。
每条路径的最后一个节点称为叶节点或外部节点，它们不包含指向子节点的链接/指针。
至少有一个子节点的节点称为内部节点。
边
它是任何两个节点之间的链接。
根
它是树的最顶层节点。
节点的度
一个节点的度是该节点分支的总数。
节点的深度
一个节点的深度是从根到该节点的边的数量。
树的高度
树的高度是根节点的高度或最深节点的深度。
节点的度
一个节点的度是该节点分支的总数。
森林
不相交的树的集合称为森林。
通过剪断树的根，您可以创建一个森林。
树的类型
树遍历
为了在树上执行任何操作，您需要找到特定节点。树遍历算法有助于访问树中的所需节点。
要了解更多信息，请访问树遍历。
树的应用
- 二叉搜索树（BST）用于快速检查一个元素是否存在于一个集合中。
- 堆是一种用于堆排序的树。
- 一种称为 Trie 的树的修改版本用于现代路由器存储路由信息。
- 大多数流行的数据库使用 B 树和 T 树（是我们上面学到的树结构的变体）来存储它们的数据
- 编译器使用语法树来验证您编写的每个程序的语法。