山東軍隊(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ù)，且分別稱(chēng)為該結(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ù)部分。
滿(mǎn)二叉樹(shù)與完全二叉樹(shù)
滿(mǎn)二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù)。
滿(mǎn)二叉樹(shù)
所謂滿(mǎn)二叉樹(shù)是指這樣的一種二叉樹(shù)；除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說(shuō)，在滿(mǎn)二叉樹(shù)中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿(mǎn)二叉樹(shù)的第K層上有2K-1個(gè)結(jié)點(diǎn)，且深度為m的滿(mǎn)二叉樹(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的滿(mǎn)二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)之為完全二叉樹(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。
由滿(mǎn)二叉樹(shù)與完全二叉樹(shù)的特點(diǎn)可以看出，滿(mǎn)二叉樹(shù)也是完全二叉樹(shù)，而完全二叉樹(shù)一般不是滿(mǎn)二叉樹(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)。
用戶(hù)名：！查看更多評(píng)論
分值：100分55分1分
內(nèi)容：！
通知管理員驗(yàn)證碼：點(diǎn)擊獲取驗(yàn)證碼
軍隊(duì)文職招聘行測(cè)基礎(chǔ)知識(shí)-計(jì)算機(jī)發(fā)展簡(jiǎn)史-第一代（1946～1957年），電子管計(jì)算機(jī) - 常識(shí)判斷
軍隊(duì)文職招聘行測(cè)基礎(chǔ)知識(shí)-計(jì)算機(jī)發(fā)展簡(jiǎn)史-第一代（1946～1957年），電子管計(jì)算機(jī)減小字體增大字體軍隊(duì)文職招聘行測(cè)基礎(chǔ)知識(shí)-計(jì)算機(jī)發(fā)展簡(jiǎn)史-第一代（1946～1957年），電子管計(jì)算機(jī)它是一臺(tái)電子數(shù)字積分計(jì)算機(jī)，取名為ENIAC。這臺(tái)計(jì)算機(jī)是個(gè)龐然大物，共用了18000多個(gè)電子管、1500個(gè)繼電器，重達(dá)30噸，占地170平方米，每小時(shí)耗電140千瓦，計(jì)算速度為每秒5000次加法運(yùn)算。盡管它的功能遠(yuǎn)不如今天的計(jì)算機(jī)，但ENIAC作為計(jì)算機(jī)大家族的鼻祖，開(kāi)辟了人類(lèi)科學(xué)技術(shù)領(lǐng)域的先河，使信息處理技術(shù)進(jìn)入了一個(gè)嶄新的時(shí)代。其主要特征如下：
（1）電子管元件，體積龐大、耗電量高、可靠性差、維護(hù)困難。
（2）運(yùn)算速度慢，一般為每秒鐘1千次到1萬(wàn)次。
（3）使用機(jī)器語(yǔ)言，沒(méi)有系統(tǒng)軟件。
（4）采用磁鼓、小磁芯作為存儲(chǔ)器，存儲(chǔ)空間有限。
（5）輸入/輸出設(shè)備簡(jiǎn)單，采用穿孔紙帶或卡片。
（6）主要用于科學(xué)計(jì)算。
用戶(hù)名：！查看更多評(píng)論
分值：100分55分1分
內(nèi)容：！
通知管理員驗(yàn)證碼：點(diǎn)擊獲取驗(yàn)證碼
