2022考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱：樹(shù)

　　計(jì)算機(jī)的競(jìng)爭(zhēng)度逐年加大，報(bào)考學(xué)生越來(lái)越多，對(duì)于打算報(bào)考2022考研計(jì)算機(jī)的考生們來(lái)說(shuō)復(fù)習(xí)是難點(diǎn)，大家復(fù)習(xí)也需要講究方法，掌握一定的技巧。下面小編整理了2022考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)：樹(shù)，供大家參考。

　　樹(shù)

　　層次：根為第一層，最大層為樹(shù)的高度，深度為根到該節(jié)點(diǎn)的路徑長(zhǎng)度;高度為葉節(jié)點(diǎn)到該節(jié)點(diǎn)最大路徑

　　二叉樹(shù)性質(zhì)：

　　1，二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)最多為2i-1(i≥1)。

　　2，深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)(k≥1)

　　3，在任意-棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則no=n2+1

　　4，具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為：log2[n](向下)+1或log2[n+1](向上)

　　二叉樹(shù)存儲(chǔ)形式：

　　1，順序存儲(chǔ)：第i個(gè)結(jié)點(diǎn)的孩子是2i,2i+1(完全二叉樹(shù)適用，如果該樹(shù)不是完全二叉樹(shù)，需要添加空節(jié)點(diǎn)構(gòu)成完全二叉樹(shù))

　　2，二叉鏈表結(jié)構(gòu)：左右指針，中間數(shù)據(jù)|left|data|right|

　　二叉樹(shù)遍歷：

　　遍歷是樹(shù)進(jìn)行其他運(yùn)算的基礎(chǔ)，前+中，中+后，層次+中(因?yàn)榍昂罂梢酝瞥龈Y(jié)點(diǎn)，而中可以推左右)使用遞歸思想來(lái)推樹(shù)的結(jié)構(gòu)能夠快些

　　如：前+中

　　前：GDAFEMHZ中：ADEFGHMZ

　　步驟：根據(jù)前知道root是G，根據(jù)中知道左子樹(shù)是ADEF,右子樹(shù)是HMZ

　　分析leftTree,由前知道root是D，soleftTreeis:A,andrightTreeis:EF

　　分析leftTreeA,結(jié)束，分析rightTree,From前知道root是F，F(xiàn)rom中知leftTreeisE

　　分析rigthTreeHMZ,From前知rootisM,From中知leftTreeisH,andrightTreeisZ

　　遍歷結(jié)束，樹(shù)的層次遍歷為GDMAFHZE

　　如：中+后

　　中：ADEFGHMZ后：AEFDHZMG

　　步驟：From后，知道root是G，F(xiàn)rom中知leftTreeisADEF,rightTreeisHMZ;

　　分析leftTree:From后知rootisD,From中l(wèi)eftTreeisA,rightTreeisEF;

　　分析rightTreeEF;From后知：rootisF,From中l(wèi)eftTreeisE;

　　分析rightTreeHMZ;From后知rootisM，F(xiàn)rom中l(wèi)eftTreeisH，rightTreeisZ;

　　遍歷結(jié)束，層次遍歷為：GDMAFHZE

　　線索二叉樹(shù)：左右標(biāo)簽為0，表示左右指針指向左右孩子節(jié)點(diǎn)，若為1，指向其左指向前驅(qū)，右指向后繼(方便前，中，后遍歷)

　　樹(shù)轉(zhuǎn)二叉樹(shù)：二叉樹(shù)左子樹(shù)為樹(shù)的子節(jié)點(diǎn)，右子樹(shù)為兄弟，單個(gè)樹(shù)即只有左側(cè)，同樣森林可以是左右子樹(shù)的二叉樹(shù)

　　同理二叉樹(shù)轉(zhuǎn)回森林和樹(shù)：類(lèi)似

　　(注：本文來(lái)自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系刪除)