一、背景

有很多数据的逻辑关系并不是线性关系，在实际场景中，常常存在着一对多，甚至是多对多的情况。比如家谱，组织结构，书的目录等，这些结构，我们称为树。

二、树的定义

在数据结构中，树的定义如下： 树（tree）是n（n≥0）个节点的有限集。

当n=0时，称为空树。

在任意一个非空树中，有如下特点。

有且仅有一个特定的称为根的节点。

当n>1时，其余节点可分为m（m>0）个互不相交的有限集。

每一个集合本身又是一个树，并称为根的子树。

节点1是根节点（root），没有父节点。

节点5、6、7、8是树的末端，没有“孩子”，被称为叶子节点（leaf）。

节点2、3、4、是树的中端，有父节点，有孩子，被称为中间节点或枝节点。

图中的虚线部分，是根节点1的其中一个子树。

树的最大层级数，被称为树的高度或深度，上图这个树的高度是4。

三、树的分类