數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 5.2 二叉樹

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計二叉樹的概念二叉樹的性質(zhì)二叉樹的存儲二叉樹的遍歷5.2二叉樹定義二叉樹是節(jié)點的有限集合或者是空樹或者由一個根節(jié)點和兩棵二叉子樹構(gòu)成左子樹，右子樹子樹不相交特點每個節(jié)點至多有二棵子樹不存在度大于2的節(jié)點子樹有左、右之分，次序不能任意顛倒二叉樹二叉樹的五種形態(tài)空二叉樹右子樹為空的二叉樹左子樹非空的二叉樹僅有根節(jié)點的二叉樹左右子樹均非空的二叉樹深度為k的滿二叉樹，有2k-1個節(jié)點2k-1是深度為K的二叉樹所具有的最大節(jié)點個數(shù)滿二叉樹123114589121367101415特點每層上的節(jié)點數(shù)都達(dá)到最大值只有度為0的節(jié)點和度為2的節(jié)點每個節(jié)點均有兩棵高度相同的子樹葉子節(jié)點都在樹的最下面一層上葉子節(jié)點只出現(xiàn)在最低兩層上對任意節(jié)點，若其右分支下的子孫最大層次為L，則其左分支下的子孫的最大層次為L或L+1除最低層外，每一層上的節(jié)點數(shù)均達(dá)到最大值；在最低層上只缺少右邊的若干節(jié)點(也可不缺)。完全二叉樹123114589121367101415滿二叉樹完全二叉樹123114589126710性質(zhì)1：在二叉樹第i層上至多有2i-1

個節(jié)點(i≥1)證明：當(dāng)i=1時，只有一個根節(jié)點。顯然，2i-1

＝20

＝１是對的假設(shè)對所有的j(1≤j﹤i)，命題成立即第j層上至多有2j-1

個節(jié)點那么可以證明j=i時命題成立歸納假設(shè)：第i-1層上至多有2i-2

個節(jié)點。由于二叉樹的每個節(jié)點的度至多為2，故在第i層上的最大節(jié)點數(shù)為第i-1層上的最大節(jié)點數(shù)的2倍即2*2i-2＝2i-1。二叉樹的性質(zhì)123114589121367101415性質(zhì)2：深度為k的二叉樹至多有2k-１個節(jié)點(k≥1)證明：

由性質(zhì)１可見，深度為k的二叉樹的最大節(jié)點數(shù)為：二叉樹的性質(zhì)123114589121367101415性質(zhì)3：對任意二叉樹T，如果其終端節(jié)點數(shù)為n0

，度為2的節(jié)點數(shù)為n2,則n0=n2+1。證明：二叉樹中節(jié)點總數(shù)為：

n=n0+n1+n2 (5-1)二叉樹的分支數(shù)為：

n1+2*n2 (5-2)因此，節(jié)點總數(shù)為：

n=n1+2*n2+1由(5-1)、(5-2)兩式可得：

n0=n2+1二叉樹的性質(zhì)1234567性質(zhì)4：具有n個節(jié)點的完全二叉樹的深度為

log2

n

+1證明：假設(shè)深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有于是因為k是整數(shù),所以二叉樹的性質(zhì)性質(zhì)5：對一棵有n個節(jié)點的完全二叉樹的節(jié)點按層序號編號(從第1層到

log2n

+1層，每層從左到右)，則對任一節(jié)點i(1≤i≤n)，有：如果i=1，則節(jié)點i是根節(jié)點，無雙親，否則，其雙親節(jié)點為：

i/2

如果2i>n，則節(jié)點i無左孩子(節(jié)點i為葉子節(jié)點);否則其左孩子是節(jié)點2i如果2i+1>n，則節(jié)點i無右孩子;否則其右孩子是節(jié)點2i+1二叉樹的性質(zhì)123114589126710順序存儲將任意二叉樹“修補(bǔ)”成完全二叉樹利用順序表對數(shù)據(jù)元素進(jìn)行存儲原二叉樹中空缺的節(jié)點在數(shù)組中相應(yīng)單元置空二叉樹的存儲123φ5φ7φφ10鏈?zhǔn)酱鎯?二叉鏈表節(jié)點包含3個域：數(shù)據(jù)域和指向左、右子樹的指針域二叉樹的存儲LChildDataRChild遍歷（taversal）按一定的規(guī)則和次序走遍二叉樹的所有節(jié)點使每個節(jié)點都被訪問一次，且只被訪問一次訪問對節(jié)點進(jìn)行各種操作遍歷二叉樹的目的遍歷是對數(shù)據(jù)進(jìn)行操作的基礎(chǔ)得到二叉樹中各節(jié)點的一種線性順序使非線性的二叉樹線性化，簡化有關(guān)的運(yùn)算和處理二叉樹的遍歷若二叉樹為空，則返回；否則依次執(zhí)行以下操作：訪問根節(jié)點；按先序遍歷左子樹；按先序遍歷右子樹；返回。先序遍歷先序遍歷序列：ABDECACBDEACBDE若二叉樹為空，則返回；否則依次執(zhí)行以下操作：按中序遍歷左子樹；訪問根節(jié)點；按中序遍歷右子樹；返回。中序遍歷中序遍歷序列：DBEACACBDEACBDE若二叉樹為空，則返回；否則依次執(zhí)行以下操作：按后序遍歷左子樹；