專題八-二叉樹(shù)

2019-11-08 03:04:25

字體：大中小

供稿：網(wǎng)友

二叉樹(shù)的深層性質(zhì)

二叉樹(shù)的深層性質(zhì)：性質(zhì)1：在二叉樹(shù)的第i層最多有2^(i-1)個(gè)結(jié)點(diǎn)。（i>=1），第一層最多有1個(gè)，二層2個(gè)......

性質(zhì)二：在深度為k的二叉樹(shù)最多有2^(k)-1個(gè)結(jié)點(diǎn)。（k>=0）性質(zhì)三：對(duì)任何一棵二叉樹(shù)，如果其葉節(jié)點(diǎn)有n0個(gè)，度為2的非葉節(jié)點(diǎn)有n2個(gè)，則有n0=n2+1

小結(jié)：理解和掌握二叉樹(shù)的深層次特性有助于我們?cè)O(shè)計(jì)出更加精巧的算法。

創(chuàng)建二叉樹(shù)

指路法定位結(jié)點(diǎn)（1）指路法通過(guò)根節(jié)點(diǎn)與目標(biāo)結(jié)點(diǎn)的相對(duì)位置進(jìn)行定位（2）指路法可以避開(kāi)二叉樹(shù)遞歸性質(zhì)“線性”定位

（3）用結(jié)構(gòu)體來(lái)定義二叉樹(shù)中的指針域（4）二叉樹(shù)的頭結(jié)點(diǎn)也可以用結(jié)構(gòu)體來(lái)定義

二叉樹(shù)結(jié)構(gòu)實(shí)現(xiàn)

遍歷二叉樹(shù)

什么是遍歷？（1）單鏈表的遍歷是指從第一個(gè)節(jié)點(diǎn)開(kāi)始的（下標(biāo)為0的節(jié)點(diǎn)），按照某種次序依次訪問(wèn)每一個(gè)節(jié)點(diǎn)（2）二叉樹(shù)的遍歷是指從根節(jié)點(diǎn)開(kāi)始，按照某種次序依次訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。