跳到主要内容

树形数据结构

提示
  1. 非线性数据结构：树是一种非线性层次化数据结构，由节点组成，通过边相互连接，与线性数据结构（如数组、链表）相比，树结构提供了更高效的数据存取方式。
  2. 树的基本术语：树包含了多个节点和边，其中每个节点可以有零个或多个子节点。树顶部的节点称为根节点，没有子节点的节点称为叶节点，其他节点称为内部节点。树的高度是从根到最深叶子的距离。
  3. 应用场景：树形数据结构广泛应用于各种场合，如二叉搜索树用于高效数据搜索，堆用于排序，Tries用于路由器中存储路由信息，数据库中使用B树存储数据，编译器使用语法树检查程序语法等。

树是一种非线性层次化的数据结构，由节点通过边连接而成。

数据结构中的树

为什么使用树形数据结构？​

其他如数组、链表、栈和队列等线性数据结构按顺序存储数据。在线性数据结构中执行任何操作时，随着数据大小的增加，时间复杂度也会增加。但在当今的计算世界中，这是不可接受的。

不同的树形数据结构允许更快、更容易地访问数据，因为它是一种非线性数据结构。

树的术语​

节点​

节点是包含键或值以及指向其子节点的指针的实体。

每条路径的最后节点被称为叶节点或外部节点，不包含指向子节点的链接/指针。

至少有一个子节点的节点称为内部节点。

边​

它是任意两个节点之间的链接。

树中的节点和边

根​

它是树的最顶部节点。

节点的高度​

节点的高度是从该节点到最深叶子的边数（即从节点到叶节点的最长路径）。

节点的深度​

节点的深度是从根到该节点的边数。

树的高度​

树的高度是根节点的高度或最深节点的深度。

树中每个节点的高度和深度

节点的度​

节点的度是该节点的分支总数。

森林​

不相交树的集合称为森林。

数据结构中的森林

你可以通过切断树的根来创建一个森林。

树的类型​

  1. 二叉树
  2. 二叉搜索树
  3. AVL 树
  4. B 树

树的遍历​

为了在树上执行任何操作，你需要到达特定的节点。树遍历算法有助于访问树中所需的节点。

要了解更多，请访问树的遍历。

树的应用​

  • 二叉搜索树（BST）用于快速检查元素是否存在于一个集合中。
  • 堆是一种用于堆排序的树形结构。
  • 在现代路由器中使用了树的修改版本 Tries 来存储路由信息。
  • 大多数流行的数据库使用 B 树和 T 树（树结构的变体）来存储它们的数据。
  • 编译器使用语法树来验证你编写的每个程序的语法。
最后于 更新