DSA 树
树
树数据结构类似于 链表，每个节点包含数据，可以链接到其他节点。
我们之前已经涵盖了像数组、链表、栈和队列这样的数据结构。这些都是线性结构，这意味着每个元素都直接在序列中紧随其后。然而，树则不同。在树中，单个元素可以有多个“下一个”元素，允许数据结构向各个方向分支。
这种数据结构被称为“树”，因为它看起来像一棵树，只是倒置的，就像下面的图片一样。
树数据结构在很多情况下都很有用
- 分层数据：文件系统、组织模型等等。
- 数据库：用于快速数据检索。
- 路由表：用于网络算法中路由数据。
- 排序/搜索：用于排序数据和搜索数据。
- 优先级队列：优先级队列数据结构通常使用树来实现，例如二叉堆。
树术语和规则
使用下面的交互式树可视化来学习用来描述树数据结构的词汇。
树中的第一个节点被称为根节点。
连接一个节点到另一个节点的链接被称为边。
一个父节点链接到它的子节点。父节点的另一个词是内部节点。
一个节点可以有零个、一个或多个子节点。
一个节点只能有一个父节点。
没有链接到其他子节点的节点被称为叶子或叶子节点。
树高是从根节点到叶子节点的最大边数。上面树的高度为 2。
节点的高度是从节点到叶子节点的最大边数。
树的大小是树中节点的个数。
树的类型
树是计算机科学中的一种基本数据结构，用于表示分层关系。本教程涵盖了几种关键的树类型。
二叉树：每个节点最多有两个子节点，即左子节点和右子节点。这种结构是构建更复杂树类型（例如二叉搜索树和 AVL 树）的基础。
二叉搜索树 (BST)：一种二叉树，其中对于每个节点，左子节点的值较小，右子节点的值较大。
AVL 树：一种二叉搜索树，它自身平衡，以便对于每个节点，左子树和右子树之间的高度差最多为一。这种平衡通过在插入或删除节点时进行旋转来维持。
这些数据结构中的每一个都在接下来的页面中有详细描述，包括动画以及如何实现它们。
