目錄

1、二叉樹概念及結(jié)構(gòu)

1.1、概念

1.2、特殊的二叉樹

1.3、二叉樹的性質(zhì)

1.4、二叉樹的存儲結(jié)構(gòu)

1.4.1、順序存儲 -- 看截圖：二叉樹的順序存儲

1.4.2、鏈式存儲 -- 非完全二叉樹用這種方式存儲

2、二叉樹的遍歷

2.1、前序、中序以及后序遍歷2.2、層序遍歷

---

1、二叉樹概念及結(jié)構(gòu)

1.1、概念

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

1. 為空
2. 只有一個根節(jié)點
3. 由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成

二叉樹的概念：

????????

從圖中可看出：

1. 二叉樹不存在度大于2的結(jié)點 -- 二叉樹不一定度為2(可能是空樹，或者只有一個孩子)，但度為2的樹可以認為是二叉樹
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

二叉樹的幾種形式：

補充：普通二叉樹的增刪查改沒有價值！！
原因：用二叉樹這么復(fù)雜的結(jié)構(gòu)來存儲數(shù)據(jù)，太麻煩，不如用鏈表、數(shù)組...

補充：任何一顆二叉樹都要拆解成三部分來看
1.根
2.左子樹
3.右子樹

1.2、特殊的二叉樹

1.滿二叉樹：一個二叉樹，如果每一個層的結(jié)點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是2^k-1(等比數(shù)列之和，公比為2)，則它就是滿二叉樹。-- 就是每一層都是滿的。
2.完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。-- 就是前K-1層都是滿的，最后一層不一定滿(但至少有一個)，但是從左到右必須連續(xù)。
注：完全二叉樹的結(jié)點數(shù)：2^(k-1) ~ 2^k-1。

注意：滿二叉樹是一種特殊的完全二叉樹。

1.3、二叉樹的性質(zhì)

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

1. 若i>0，i位置節(jié)點的雙親序號：(i-1)/2；i=0，i為根節(jié)點編號，無雙親節(jié)點。
2. 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子。
3. 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子。

6.對于完全二叉樹來說，度為1的結(jié)點個數(shù)只有 1 個或 0 個。
7.如果一顆完全二叉樹的結(jié)點個數(shù)為奇數(shù)，說明度為 1 的結(jié)點個數(shù)為 0。
? ? ? ? ? ? ? ? ? ? ? ? ? ? 為偶數(shù)，說明度為 1 的結(jié)點個數(shù)為 1。
?

1.4、二叉樹的存儲結(jié)構(gòu)

二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈式結(jié)構(gòu)。

1.4.1、順序存儲

順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

補充：

父子結(jié)點間的下標有一個規(guī)律關(guān)系：
leftchild = parent*2+1
rightchild = parent*2+2
parent = (child-1)/2 // 無所謂是左孩子還是右孩子都行

1.4.2、鏈式存儲

二叉樹的鏈式存儲結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。鏈式結(jié)構(gòu)又分為二叉鏈和三叉鏈(紅黑樹、AVL樹)。

2、二叉樹的遍歷

2.1、前序、中序以及后序遍歷

學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。
所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。
訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。
遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎(chǔ)。
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：
1.前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前。 -- 根左右
2.中序遍歷(Inorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）。 -- 左根右
3.后序遍歷(Postorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。 -- 左右根
由于被訪問的結(jié)點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。
NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

2.2、層序遍歷

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

補充：深度優(yōu)先遍歷和廣度優(yōu)先遍歷
深度優(yōu)先遍歷：前序遍歷的本質(zhì)就是一種深度優(yōu)先遍歷(dfs--Depth First Search)
注：中序遍歷和后序遍歷也算是不太正規(guī)的深度優(yōu)先遍歷
廣度優(yōu)先遍歷：層序遍歷的本質(zhì)就是一種廣度優(yōu)先遍歷(bfs--Breadth First Search)
ex：掃雷的展開就可以使用這兩種遍歷來實現(xiàn)(就是點一下直接打開一堆的效果)