山東軍隊文職招聘考試網(wǎng)計算機常識-什么是二叉樹 - 常識判斷

山東軍隊文職招聘考試網(wǎng)計算機常識-什么是二叉樹減小字體增大字體山東軍隊文職招聘考試網(wǎng)計算機常識-什么是二叉樹

二叉樹是一種很有用的非線性結(jié)構(gòu)。二就樹具有以下兩個特點:

非空二叉樹只有一個根結(jié)點;

每一個結(jié)點最多有兩棵子樹,且分別稱為該結(jié)點的左子樹與右子樹。

由以上特點可以看出,在二叉樹中,每一個結(jié)點的度最大為2,即所有子樹(左子樹或右子樹)也均為二叉樹,而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。另外,二叉樹中的每一個結(jié)點的子樹被明顯地分為左子樹與右子樹??梢詻]有其中的一個,也可以全沒有。

二叉樹的基本性質(zhì)

性質(zhì)1:在二叉樹的第K層上,最多有(K1)個結(jié)點。

性質(zhì)2:濃度為M的二叉樹最多有2m-1個結(jié)點。

深度為m的二叉樹是指二叉樹共有m層。

性質(zhì)3:在任意一棵二叉樹中度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。

性質(zhì)4:具有n個結(jié)點的二叉樹,其深度至少為[log2n]+1,其中[log2n]表示取的整數(shù)部分。

滿二叉樹與完全二叉樹

滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。

滿二叉樹

所謂滿二叉樹是指這樣的一種二叉樹;除最后一層外,每一層上的所有結(jié)點都有兩個子結(jié)點。這就是說,在滿二叉樹中,每一層上的結(jié)點數(shù)都達到最大值,即在滿二叉樹的第K層上有2K-1個結(jié)點,且深度為m的滿二叉樹有2m-1個結(jié)點。

完全二叉樹

所謂完全二叉樹是指這樣的二叉樹,除最后一層外,每一層上的結(jié)點數(shù)均達的最大值;在最后一層上只缺少右邊的若干結(jié)點。

列確切地說,如果從根結(jié)點起,對二叉樹的結(jié)點自上而下、自左至右用自然數(shù)進行邊疆編號,則深度為m、且有n個結(jié)點的二叉樹,當且僅當其每一個結(jié)點都與深度為m的滿二叉樹中編號從1到n的結(jié)點一一對應時,稱之為完全二叉樹。

對于完全二叉樹來說,葉子結(jié)點只可能在層次最大的兩層上出現(xiàn);對于任何一個結(jié)點,若其右分支下的子孫結(jié)點的最大層次為p,則其左分支下的子孫結(jié)點的最大層次或為p,或為p+1。

由滿二叉樹與完全二叉樹的特點可以看出,滿二叉樹也是完全二叉樹,而完全二叉樹一般不是滿二叉樹。

完全二叉樹還具有以下兩個性質(zhì):

性質(zhì)5:具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。

性質(zhì)6:設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始,按層序(每一層從左到右)用自然數(shù)1,2,,n給結(jié)點進行編號,則對于編號為k(k=1,2,n)的結(jié)點有以下結(jié)論:

若k=1,則該結(jié)點為根結(jié)點,它沒有父結(jié)點;若k1,則該結(jié)點的父結(jié)點編號為INT(k/2)。

若2kn,則編號為k的結(jié)點的左子結(jié)點編號為2k;否則該結(jié)點無左子結(jié)點(顯然也沒有右子結(jié)點)。

若2k+1n,則編號為k的結(jié)點的右子結(jié)點編號為2k+1;否則該結(jié)點無右子結(jié)點。

用戶名:!查看更多評論

分值:100分55分1分

內(nèi)容:!

通知管理員驗證碼:點擊獲取驗證碼

軍隊文職招聘行測基礎(chǔ)知識-計算機發(fā)展簡史-第一代(1946~1957年),電子管計算機 - 常識判斷

軍隊文職招聘行測基礎(chǔ)知識-計算機發(fā)展簡史-第一代(1946~1957年),電子管計算機減小字體增大字體軍隊文職招聘行測基礎(chǔ)知識-計算機發(fā)展簡史-第一代(1946~1957年),電子管計算機它是一臺電子數(shù)字積分計算機,取名為ENIAC。這臺計算機是個龐然大物,共用了18000多個電子管、1500個繼電器,重達30噸,占地170平方米,每小時耗電140千瓦,計算速度為每秒5000次加法運算。盡管它的功能遠不如今天的計算機,但ENIAC作為計算機大家族的鼻祖,開辟了人類科學技術(shù)領(lǐng)域的先河,使信息處理技術(shù)進入了一個嶄新的時代。其主要特征如下:

(1)電子管元件,體積龐大、耗電量高、可靠性差、維護困難。

(2)運算速度慢,一般為每秒鐘1千次到1萬次。

(3)使用機器語言,沒有系統(tǒng)軟件。

(4)采用磁鼓、小磁芯作為存儲器,存儲空間有限。

(5)輸入/輸出設(shè)備簡單,采用穿孔紙帶或卡片。

(6)主要用于科學計算。

用戶名:!查看更多評論

分值:100分55分1分

內(nèi)容:!

通知管理員驗證碼:點擊獲取驗證碼