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

1、元素搜索

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

2、數(shù)據(jù)排序

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

3、反向順序遍歷

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

4、構(gòu)建有效的數(shù)據(jù)結(jié)構(gòu)

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

二、二叉樹性質(zhì)

1、一般二叉樹性質(zhì)

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

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

2、完全二叉樹性質(zhì)

具有n的結(jié)點(diǎn)的完全二叉樹的深度為log₂n+1：

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

根據(jù)上面推斷得出：2^k-1-1< n=<2^k-1，因?yàn)榻Y(jié)點(diǎn)數(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個(gè)節(jié)點(diǎn)的完全二叉樹的節(jié)點(diǎn)按層次序編號(hào)，對(duì)任一層的節(jié)點(diǎn)i（1<=i<=n）有：

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

三、特殊的二叉樹及其特點(diǎn)

1、斜樹

所有的結(jié)點(diǎn)都只有左子樹（左斜樹），或者只有右子樹（右斜樹）。這就是斜樹，應(yīng)用較少。

2、滿二叉樹

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

根據(jù)滿二叉樹的定義，得到其特點(diǎn)為：

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

3、完全二叉樹

對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序排號(hào)，如果編號(hào)為i的結(jié)點(diǎn)與同樣深度的滿二叉樹編號(hào)為i結(jié)點(diǎn)在二叉樹中位置完全相同，就是完全二叉樹。滿二叉樹必須是完全二叉樹，反過來不一定成立。

其中關(guān)鍵點(diǎn)是按層序編號(hào)，然后對(duì)應(yīng)查找。

結(jié)合完全二叉樹定義得到其特點(diǎn)：

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

延伸閱讀1：平衡二叉樹

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