树

介绍

• 树有一个根
• 树干上连着根的
• 树干上的分叉是树枝
• 树枝最后的是树叶

术语

• 节点的度 ( Degree ) : 节点的子树个数, 比如节点 B 的度为 2
• 树的度: 树的所有节点中最大的度数, 如上图树的度为 2
• 叶节点 ( Leaf ) : 度为 0 的节点 ( 也称为叶子节点 ) , 如上图的 H, I 等
• 父节点 ( Parent ) : 度不为 0 的节点称为父节点, 如上图节点 B 是节点 D 和 E 的父节点
• 子节点 ( Child ) : 若 B 是 D 的父节点, 那么 D 就是 B 的子节点
• 兄弟节点 ( Sibling ) : 具有同一父节点的各节点彼此是兄弟节点, 比如上图的 B 和 C, D 和 E 互为兄弟节点
• 路径和路径长度: 路径指的是一个节点到另一节点的通道, 路径所包含边的个数称为路径长度, 比如 A->H 的路径长度为 3
• 节点的层次 ( Level ) : 规定根节点在 1 层, 其他任一节点的层数是其父节点的层数加 1. 如 B 和 C 节点的层次为 2
• 树的深度 ( Depth ) : 树种所有节点中的最大层次是这棵树的深度, 如上图树的深度为 4