数据结构中的树

数据结构中的树有很多种,包括二叉树、二叉搜索树、AVL 树、红黑树、B 树等。

相关术语

  • 节点的度:一个节点包含的子树的个数。
  • 叶子节点或终端节点:度为 0 的节点。
  • 树的度:树内所有节点度的最大值。
  • 节点的高度:高度的定义是从下往上的,计算时为从该节点向下到某个叶子节点最长简单路径中边的条数(叶子节点的高度为 0)。
  • 节点的深度:深度的定义是从上往下的,计算时为从根节点往下到该节点最长简单路径中边的条数(根节点深度为 0)。
  • 节点的层数:从根节点往下,根节点的子节点为下一层,以此类推。

树的高度、深度在计算时,根据起始位置值的不同(0 或者 1),计算的值也会有差异。

树的例子

比如这棵树,当起始位置值为 0 时,树的高度为 4,深度为 4,层数为 4。当起始位置为 1 时,树的高度为 5,深度为 5,层数也为 5。