山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-什么是二叉樹(shù) - 常識(shí)判斷
山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-什么是二叉樹(shù)減小字體增大字體山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-什么是二叉樹(shù)
二叉樹(shù)是一種很有用的非線性結(jié)構(gòu)。二就樹(shù)具有以下兩個(gè)特點(diǎn):
非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn);
每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。
由以上特點(diǎn)可以看出,在二叉樹(shù)中,每一個(gè)結(jié)點(diǎn)的度最大為2,即所有子樹(shù)(左子樹(shù)或右子樹(shù))也均為二叉樹(shù),而樹(shù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外,二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)的子樹(shù)被明顯地分為左子樹(shù)與右子樹(shù)??梢詻](méi)有其中的一個(gè),也可以全沒(méi)有。
二叉樹(shù)的基本性質(zhì)
性質(zhì)1:在二叉樹(shù)的第K層上,最多有(K1)個(gè)結(jié)點(diǎn)。
性質(zhì)2:濃度為M的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)。
深度為m的二叉樹(shù)是指二叉樹(shù)共有m層。
性質(zhì)3:在任意一棵二叉樹(shù)中度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。
性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其深度至少為[log2n]+1,其中[log2n]表示取的整數(shù)部分。
滿二叉樹(shù)與完全二叉樹(shù)
滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù)。
滿二叉樹(shù)
所謂滿二叉樹(shù)是指這樣的一種二叉樹(shù);除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說(shuō),在滿二叉樹(shù)中,每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值,即在滿二叉樹(shù)的第K層上有2K-1個(gè)結(jié)點(diǎn),且深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。
完全二叉樹(shù)
所謂完全二叉樹(shù)是指這樣的二叉樹(shù),除最后一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)的最大值;在最后一層上只缺少右邊的若干結(jié)點(diǎn)。
列確切地說(shuō),如果從根結(jié)點(diǎn)起,對(duì)二叉樹(shù)的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行邊疆編號(hào),則深度為m、且有n個(gè)結(jié)點(diǎn)的二叉樹(shù),當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí),稱之為完全二叉樹(shù)。
對(duì)于完全二叉樹(shù)來(lái)說(shuō),葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn);對(duì)于任何一個(gè)結(jié)點(diǎn),若其右分支下的子孫結(jié)點(diǎn)的最大層次為p,則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜,或?yàn)閜+1。
由滿二叉樹(shù)與完全二叉樹(shù)的特點(diǎn)可以看出,滿二叉樹(shù)也是完全二叉樹(shù),而完全二叉樹(shù)一般不是滿二叉樹(shù)。
完全二叉樹(shù)還具有以下兩個(gè)性質(zhì):
性質(zhì)5:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1。
性質(zhì)6:設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始,按層序(每一層從左到右)用自然數(shù)1,2,,n給結(jié)點(diǎn)進(jìn)行編號(hào),則對(duì)于編號(hào)為k(k=1,2,n)的結(jié)點(diǎn)有以下結(jié)論:
若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn),它沒(méi)有父結(jié)點(diǎn);若k1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。
若2kn,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k;否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)(顯然也沒(méi)有右子結(jié)點(diǎn))。
若2k+1n,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1;否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。
用戶名:!查看更多評(píng)論
分值:100分55分1分
內(nèi)容:!
通知管理員驗(yàn)證碼:點(diǎn)擊獲取驗(yàn)證碼
山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-線性鏈表 - 常識(shí)判斷
山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-線性鏈表減小字體增大字體山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-線性鏈表
數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元,這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn),簡(jiǎn)稱結(jié)點(diǎn)。
結(jié)點(diǎn)由兩部分組成:(1)用于存儲(chǔ)數(shù)據(jù)元素值,稱為數(shù)據(jù)域;(2)用于存放指針,稱為指針域,用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。
在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù),各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。
鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu),也可用于表示非線性結(jié)構(gòu)。
線性鏈表,HEAD稱為頭指針,HEAD=NULL(或0)稱為空表,如果是兩指針:左指針(Llink)指向前件結(jié)點(diǎn),右指針(Rlink)指向后件結(jié)點(diǎn)。
線性鏈表的基本運(yùn)算:查找、插入、刪除。
用戶名:!查看更多評(píng)論
分值:100分55分1分
內(nèi)容:!
通知管理員驗(yàn)證碼:點(diǎn)擊獲取驗(yàn)證碼