什么是树

在计算机科学中，树是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

其他数据结构，如数组、链表、堆栈和队列，都是按顺序存储数据的线性数据结构。为了在线性数据结构中执行任何操作，时间复杂度随着数据大小的增加而增加。但是，在当今的计算世界中，这是不可接受的。树数据结构允许更快、更轻松地访问数据，因为它是一种非线性数据结构。

树术语

树的节点

节点是包含键或值以及指向其子节点的指针的实体。每条路径的最后一个节点称为叶节点或不包含指向子节点的链接/指针的外部节点。至少有一个子节点的节点称为内部节点。

树的边缘

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

树的节点和边

树根节点

它是树的最顶层节点。

节点高度

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

节点深度

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

树的高度

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

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

节点度数

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

森林

一组不相交的树称为森林。您可以通过砍伐树根来创建森林。

从一棵树创造森林

树的类型

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

树的应用

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