一、二叉樹二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)的樹結(jié)構(gòu)這兩個(gè)子節(jié)點(diǎn)分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。其核心特征如下度不超過 2二叉樹中每個(gè)節(jié)點(diǎn)的度子節(jié)點(diǎn)個(gè)數(shù)最大為 2即度可以取 0、1 或 2。有序樹節(jié)點(diǎn)的子樹有左右之分次序不能顛倒因此二叉樹是有序樹。例如下面這棵二叉樹節(jié)點(diǎn) 1 為根節(jié)點(diǎn)2 和 3 分別是它的左右子節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)都有明確的左右位置1 / \ 2 3 / \ \ 4 5 6二叉樹的重要性質(zhì)以下性質(zhì)在面試和考試中經(jīng)常出現(xiàn)需要熟練掌握第 i 層最多節(jié)點(diǎn)數(shù)二叉樹的第 i 層最多有2^(i-1)個(gè)節(jié)點(diǎn)i ≥ 1。深度為 k 的二叉樹最多節(jié)點(diǎn)數(shù)深度為 k 的二叉樹最多有2^k - 1個(gè)節(jié)點(diǎn)k ≥ 1。葉子節(jié)點(diǎn)與度為 2 的節(jié)點(diǎn)關(guān)系對(duì)任意非空二叉樹若葉子節(jié)點(diǎn)數(shù)為 n0度為 2 的節(jié)點(diǎn)數(shù)為 n2則n0 n2 1。節(jié)點(diǎn)總數(shù)與度關(guān)系若二叉樹節(jié)點(diǎn)總數(shù)為 n度為 0、1、2 的節(jié)點(diǎn)數(shù)分別為 n0、n1、n2則 n n0 n1 n2且 n n1 2×n2 1。易錯(cuò)點(diǎn)提示性質(zhì) 3 中「葉子節(jié)點(diǎn)數(shù) 度為 2 的節(jié)點(diǎn)數(shù) 1」是常考結(jié)論推導(dǎo)依據(jù)是「總邊數(shù) 節(jié)點(diǎn)數(shù) - 1」與「總邊數(shù) n1 2×n2」兩個(gè)等式聯(lián)立。二、二叉樹的遍歷遍歷是按照某種順序訪問二叉樹中的每個(gè)節(jié)點(diǎn)且每個(gè)節(jié)點(diǎn)只訪問一次。下面以這棵二叉樹為例a / \ b c / \ \ d e f / g1. 先序遍歷訪問順序根節(jié)點(diǎn) → 左子樹 → 右子樹。遍歷結(jié)果a b d e g c f圖中括號(hào)里的數(shù)字表示訪問先后順序a(1) / \ b(2) c(6) / \ \ d(3) e(4) f(7) / g(5)2. 中序遍歷訪問順序左子樹 → 根節(jié)點(diǎn) → 右子樹。遍歷結(jié)果d b g e a c f。注:根節(jié)點(diǎn)左邊是左子樹的遍歷結(jié)果右邊是右子樹的遍歷結(jié)果。a(5) / \ b(2) c(6) / \ \ d(1) e(4) f(7) / g(3)3. 后序遍歷訪問順序左子樹 → 右子樹 → 根節(jié)點(diǎn)。遍歷結(jié)果d g e b f c a。注:1.第一個(gè)節(jié)點(diǎn)不一定是左子樹節(jié)點(diǎn)但最后一個(gè)一定是根節(jié)點(diǎn)后序遍歷交換左右子樹后再逆序結(jié)果就是前序遍歷。a(7) / \ b(4) c(6) / \ \ d(1) e(3) f(5) / g(2)4. 層序遍歷訪問順序一層一層從上到下從左往右。遍歷結(jié)果a b c d e f g。a(1) / \ b(2) c(3) / \ \ d(4) e(5) f(6) / g(7)三、兩種特殊二叉樹1. 滿二叉樹其每個(gè)節(jié)點(diǎn)都為最大值如果其層數(shù)為 k那結(jié)點(diǎn)總數(shù)是 (2^k) - 1。例如層數(shù) k3 時(shí)結(jié)點(diǎn)總數(shù)是 2^3 - 1 7圖形如下1 / \ 2 3 / \ / \ 4 5 6 72. 完全二叉樹把若干元素一層層從左往右填充過程中沒有缺口就是完全二叉樹。例如下面這棵完全二叉樹節(jié)點(diǎn)從左往右連續(xù)填充沒有空缺1 / \ 2 3 / \ / 4 5 6