二叉樹（Binary Tree)是n（n>=0)個結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。在二叉樹中又有一些特殊的存在，各種有著基于二叉樹特性之外的特點(diǎn)，我們稱之為特殊二叉樹。

為了更好的理解特殊二叉樹，我們先來看看二叉樹的特點(diǎn)：

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

（2）左子樹和右子樹是由順序的，次序不能顛倒。

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

我們結(jié)合著二叉樹的一些特點(diǎn)來看看特殊二叉樹。

1.斜樹

所有結(jié)點(diǎn)都只有左子樹的二叉樹稱之為左斜樹，所有結(jié)點(diǎn)都只有右子樹的二叉樹稱之為右斜樹。

特點(diǎn)：

1）斜樹每層只有一個結(jié)點(diǎn)

2）結(jié)點(diǎn)個數(shù)等于二叉樹深度。

2.滿二叉樹

所有分支結(jié)點(diǎn)都存在左子樹和右子樹，且所有葉子都在同一層上的二叉樹叫做滿二叉樹。

特點(diǎn)：

1) 葉子只出現(xiàn)在最下一層

2) 非葉子節(jié)點(diǎn)度一定為2

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

4) 葉子結(jié)點(diǎn)數(shù)為2h

5) 第k層的結(jié)點(diǎn)數(shù)是：2k-1

3. 完全二叉樹

對于具有n個結(jié)點(diǎn)的二叉樹按層序編號，如果每個結(jié)點(diǎn)的編號與同樣深度的滿二叉樹中對應(yīng)編號的結(jié)點(diǎn)在二叉樹中位置完全相同，則該二叉樹稱為完全二叉樹。

特點(diǎn)：

1）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。

2）葉子結(jié)點(diǎn)只出現(xiàn)在最下兩層

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

4）倒數(shù)二層若有葉子節(jié)點(diǎn)一定集中在右部連續(xù)位置如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子

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

4. 線索二叉樹

二叉樹的結(jié)點(diǎn)加上線索的二叉樹叫做線索二叉樹。

線索：指將二叉樹中的空指針指向該節(jié)點(diǎn)的前驅(qū)或者后繼

線索化：對二叉樹以某種遍歷方式（如先序、中序、后序或?qū)哟蔚龋┻M(jìn)行遍歷，使其變?yōu)榫€索二叉樹的過程

5. 霍夫曼樹

霍夫曼樹是指帶權(quán)路徑長度WPL最小的二叉樹。

構(gòu)建算法：

1）根據(jù)給定的n個權(quán)值{w1,w2,...,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,...,Tn},其中每棵二叉樹Ti只有一個帶權(quán)為wi根節(jié)點(diǎn)，左右子樹均為空。

2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根節(jié)點(diǎn)的權(quán)值為其左右子樹上根節(jié)點(diǎn)的權(quán)值之和。

3）在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。

4）重復(fù)2和3步驟，直到F只含一棵樹為止。得到的便是Huffman Tree

6. 二叉查找樹（Binary Search Tree）又稱二叉排序樹（Binary Sort Tree）或二叉搜索樹

二叉查找樹是指一棵空樹，或者是具有下列性質(zhì)的二叉樹：

（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

（3）左、右子樹也分別為二叉排序樹；

（4）沒有鍵值相等的結(jié)點(diǎn)。

特點(diǎn)：

1）二叉排序樹是為了提高查找和插入刪除關(guān)鍵字的速度二叉排序樹這樣的非線性結(jié)構(gòu)，也2）有利于插入和排序的實(shí)現(xiàn)。

3）二叉查找樹的高度決定了二叉查找樹的查找效率。

4）對二叉查找樹進(jìn)行中序遍歷，即可得到有序的數(shù)列。

以上就是為大家簡短介紹的6種特殊二叉樹，特殊二叉樹本質(zhì)上還是二叉樹，具有二叉樹的一切特性，我們可以以二叉樹為基點(diǎn)，慢慢去學(xué)習(xí)這些特殊二叉樹。學(xué)好二叉樹不是一朝一夕的事情，可以借助本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中的生動形象的二叉樹圖解來深入學(xué)習(xí)二叉樹。