树结构及其在数据结构中的应用

树：一种非线性组织的数据结构

树的定义与特性

树（Tree）是一种由有限个节点构成的集合，其中当节点数量n等于0时，称为空树；
（1）该集合中存在唯一一个被称为根的节点
（2）包含若干个互不重叠的子树，而这些子树自身也符合树的结构
**通俗地讲：
（1）树由节点、边以及整体结构共同组成
（2）除根节点外，其余每个节点都仅有一个父节点，但可以拥有多个子节点
个人认为，树的概念其实并不难理解。可以形象地将其比喻为一棵葡萄藤（虽然这与我们常见的树木形态有所不同，毕竟在日常生活中见到的树木并非如此倒置的结构）。

树结构专业术语解析

（1）结点（这个概念较为直观，此处不再赘述）
（2）结点的度：指一个结点所连接的子树数量（简单来说，就是该结点下连接了多少个其他结点，这一数值即为该结点的度）
（3）树的度：整棵树中所有结点度数的最大值
注意：需要明确区分结点的度与树的度之间的差异：
结点的度是针对某个具体结点而言，而树的度则是针对整棵树而言。
（4）叶子：当一个结点的度为0时，该结点被称为叶子或终端结点（通俗地讲，就是没有子节点的那个孤立节点，如同断子绝孙一般）
（5）非终端结点（分支结点）：指那些度不为0的节点（换句话说，除了叶子之外的所有节点都属于非终端节点，这些节点往往承担着支撑上下结构的作用）。其中