二叉树

二叉树是一种树状结构，它是有根的，其中每个顶点最多有两个子节点，并且每个顶点的子节点都被指定为其左子节点或右子节点（West 2000，第 101 页）。换句话说，与真树不同，子节点的相对位置很重要。

放弃左右子节点被认为是唯一的要求，就得到了一棵被称为弱二叉树的真树（其中，按照惯例，根节点也被要求最多与一个图顶点相邻）。

二叉树的高度是树内层级的数量。高度 , 2, ... 的二叉树的节点数量为 1, 3, 21, 651, 457653, ... (OEIS A001699)。给出这些计数的递推方程是

(1)

其中 。

具有 个节点的二叉树的数量为 1, 2, 5, 14, 42, ... (OEIS A000108)，它们是卡塔兰数 。

对于高度为 且有 个节点的二叉树，

(2)

这些极端情况分别对应于平衡树（除了树叶之外的每个节点都有一个左子节点和右子节点，并且所有树叶都在同一层级）和退化树（每个节点只有一个外向分支）。

对于组织成二叉树的数据搜索，找到一个项目所需的搜索步骤 的数量受限于

(3)

将任意树部分平衡为所谓的 AVL 二叉搜索树可以提高搜索速度。