在计算机科学中，树是一种抽象数据结构(abstract data type)(ADT)或者是根据这种抽象数据结构(ADT)实现的数据结构。

树的定义：树是由节点或者顶点和边组成的无循环的数据结构。当树没有节点时，我们称它为空树。非空的树由一个根节点和可能形成层次结构的许多级别的附加节点组成。

树的术语

术语 名称 说明
根 root 树的顶部节点，有且仅有一个根节点
边 edge 两个节点直接的连接，在 N 个节点里面，最多只有 N-1 条边
子节点 child 两个节点直接相连时，远离根节点的节点叫子节点
父节点 parent 两个节点直接相连时，靠近根节点的节点叫父节点
兄弟节点 siblings 具有相同父节点的两个节点
叶节点 leaf 没有子节点的节点
分支节点 branch node 至少有一个子节点的节点
度 degree 节点含有的子节点的个数，叶节点的度为 0
层 level 从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推
深度 depth 节点的深度为根节点到节点的路径长，根的深度为 0
高度 height 节点到高度为节点到叶节点的最长路径长，所有叶节点的高度为 0

关于树的深度与高度的区别可以查看：What is the difference between tree depth and height?

常见的树的种类

  • 二叉树 Binary Tree
    • 二叉查找树 Binary Search Tree
      • 平衡二叉查找树 Self-balancing Tree
  • B 树 B-Tree
  • 堆 Heap

注：由于二叉树的内容比较多，故分开来记录。

B 树(B-Tree)

B 树是一个具有多键值多子树自平衡搜索树。一个 m 阶的 B 树具有以下特性：

  1. 所有的叶节点必须在同一层。
  2. 所有的节点除了根节点，至少要有[m / 2] / 2 个键值，至多有 m - 1 个键值。
  3. 所有的内部节点除根节点，至少有 m / 2 个子节点。
  4. 若根节点不是叶子节点，至少要有 2 个子节点。
  5. 具有 n - 1 个键值的非叶节点，必须有 n 个子节点。
  6. 一个节点内的键值必须为升序。

参考链接