在计算机科学中，二叉树是一种树形的数据结构，其中每个节点最多具有两个子节点，其被称为左子节点和右子节点。仅使用集合理论概念的递归定义是（非空）二叉树是一个元组（L，S，R），其中L和R是二叉树或空集，S是单例集合。
树中的常见术语包括：
树结构的优点包括：
欢迎关注 DataLearner 官方微信，获得最新 AI 技术推送
如下图所示就是一个二叉树：
在计算机领域，二叉树有两个主要的用途：
第一个用途是用来实现二叉查找树和二进制堆，以便于搜索和排序。
第二个用途是作为具有相关分叉的数据表示。例如霍夫曼编码（Huffman coding）和分支图（Cladograms）。
注意二叉树并不是一种数据结构，它是一类数据结构。在二叉树数据结构中，不平衡的树比自平衡树的效率低很多。平衡与否取决于左右两个子树的高度差的绝对值。绝对值小于1的一般可以理解为平衡树，否则是不平衡树。
如果一个二叉树的每一个节点数都是最大节点数，那么它就是满二叉树。如下图：
如果一个二叉树除了最后一层外的每一个节点数都是最大节点数，那么它就是完全二叉树。如下图：
满二叉树的节点数是$2^k-1$ 完全二叉树的节点数$2^{h-1} \leq k < 2^h-1$
二叉树是一种非常基础的数据结构，它和它的变种有很多的应用。这里列举一些：
