Hello,米娜桑們，這里是君兮_，今天帶來數(shù)據(jù)結(jié)構(gòu)里的重點(diǎn)內(nèi)容也是在筆試，面試中的常見考點(diǎn)——樹與二叉樹，其中二叉樹又分為很多種，我們先來講講基礎(chǔ)的內(nèi)容帶大家一步步入門

一 樹的概念及其結(jié)構(gòu)

在介紹二叉樹之前，我們得先知道什么是樹結(jié)構(gòu)，以及幾個常用的概念

• 樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。
• 樹有一個特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)
  除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個前驅(qū)，可以有0個或多個后繼
• 因此，樹是遞歸定義的
  

1. 樹結(jié)構(gòu)中的相關(guān)概念

• 節(jié)點(diǎn)的度：
  一個節(jié)點(diǎn)含有的子樹的個數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6
• 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：
  度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn)
• 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：
  度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G…等節(jié)點(diǎn)為分支節(jié)點(diǎn)
• 雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：
  若一個節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
• 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：
  一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)
• 兄弟節(jié)點(diǎn)：
  具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)
• 樹的度：
  一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6
• 節(jié)點(diǎn)的層次：
  從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
• 樹的高度或深度：
  樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4
• 堂兄弟節(jié)點(diǎn)：
  雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)
• 節(jié)點(diǎn)的祖先：
  從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先
• 子孫：
  以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫
• 森林：
  由m（m>0）棵互不相交的樹的集合稱為森林

2. 樹的表示

• 這里不是本篇博客要講的重點(diǎn)，就簡單介紹一種常用的孩子兄弟表示法

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一個孩子結(jié)點(diǎn)
struct Node* _pNextBrother; // 指向其下一個兄弟結(jié)點(diǎn)
DataType _data; // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

二 什么是二叉樹？

1 概念

• 一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合:

• 1. 或者為空

• 2. 由一個根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成
  

• 從上圖可以看出：
  二叉樹不存在度大于2的結(jié)點(diǎn)
  二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

• 注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：
  

2 特殊的二叉樹

• 下面我們要介紹兩種特殊的二叉樹，理解并掌握這兩種二叉樹對我們之后學(xué)習(xí)的內(nèi)容也是非常重要的

1. 滿二叉樹：一個二叉樹，如果每一個層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是
說，如果一個二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 ，則它就是滿二叉樹。

2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K
的，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對
應(yīng)時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

3 二叉樹的性質(zhì)

• 1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1) 個結(jié)點(diǎn).
• 2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是 2^h-1.
• 3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個數(shù)為n2 ,則有 n2＝n0 +1
• 4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個結(jié)點(diǎn)的滿二叉樹的深度，h=log2(n+1) . (log2(n+1) 是log以2
  為底的對數(shù))
• 5. 對于具有n個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號，則對
  于序號為i的結(jié)點(diǎn)有：

1. 若i>0，i位置節(jié)點(diǎn)的雙親序號：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號，無雙親節(jié)點(diǎn)
2. 若2i+1<n，左孩子序號：2i+1，2i+1>=n 無左孩子 一共n個節(jié)點(diǎn)且存在數(shù)組里
3. 若2i+2<n，右孩子序號：2i+2，2i+2>=n 無右孩子 同上

• 對于上面的一些結(jié)論，基本上都是數(shù)學(xué)知識，畫個二叉樹的圖結(jié)合數(shù)學(xué)知識自己能很輕易的推出，這里就不浪費(fèi)筆墨了

4 二叉樹在內(nèi)存中的存儲

順序存儲

• 普通的二叉樹是不適合用數(shù)組來存儲的，因?yàn)榭赡軙嬖诖罅康目臻g浪費(fèi)。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。現(xiàn)實(shí)中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲。
• 需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段
  

鏈?zhǔn)酱鎯?/h4>

• 在學(xué)習(xí)二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于現(xiàn)在我們才剛?cè)腴T對二叉樹結(jié)構(gòu)掌握還不夠深入，為了降低大家學(xué)習(xí)成本，此處手動快速創(chuàng)建一棵簡單的二叉樹，快速進(jìn)入二叉樹操作學(xué)習(xí)，等二叉樹結(jié)構(gòu)了解的差不多時，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    int val;
}BTNode;

int main()
{
     
    //手動構(gòu)建
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    
    return 0;
}

• 從前面二叉樹的定義我們可以看出，二叉樹存在空樹和非空，當(dāng)非空時，二叉樹是由根節(jié)點(diǎn)，根節(jié)點(diǎn)的左子樹，根節(jié)點(diǎn)的右子樹組成的
• 也就是說，二叉樹的定義是遞歸式的，后面我們的遍歷等操作都是依據(jù)這一特性來進(jìn)一步實(shí)現(xiàn)的

5 二叉樹的遍歷

由于是第一次提出二叉樹的結(jié)構(gòu)，大家對各種概念還不夠了解，我們只先講講有哪幾種遍歷方式，具體的實(shí)現(xiàn)方式我們放到下一篇博客中講解

• 所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)

• 按照一定的規(guī)則，二叉樹的遍歷大概有以下幾種
  1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。
  2. 中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）。
  3. 后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后
  

• 由于被訪問的結(jié)點(diǎn)必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

• 4.層序遍歷
  除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然后從左到右訪問第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷
  

總結(jié)

• 今天的內(nèi)容就到這里了，由于是第一篇介紹樹狀結(jié)構(gòu)的博客，因此只講了一些基本的概念，但是千萬不要因?yàn)槭歉拍罹筒蝗ズ煤美斫馑?，?shí)際上如果你這些概念掌握的不夠熟練，在后面真正運(yùn)用的時候是很難弄懂的
• 因此，想弄懂關(guān)于樹與二叉樹這一塊內(nèi)容，得從一開始就熟悉里面的概念，有些文中給出卻沒有推的結(jié)論不妨自己試著推理一下會記得更牢，如果有任何有關(guān)的問題，歡迎在評論區(qū)提出或者直接私信我，我看到有時間會第一時間回復(fù)的

新人博主創(chuàng)作不易，如果感覺文章內(nèi)容對你有所幫助的話不妨三連一下再走唄。你們的支持就是我更新的動力！?。?/font>