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

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

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

非空二叉樹只有一個(gè)根結(jié)點(diǎn)；

每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。

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

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

性質(zhì)1：在二叉樹的第K層上，最多有（K1）個(gè)結(jié)點(diǎn)。

性質(zhì)2：濃度為M的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)。

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

性質(zhì)3：在任意一棵二叉樹中度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。

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

滿二叉樹與完全二叉樹

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

滿二叉樹

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

完全二叉樹

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

列確切地說，如果從根結(jié)點(diǎn)起，對(duì)二叉樹的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行邊疆編號(hào)，則深度為m、且有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。

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

由滿二叉樹與完全二叉樹的特點(diǎn)可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。

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

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

性質(zhì)6：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(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)，它沒有父結(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)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。

若2k+1n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(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)系是由指針域來確定的。

鏈?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)證碼