数据结构（六）——树

树数据结构

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

image.png

树的相关术语

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

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

有关树的另一个术语是子树。子树由节点和它的后代构成。例如，节点 13、12 和 14 构成了上图中树的一棵子树。
节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。比如，节点 3 有 3 个祖先节点（5、7 和 11），它的深度为 3。