什么是树结构？
树（Tree）是一种具有层次性的非线性数据结构。它是由一个或多个节点（Node）组成。每个节点由数据和指针组成。存在一个特殊的节点称为根节点。
除了根节点，其余节点可分为n个互斥的集合，每个集合本身也是一个树结构。
其中A是树根节点，其子节点B、E、K又可以分为3个集合：
第1个集合：B、C、D
第2个集合：E F G H I J
第3个集合：K
每个集合又是一个树结构。
注意：一棵合法的树，节点之间可相互连接，但不能形成环路。
概念
1. 森林
森林（Forest）：森林是多棵树的集合，每棵树都是独立的树结构。森林=多棵树
一棵树被定义为一组节点和边，这些节点和边之间相互连接，形成一个层次结构。
如果有多个独立的树，它们就构成了一个森林。森林中的每棵树都可以有自己的根节点，不必连接到其他树。
2. 层次性结构
树是一个层次性结构，其中有一个顶部的根节点（Root）。根节点可以有零个或多个子节点，而子节点也可以有自己的子节点，形成层次结构。
3. 节点
树的基本元素是节点，每个节点可以包含数据、指针，并可以连接到零个或多个子节点。节点之间通过边（指针）连接。
4. 根节点
树的根节点是顶层节点，它没有父节点，它是树的起始点。
5.父节点和子节点
树结构是有层次的。一个节点可以有一个父节点和零个或多个子节点。
父节点是位于该节点直接连接的较高层次的节点，子节点是位于该节点较低层次、直接连接的节点。
6. 叶子节点（也叫终端节点） &非终端节点（Nonterminal Node）
叶节点是没有子节点的节点，它们位于树的末端。即度数为0的节点就是树叶即叶子节点
非终端节点：树叶节点以为的节点。
7. 祖先（Ancestor）和子孙（Descendent即后代）
祖先是从树根节点到该节点路径上所包含的所有节点。比如上图的C节点的祖先是B、A。I节点的祖先是G、E、A
子孙（后代）该节点可连接的下层的节点，比如上图的B节点的子孙节点是C、D。E的子孙节点是F、G、H、I、J
8. 兄弟节点（Sibling） && 同代（Generation）
有共同父节点的节点成为兄弟节点。
同代：同一颗树，处于同一层级的节点，成为同代
9. 度数（Degree）
度数是对具体某个节点而已，表示其所有子树的个数（也可以说是子节点的个数）。比如上图B节点的度数是2（有2个子节点）、E节点的度数是3（有3个子节点）
度数为0的节点就是树叶即叶子节点
10. 层数（Level）&& 高度（Height）
树是分层级的。根节点所在层级是第1层，其子节点为第2层，孙子为第3层，依次类推。有几层就是几层树。
高度：树的最大层数。上图是4层树，因此高度是4
树结构的应用场景
树结构在计算机科学和信息技术中有广泛的应用，它们用于组织和管理层次性数据，提供了高效的数据存储、搜索和检索方法。以下是一些树结构的常见应用场景：
-
文件系统：计算机的文件系统通常以树的形式组织文件和目录。每个目录可以包含文件和其他子目录，从根目录开始，形成一个树结构。
-
数据库索引：数据库系统使用树结构（通常是B树或B+树）来加速数据检索操作。这些树结构允许快速查找和范围查询，对于大型数据库非常重要。
-
XML和JSON解析：树结构常用于解析和表示XML（eXtensible Markup Language）和JSON（JavaScript Object Notation）数据。这些数据格式具有层次结构，可以用树表示。
-
编程语言的抽象语法树（AST）：在编程语言编译器和解释器中，AST用于表示源代码的语法结构，支持编译、解释和代码分析。
-
家谱和组织结构：家谱通常以树的形式表示，每个个体有父母和子孙。组织结构中的层次性管理也可以用树结构表示，如公司的组织架构。
-
网络路由：路由表通常使用树结构来确定数据包的传输路径。IP路由表使用Trie树来实现高效的路由查找。
-
图形用户界面（GUI）部件层次：GUI应用程序的用户界面元素（如窗口、按钮、文本框）通常以树结构的形式组织，这有助于事件处理和布局管理。
-
平衡树：平衡树（如AVL树和红黑树）用于实现高效的插入、删除和搜索操作，通常用于实现数据存储和数据库索引。
-
哈夫曼树：哈夫曼树用于数据压缩，其中频率较高的字符在树的较浅层，频率较低的字符在树的较深层，以实现数据压缩。
-
决策树：在机器学习中，决策树用于分类和预测任务，树的节点代表不同的特征和决策规则。