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

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

　　樹

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

　　二叉樹性質(zhì)：

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

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

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

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

　　二叉樹存儲形式：

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

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

　　二叉樹遍歷：

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

　　如：前+中

　　前：GDAFEMHZ中：ADEFGHMZ

　　步驟：根據(jù)前知道root是G，根據(jù)中知道左子樹是ADEF,右子樹是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é)束，樹的層次遍歷為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

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

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

　　同理二叉樹轉(zhuǎn)回森林和樹：類似

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