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