1、基本概念

二叉樹（Binary Tree）是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。

二叉樹的特點(diǎn)：

二叉樹不存在度大于2的結(jié)點(diǎn)。

二叉樹的子樹有左右之分，次序不能顛倒。

如下圖中，樹1和樹2是同一棵樹，但它們是不同的二叉樹。

二叉樹

1）、斜樹

所有的結(jié)點(diǎn)都只有左子樹的二叉樹叫左斜樹。所有的結(jié)點(diǎn)都只有右子樹的二叉樹叫右斜樹。這兩者統(tǒng)稱為斜樹。

斜樹每一層只有一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的個(gè)數(shù)與二叉樹的深度相同。其實(shí)斜樹就是線性表結(jié)構(gòu)。

2）、滿二叉樹

在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹具有如下特點(diǎn)：

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

非葉子結(jié)點(diǎn)的度一定是2

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

3）、完全二叉樹

若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹。

完全二叉樹的特點(diǎn)：

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

最下層葉子在左部并且連續(xù)

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

4）、平衡二叉樹

平衡二叉樹又被稱為AVL樹（區(qū)別于AVL算法），它是一棵二叉排序樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹

2、二叉樹的性質(zhì)

在二叉樹的第i層上至多有2^i-1^個(gè)結(jié)點(diǎn)（i>=1）。

深度為k的二叉樹至多有2^k^-1個(gè)結(jié)點(diǎn)（k>=1）。

對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)個(gè)數(shù)為n~0~，度為2的結(jié)點(diǎn)數(shù)為n~2~，則n~0~ = n~2~ + 1。

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為「log~2~n」+ 1（「x」表示不大于x的最大整數(shù)）。

如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號（從第一層到第「log~2~n」+ 1層，每層從左到右），對任一結(jié)點(diǎn)i（1≤i≤n）有：

若i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如i>1，則其雙親是結(jié)點(diǎn)「i/2」。

如2i>n，則結(jié)點(diǎn)i無左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子是結(jié)點(diǎn)2i。

若2i+1>n，則結(jié)點(diǎn)i無右孩子；否則其右孩子是結(jié)點(diǎn)2i+1。

3、二叉樹的存儲結(jié)構(gòu)和遍歷

二叉樹是一種特殊的樹，它的存儲結(jié)構(gòu)相對于前面談到的一般樹的存儲結(jié)構(gòu)要簡單一些。

①順序存儲結(jié)構(gòu)

②鏈?zhǔn)酱鎯Y(jié)構(gòu)