一、二叉树二叉树是每个节点最多有两个子节点的树结构这两个子节点分别称为左子节点和右子节点。其核心特征如下度不超过 2二叉树中每个节点的度子节点个数最大为 2即度可以取 0、1 或 2。有序树节点的子树有左右之分次序不能颠倒因此二叉树是有序树。例如下面这棵二叉树节点 1 为根节点2 和 3 分别是它的左右子节点每个节点的子节点都有明确的左右位置1 / \ 2 3 / \ \ 4 5 6二叉树的重要性质以下性质在面试和考试中经常出现需要熟练掌握第 i 层最多节点数二叉树的第 i 层最多有2^(i-1)个节点i ≥ 1。深度为 k 的二叉树最多节点数深度为 k 的二叉树最多有2^k - 1个节点k ≥ 1。叶子节点与度为 2 的节点关系对任意非空二叉树若叶子节点数为 n0度为 2 的节点数为 n2则n0 n2 1。节点总数与度关系若二叉树节点总数为 n度为 0、1、2 的节点数分别为 n0、n1、n2则 n n0 n1 n2且 n n1 2×n2 1。易错点提示性质 3 中「叶子节点数 度为 2 的节点数 1」是常考结论推导依据是「总边数 节点数 - 1」与「总边数 n1 2×n2」两个等式联立。二、二叉树的遍历遍历是按照某种顺序访问二叉树中的每个节点且每个节点只访问一次。下面以这棵二叉树为例a / \ b c / \ \ d e f / g1. 先序遍历访问顺序根节点 → 左子树 → 右子树。遍历结果a b d e g c f图中括号里的数字表示访问先后顺序a(1) / \ b(2) c(6) / \ \ d(3) e(4) f(7) / g(5)2. 中序遍历访问顺序左子树 → 根节点 → 右子树。遍历结果d b g e a c f。注:根节点左边是左子树的遍历结果右边是右子树的遍历结果。a(5) / \ b(2) c(6) / \ \ d(1) e(4) f(7) / g(3)3. 后序遍历访问顺序左子树 → 右子树 → 根节点。遍历结果d g e b f c a。注:1.第一个节点不一定是左子树节点但最后一个一定是根节点后序遍历交换左右子树后再逆序结果就是前序遍历。a(7) / \ b(4) c(6) / \ \ d(1) e(3) f(5) / g(2)4. 层序遍历访问顺序一层一层从上到下从左往右。遍历结果a b c d e f g。a(1) / \ b(2) c(3) / \ \ d(4) e(5) f(6) / g(7)三、两种特殊二叉树1. 满二叉树其每个节点都为最大值如果其层数为 k那结点总数是 (2^k) - 1。例如层数 k3 时结点总数是 2^3 - 1 7图形如下1 / \ 2 3 / \ / \ 4 5 6 72. 完全二叉树把若干元素一层层从左往右填充过程中没有缺口就是完全二叉树。例如下面这棵完全二叉树节点从左往右连续填充没有空缺1 / \ 2 3 / \ / 4 5 6