2011考研備考數(shù)據(jù)結(jié)構(gòu)之圖_跨考網(wǎng)

復(fù)習(xí)緊張，焦頭爛額？逆風(fēng)輕襲，來(lái)跨考秋季集訓(xùn)營(yíng)，幫你尋方法，定方案！ 了解一下>>

復(fù)習(xí)策略：樹(shù)是數(shù)據(jù)結(jié)構(gòu)最重要的部分，它的內(nèi)容紛繁而復(fù)雜，但又尤為重要，是復(fù)習(xí)的重中之重。無(wú)論是?？歼€是統(tǒng)考，樹(shù)無(wú)疑都是出題的重點(diǎn)，如樹(shù)的質(zhì)性，無(wú)論那套試卷，都會(huì)有這么一道必考的選擇題。對(duì)于樹(shù)的復(fù)習(xí)方法，同學(xué)們要重點(diǎn)掌握樹(shù)的遍歷，樹(shù)的任何操作，其實(shí)都是以遍歷為基礎(chǔ)，稍加改動(dòng)visit函數(shù)而已。
　　
　　09年真題分值比例：選擇題4道（4*2=8分） 17.8%
　　
　?。ㄒ唬?shù)的基本概念
　　
　　樹(shù)：n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí)，稱為空樹(shù)；任意一棵非空樹(shù)滿足以下條件：
　　
　?。?）有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；
　　
　?。?）當(dāng)n＞1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的有限集合T1,T2,…,Tm，其中每個(gè)集合又是一棵樹(shù)，并稱為這個(gè)根結(jié)點(diǎn)的子樹(shù)。
　　
　　結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。
　　樹(shù)的度：樹(shù)中各結(jié)點(diǎn)度的最大值。
　　葉子：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。
　　分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。
　　孩子、雙親、兄弟、祖先、子孫、堂兄弟的概念參考家譜形象記憶
　　層次：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。
　　深度（高度）：樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。
　　層序編號(hào)：將樹(shù)中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開(kāi)始的連續(xù)自然數(shù)。
　　有序樹(shù)、無(wú)序樹(shù)：如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，稱這棵樹(shù)為有序樹(shù)；反之，稱為無(wú)序樹(shù)。
　　森林：m（m≥0）棵互不相交的樹(shù)的集合。