树 - 《数据结构与算法》

树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱，或是公司的组织架构图。

树有以下一些术语：

节点

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点：

位于树顶部的节点叫作根节点（11）。它没有父节点。树中的每个元素都叫作节点，节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点（7、5、9、15、13和20是内部节点）。没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18和25是叶节点）。

子树由节点和它的后代构成。例如，节点13、12和14构成了上图中树的一棵子树。

深度、高度、层级是非常相似的东西。下面这幅图展示了深度、高度、层级三者在树中的数值。