二叉树的基本概念

二叉树（Binary Tree）是 n（ $n \geq 0$ ）个结点的有限集合。当 $n = 0$ 时称为空二叉树；否则二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

递归定义

二叉树的定义本身具有递归性：

结点的度：结点拥有的子树数。二叉树的结点的度最大为 2
叶子结点（Leaf）：度为 0 的结点，也称终端结点
分支结点：度不为 0 的结点，也称非终端结点
孩子与双亲：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲
兄弟：同一个双亲的孩子之间互称兄弟
结点的层次：从根开始定义，根为第 1 层，根的孩子为第 2 层，以此类推
深度（Depth）：树中结点的最大层次数
满二叉树：深度为 k 且含有 2^k - 1 个结点的二叉树。每一层上的结点数都达到最大
完全二叉树：深度为 k 的、有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称为完全二叉树

满二叉树的特点：

完全二叉树的特点：

二叉树严格区分左子树和右子树，即使只有一棵子树也要明确是左子树还是右子树，这是二叉树与有序树的本质区别之一。