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

1、元素搜索

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

2、數據排序

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

3、反向順序遍歷

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

4、構建有效的數據結構

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

二、二叉樹性質

1、一般二叉樹性質

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

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

2、完全二叉樹性質

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

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

根據上面推斷得出：2^k-1-1< n=<2^k-1，因為結點數Nn為整數那么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個節點的完全二叉樹的節點按層次序編號，對任一層的節點i（1<=i<=n）有：

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

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

1、斜樹

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

2、滿二叉樹

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

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

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

3、完全二叉樹

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

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

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

葉子結點只能出現在最下一層（滿二叉樹繼承而來）。最下層葉子結點一定集中在左 部連續位置。倒數第二層，如有葉子節點，一定出現在右部連續位置。同樣結點樹的二叉樹，完全二叉樹的深度最小（滿二叉樹也是對的）。

延伸閱讀1：平衡二叉樹

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