一、二叉樹解決了什么問題

1、元素搜索

二叉樹的快速查找性質使其非常適合于元素搜索。通過二叉樹的查找操作，可以高效地搜索指定元素是否存在于樹中。

2、數(shù)據排序

二叉搜索樹還可以用于數(shù)據排序。具體地說，將數(shù)據插入到二叉搜索樹中，并按照一定規(guī)則遍歷樹，就可以得到有序的數(shù)據。

3、反向順序遍歷

通過對二叉樹的左右子樹遍歷順序進行逆序遍歷，可以實現(xiàn)反向順序遍歷。這在某些場景下非常有用，例如一個日志文件，需要按時間逆序輸出。

4、構建有效的數(shù)據結構

二叉樹可以應用到各種算法和系統(tǒng)中，提供高效的數(shù)據存儲和查找，非常適用于構建各種有效的數(shù)據結構，例如哈希表、堆等，這些數(shù)據結構在計算機科學中被廣泛使用。

二、二叉樹性質

1、一般二叉樹性質

在非空二叉樹的i層上，至多有2^i-1個節(jié)點(i>=1)。通過歸納法論證。在深度為K的二叉樹上非常多有2^k-1個結點（k>=1)。通過歸納法論證。對于任何一棵非空的二叉樹,如果葉節(jié)點個數(shù)為n₀，度數(shù)為2的節(jié)點個數(shù)為n₂，則有: n0 = n₂?+ 1。

在一棵二叉樹中，除了葉子結點（度為0）之外，就剩下度為2(n2)和1(n1)的結點了。則樹的結點總數(shù)為T = n0+n1+n2；在二叉樹中結點總數(shù)為T，而連線數(shù)為T-1。所以有：n0+n1+n2-1 = 2*n2 +n1；最后得到n0 = n2+1。

2、完全二叉樹性質

具有n的結點的完全二叉樹的深度為log₂n+1：

滿二叉樹是完全二叉樹，對于深度為k的滿二叉樹中結點數(shù)量是2^k-1 = n，完全二叉樹結點數(shù)量肯定非常多2^k-1，同時完全二叉樹倒數(shù)第二層肯定是滿的（倒數(shù)名列前茅層有結點，那么倒是第二層序號和滿二叉樹相同），所以完全二叉樹的結點數(shù)最少大于少一層的滿二叉樹，為2^k-1-1。

根據上面推斷得出：2^k-1-1< n=<2^k-1，因為結點數(shù)Nn為整數(shù)那么n<=2^k-1可以推出n<=2^k?，n>2^k-1-1可以推出 n>=2^k-1，所以2^k-1k? 。即可得k-1<=log₂n2n]+1。

如果有一顆有n個節(jié)點的完全二叉樹的節(jié)點按層次序編號，對任一層的節(jié)點i（1<=i<=n）有：

如果i=1，則節(jié)點是二叉樹的根，無雙親，如果i>1，則其雙親節(jié)點為[i/2]，向下取整如果2i>n那么節(jié)點i沒有左孩子，否則其左孩子為2i如果2i+1>n那么節(jié)點沒有右孩子，否則右孩子為2i+1

三、特殊的二叉樹及其特點

1、斜樹

所有的結點都只有左子樹（左斜樹），或者只有右子樹（右斜樹）。這就是斜樹，應用較少。

2、滿二叉樹

所有的分支結點都存在左子樹和右子樹，并且所有的葉子結點都在同一層上，這樣就是滿二叉樹。就是完美圓滿的意思，關鍵在于樹的平衡。

根據滿二叉樹的定義，得到其特點為：

葉子只能出現(xiàn)在最下一層。非葉子結點度一定是2。在同樣深度的二叉樹中，滿二叉樹的結點個數(shù)非常多，葉子樹非常多。

3、完全二叉樹

對一棵具有n個結點的二叉樹按層序排號，如果編號為i的結點與同樣深度的滿二叉樹編號為i結點在二叉樹中位置完全相同，就是完全二叉樹。滿二叉樹必須是完全二叉樹，反過來不一定成立。

其中關鍵點是按層序編號，然后對應查找。

結合完全二叉樹定義得到其特點：

葉子結點只能出現(xiàn)在最下一層（滿二叉樹繼承而來）。最下層葉子結點一定集中在左 部連續(xù)位置。倒數(shù)第二層，如有葉子節(jié)點，一定出現(xiàn)在右部連續(xù)位置。同樣結點樹的二叉樹，完全二叉樹的深度最?。M二叉樹也是對的）。

延伸閱讀1：平衡二叉樹

平衡二叉樹或者是一顆空樹，或者是具有以下性質的二叉樹：它的左子樹和右子樹的深度之差的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。平衡因子(bf)：結點的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1。很顯然，平衡二叉樹是在二叉排序樹(BST)上引入的，就是為了解決二叉排序樹的不平衡性導致時間復雜度大大下降。