二叉树定义

二叉树是 $n(n\ge 0)$ 个结点的有限集合：

  • 当 n = 0 时，称为空二叉树。
  • 当 n > 0 时，由一个根结点和两棵互不相交的左子树、右子树组成。
  • 左子树和右子树本身又分别是一棵二叉树。

二叉树是递归定义的数据结构。讨论二叉树的遍历、存储、线索化时，很多算法都可以自然写成“处理根、递归处理左子树、递归处理右子树”的形式。

基本特点

  • 每个结点至多有两棵子树。
  • 左子树和右子树有次序，不能随意颠倒。
  • 即使某个结点只有一个孩子，也要区分它是左孩子还是右孩子。
  • 空树也是二叉树，这是递归定义成立的边界情况。
  • 每个节点的度只有三种选择：$0,1,2$

与“度为 2 的有序树”的区别

二叉树不是简单的“度为 2 的有序树”：

  • 二叉树可以为空；普通树通常至少有一个结点。
  • 二叉树中一个结点只有一个孩子时，必须说明它是左孩子还是右孩子。
  • 度为 2 的有序树只强调孩子之间有顺序，不天然保留“左空、右非空”或“左非空、右空”这种位置区别。

这个区别会影响二叉树顺序存储：普通二叉树若按完全二叉树位置存储，缺失的左/右位置也可能需要保留空位。