二叉树（binary tree）是一种每个节点最多拥有两个子节点的树结构，两个子节点通常分别称为左子节点和右子节点。NIST《算法与数据结构词典》给出的递归定义是：二叉树要么为空，要么由根节点、左二叉树和右二叉树组成。
递归结构
二叉树的左子树和右子树本身仍然是二叉树。一个节点可以同时拥有左右子节点，也可以只有其中一个子节点，或者没有子节点。
左、右表示两个不同的位置，并不自动表示节点值的大小关系。二叉搜索树是在二叉树的结构基础上，额外增加键值排列约束的一类数据结构；不能把普通二叉树直接当作二叉搜索树。
常见形态
根据节点分布方式，二叉树可以进一步形成满二叉树、完全二叉树、完美二叉树和平衡二叉树等类型。它们对节点是否拥有两个子节点、各层是否填满以及左右子树高度差等条件有不同要求。
二叉搜索树、二叉堆、表达式树和哈夫曼树等结构也常以二叉树为基础，但会增加各自的语义或约束。
遍历
常见遍历方式包括：
- 前序遍历：先访问当前节点，再访问左子树和右子树。
- 中序遍历：先访问左子树，再访问当前节点和右子树。
- 后序遍历：先访问左右子树，再处理当前节点。
- 层序遍历：按照节点所在层级，从上到下依次访问。
前三种遍历直接体现了二叉树的递归结构；层序遍历通常借助队列逐层处理节点。具体选择取决于问题需要在何时处理当前节点，以及是否要保留层级顺序。
存储方式
二叉树通常可以通过节点引用存储，每个节点分别保存左、右子节点；对于节点分布紧凑的完全二叉树，也可以使用数组按层序存储，并通过下标关系定位父子节点。
引用结构更适合形态不规则、需要频繁改变连接关系的树；数组结构在完全二叉树等场景中更紧凑，也便于实现二叉堆。