上一篇博客我們對樹有了初步了解與學(xué)習(xí)，這篇我將初步學(xué)習(xí)二叉樹！！（新年快樂！）

目錄

二叉樹??

1、定義：

2、特點(diǎn)：

3、基本形態(tài)：

4、二叉樹的種類：

（1）滿二叉樹

（2）完全二叉樹 （效率高）

（3）斜樹

5、二叉樹的性質(zhì)：

?6、二叉樹的存儲：

二叉樹??

1、定義：

二叉樹是每個節(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)。二叉樹是n（n>=0）個結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。

2、特點(diǎn)：

（1）每個結(jié)點(diǎn)最多有兩棵子樹（二叉樹不存咋大于2的結(jié)點(diǎn)）。

（2）二叉樹的子樹有左右順序之分，其子樹的次序不能顛倒。

（3）即使樹中的某結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。

3、基本形態(tài)：

（1）空二叉樹；

（2）只有一個根結(jié)點(diǎn)；

（3）根結(jié)點(diǎn)只有左子樹；

（4）根結(jié)點(diǎn)只有右子樹；

（5）根結(jié)點(diǎn)既有左子樹又有右子樹。

4、二叉樹的種類：

（1）滿二叉樹

定義：一個二叉樹每個層的結(jié)點(diǎn)數(shù)都達(dá)到了最大值。

【即如果一個二叉樹的層數(shù)為n，則結(jié)點(diǎn)總數(shù)是（2^k）-1】

滿二叉樹是一種特殊的完全二叉樹！！

特點(diǎn)：

a.葉子只能出現(xiàn)在最下一層。出現(xiàn)在其他層就不可能達(dá)到平衡。

b.非葉子結(jié)點(diǎn)的度一定為2。

c.在同樣深度的二叉樹中，滿二叉樹的結(jié)點(diǎn)個數(shù)最多，葉子樹最多。

（2）完全二叉樹 （效率高）

定義：一棵深度為k的有n個結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹中編號為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

?

特點(diǎn)：

a.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層。

b.最下層的葉子一定集中在左部連續(xù)位置。

c.倒數(shù)第二層，如果有葉子結(jié)點(diǎn)，一定都在右部連續(xù)位置。

d.如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子，即不存在只有右子樹的情況。

e.同樣結(jié)點(diǎn)數(shù)的二叉樹，完全二叉樹的深度最小。

（3）斜樹

向哪邊斜就叫啥斜樹！！

左斜樹：所有的結(jié)點(diǎn)都只有左子樹的二叉樹。

右斜樹：所有的結(jié)點(diǎn)都只有右子樹的二叉樹。

5、二叉樹的性質(zhì)：

（1）

若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)? (i>0)個結(jié)點(diǎn)。

（2）

若規(guī)定只有根結(jié)點(diǎn)的二叉樹的深度為1，則深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)是2^k-1 (k>=1)。

（3）

對任何一棵二叉樹，如果其葉結(jié)點(diǎn)個數(shù)為n0，度為2的非葉結(jié)點(diǎn)個數(shù)為n2，則有n0=n2+1。

（4）

具有n個結(jié)點(diǎn)的完全二叉樹的深度k為[log2n]+1上取整。（[x]表示不大于x的最大整數(shù)）

（5）

對于具有n個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的順序?qū)λ薪Y(jié)點(diǎn)從0開始編號，對于序號為i的結(jié)點(diǎn)有：
若i>0，雙親序號：(i-1)/2； i=0，i為根結(jié)點(diǎn)編號， 無雙親結(jié)點(diǎn)。
若2i+1<n，左孩子序號：2i+1，否則無左孩子。
若2i+2<n，右孩子序號：2i+2，否則無右孩子。

?6、二叉樹的存儲：

二叉樹的存儲結(jié)構(gòu)分為順序存儲和類似于鏈表的鏈?zhǔn)酱鎯?/strong>。

//孩子表示法class Node6 
{int val;     //數(shù)據(jù)域Node6 left;  //左孩子的引用，常常代表左孩子為根的整棵左子樹Node6 right; //右孩子的引用，常常代表右孩子為根的整棵右子樹
}//孩子雙親表示法public class Node7 {int val;      //數(shù)據(jù)域Node7 left;   //左孩子的引用，常常代表左孩子為根的整棵左子樹Node7 right;  //右孩子的引用，常常代表右孩子為根的整棵右子樹Node7 parent; //當(dāng)前結(jié)點(diǎn)的根結(jié)點(diǎn)
}