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

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

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

＝20

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

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

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

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

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

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

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

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

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

log2

n

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

log2n

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

i/2

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