##### 树 - 树 - **树**是一种[[无向图]], 其中任意两个顶点间存在唯一一条路径, 或者说是一个无环[[连通图]], 即满足无环性与连通性的[[图]], 不存在自环或环, 任意两个顶点之间存在一条路径, 并且树中有 $n$ 个顶点和 $n-1$ 条边. 由若干棵不相交的树组成的集合称为森林. 可以从图构造[[生成树]] - 根节点, 树中指定的唯一没有父节点的节点 - 叶子节点, 没有子节点的节点 - 内部节点, 至少有一个子节点的节点 - 父节点, 一个节点的直接上级节点 - 子节点, 一个节点的直接下级节点 - 兄弟节点, 具有相同父节点的节点 - 祖先节点, 从根节点到某个节点的路径上的所有节点 - 后代节点, 某个节点的子树中的所有节点 - 子树, 树中某个节点及其所有后代节点组成的树 - 树的类型 - 有根树, 规定了根节点的树 - 二叉树, 每个节点最多有两个子节点的树 - 多叉树, 每个节点可以有相同多个子节点 - 满多叉树, 每个节点都有相同多个子节点 - 平衡树, 树中任意节点的左右子树高度差不超过 $1$