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

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

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

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

（3）即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹。

我們結合著二叉樹的一些特點來看看特殊二叉樹。

1.斜樹

所有結點都只有左子樹的二叉樹稱之為左斜樹，所有結點都只有右子樹的二叉樹稱之為右斜樹。

特點：

1）斜樹每層只有一個結點

2）結點個數等于二叉樹深度。

2.滿二叉樹

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

特點：

1) 葉子只出現在最下一層

2) 非葉子節點度一定為2

3) 同樣深度二叉樹中，滿二叉樹結點個數最多葉子樹最多

4) 葉子結點數為2h

5) 第k層的結點數是：2k-1

3. 完全二叉樹

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

特點：

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

2）葉子結點只出現在最下兩層

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

4）倒數二層若有葉子節點一定集中在右部連續位置如果結點度為1，則該結點只有左孩子

5）同樣結點數的二叉樹，完全二叉樹的深度最小

4. 線索二叉樹

二叉樹的結點加上線索的二叉樹叫做線索二叉樹。

線索：指將二叉樹中的空指針指向該節點的前驅或者后繼

線索化：對二叉樹以某種遍歷方式（如先序、中序、后序或層次等）進行遍歷，使其變為線索二叉樹的過程

5. 霍夫曼樹

霍夫曼樹是指帶權路徑長度WPL最小的二叉樹。

構建算法：

1）根據給定的n個權值{w1,w2,...,wn}構成n棵二叉樹的集合F={T1,T2,...,Tn},其中每棵二叉樹Ti只有一個帶權為wi根節點，左右子樹均為空。

2）在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根節點的權值為其左右子樹上根節點的權值之和。

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

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

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

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

（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

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

（4）沒有鍵值相等的結點。

特點：

1）二叉排序樹是為了提高查找和插入刪除關鍵字的速度二叉排序樹這樣的非線性結構，也2）有利于插入和排序的實現。

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

4）對二叉查找樹進行中序遍歷，即可得到有序的數列。

以上就是為大家簡短介紹的6種特殊二叉樹，特殊二叉樹本質上還是二叉樹，具有二叉樹的一切特性，我們可以以二叉樹為基點，慢慢去學習這些特殊二叉樹。學好二叉樹不是一朝一夕的事情，可以借助本站的數據結構和算法教程中的生動形象的二叉樹圖解來深入學習二叉樹。