前面兩篇博客介紹了線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)以及對(duì)應(yīng)的操作，并且還聊了棧與隊(duì)列的相關(guān)內(nèi)容。本篇博客我們就繼續(xù)聊數(shù)據(jù)結(jié)構(gòu)的相關(guān)東西，并且所涉及的相關(guān)Demo依然使用面向?qū)ο笳Z言Swift來表示。本篇博客我們就來介紹樹結(jié)構(gòu)的一種：二叉樹。在之前的博客中我們簡單的聊了一點(diǎn)樹的東西，樹結(jié)構(gòu)的特點(diǎn)是除頭節(jié)點(diǎn)以外的節(jié)點(diǎn)只有一個(gè)前驅(qū)，但是可以有一個(gè)或者多個(gè)后繼。而二叉樹的特點(diǎn)是除頭結(jié)點(diǎn)外的其他節(jié)點(diǎn)只有一個(gè)前驅(qū)，節(jié)點(diǎn)的后繼不能超過2個(gè)。

本篇博客，我們只對(duì)二叉樹進(jìn)行討論。在本篇博客中，我們對(duì)二叉樹進(jìn)行創(chuàng)建，然后進(jìn)行各種遍歷，最后將二叉樹進(jìn)行線索化。在Demo實(shí)現(xiàn)之前，我們先對(duì)二叉樹的概念及其特性進(jìn)行介紹，然后在給出具體的代碼實(shí)現(xiàn)。

 

一、二叉樹的特性

上面我們已經(jīng)提到過，一個(gè)除頭結(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)，有零到兩個(gè)后繼的樹即為二叉樹。在二叉樹中，一個(gè)節(jié)點(diǎn)可以有左節(jié)點(diǎn)或者左子樹，也可以有右節(jié)點(diǎn)或者右子樹。一些特殊的二叉樹，比如斜二叉樹、滿二叉樹、完全二叉樹等等就不做過多贅述了。說這么多，不如看一張圖來的直觀。下方就是一個(gè)典型的二叉樹。

了解二叉樹，理解其特性還是比較重要的?；诙鏄浔旧淼倪壿嫿Y(jié)構(gòu)，下方是二叉樹這種數(shù)據(jù)結(jié)構(gòu)所具備的特性。

  • 特性1：在二叉樹的第i層上至多有2^(i-1)（i >= 1）個(gè)節(jié)點(diǎn)。
    • 這一特性比較好理解，如果層數(shù)是從零開始數(shù)的話，那么低i層上的節(jié)點(diǎn)數(shù)就是2^i，因?yàn)槎鏄鋵优c層之間的節(jié)點(diǎn)數(shù)是以2的指數(shù)冪進(jìn)行增長的。如果根節(jié)點(diǎn)算是第0層的話，那么第n層的節(jié)點(diǎn)數(shù)就是2^n次冪。
  • 特性2：深度為k的二叉樹至多有2^k-1（k>=1）個(gè)節(jié)點(diǎn)。
    • 這一特性也是比較好理解的, 由數(shù)學(xué)上的遞加公式就可以很容易的推出來。由特性1易知每層最多有多少個(gè)節(jié)點(diǎn)，那么深度為k的話，說明一共有k層，那么共有節(jié)點(diǎn)數(shù)為：2^0 + 2^1 + 2^2 + 2^(k-1) = 2^k - 1。