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