選擇題-1
算法
算法的基本特性:
- 可行性
- 確定性
- 有窮性
- 擁有足夠的情報(bào)
算法復(fù)雜度:
-
算法的時(shí)間復(fù)雜度
- 算法的時(shí)間復(fù)雜度≠算法程序執(zhí)行的具體時(shí)間
- 和計(jì)算工作量有關(guān)(基本運(yùn)算次數(shù)衡量)
-
算法的空間復(fù)雜度
- 執(zhí)行這個(gè)算法所需要的內(nèi)存空間
- 包括三個(gè)部分 1、輸入數(shù)據(jù)所占的儲存空間论巍;2服球、程序本身所占的儲存空間祟印;算法執(zhí)行過程中所需要的各位空間。
數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的儲存結(jié)構(gòu)
節(jié)點(diǎn):
-
根節(jié)點(diǎn)
數(shù)據(jù)結(jié)構(gòu)中鞭达,沒有前件的節(jié)點(diǎn)
-
葉子節(jié)點(diǎn)(終端節(jié)點(diǎn))
數(shù)據(jù)結(jié)構(gòu)中沒有后件的節(jié)點(diǎn)
-
內(nèi)部節(jié)點(diǎn)
數(shù)據(jù)結(jié)構(gòu)中除了根節(jié)點(diǎn)和終端節(jié)點(diǎn)以外的節(jié)點(diǎn)
二叉樹的度
樹的度:樹中各結(jié)點(diǎn)度的最大值稱為該樹的度
二叉樹中連接節(jié)點(diǎn)與節(jié)點(diǎn)的線就是度沙兰。
有n個(gè)節(jié)點(diǎn)剥纷,就有n-1個(gè)度
節(jié)點(diǎn)數(shù)總是比度要多一個(gè)
結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)成為該結(jié)點(diǎn)的度涮毫。
度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)瞬欧,度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。
一棵樹的結(jié)點(diǎn)除了葉結(jié)點(diǎn)外罢防,其余的結(jié)點(diǎn)都是分支結(jié)點(diǎn)艘虎。
樹的根結(jié)點(diǎn)的層數(shù)為1。
- 滿二叉樹:所有分支結(jié)點(diǎn)都存在左子樹和右子樹咒吐,并且所有葉子結(jié)點(diǎn)都在同一層野建。
- 度為0的節(jié)點(diǎn)數(shù)為度為2的節(jié)點(diǎn)數(shù)加