二叉树的几个术语

根(root)节点、内部(inner)节点、叶子(leaf)节点。

边(Edge)/ 链接:指向节点的线。除root之外,每个节点都有且仅有一个链接指向自己。

  • 图中的黑色实线均为边或链接
  • 未指向任何节点的线叫空链接

路径(Path):从某一节点出发到另一节点结束,期间经历的边和节点所构成的轨迹叫做这两个节点间的路径。路径是自上向下的。

  • 节点间的路径长度 = 所经历的边的个数

节点的度(degree):节点所拥有的子树的个数叫做该节点的度。

  • 树的度:各节点度的最大值即为该树的度。

节点的高度(height):当前节点与最深的叶子节点间的路径长度。仅有根节点的树,节点高度为零。

  • 树的高度:根节点的高度即为该树的高度。

节点的深度(depth):从根节点到当前节点的路径长度。规定根节点的深度为零。

  • 树的深度:树没有“深度”,只有“高度”,只能说一棵树有多高。

节点的层次(level):某节点所处的层等于其深度加1,根节点处于第一层级。

访问

注意,“访问”指的是在某个节点上执行了相应的操作,如果仅仅是经过节点,不能叫做“访问”。