3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))課件

1、3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))1內(nèi)部資料20112011年年3 3月計(jì)算機(jī)等級(jí)考試月計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)培訓(xùn)講義二級(jí)公共基礎(chǔ)知識(shí)培訓(xùn)講義理工大樓理工大樓9159153月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))2二級(jí)Access考試介紹一、考試方式一、考試方式1筆試：90 分鐘，滿分100 分，其中含公共基礎(chǔ)知識(shí)部分30分2上機(jī)操作：90 分鐘，滿分100 分二、筆試題型及分值（根據(jù)考試大綱及往年試題二、筆試題型及分值（根據(jù)考試大綱及往年試題) 1選擇題70 分（每小題2分，共3 5題）2填空題30 分（每空2 分，共15題）三、上機(jī)操作三、上機(jī)操作1基本操作（30 分）

2、2簡(jiǎn)單應(yīng)用（40 分）3綜合應(yīng)用（30 分）3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))3我們的目標(biāo)通過(guò)二級(jí)考試通過(guò)二級(jí)考試3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))4基礎(chǔ)知識(shí)部分：30分設(shè)有10道選擇題和5道填空題 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))5第一章 數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)1.4 棧和隊(duì)列1.5 線性鏈表1.6 樹(shù)與二叉樹(shù)1.7 查找技術(shù)1.8 排序技術(shù)3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))61.6 樹(shù)與二叉樹(shù)1.6.1 樹(shù)的基本概念樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。 在樹(shù)結(jié)構(gòu)中，每

3、一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱樹(shù)的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度。樹(shù)的最大層次稱為樹(shù)的深度。 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))71.6.2 二叉樹(shù)及其基本性質(zhì)二叉樹(shù)的特點(diǎn)：（1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))8二叉樹(shù)的基本性質(zhì)：（1）在二叉樹(shù)的第k層上，最多有2k-1(k1)個(gè)結(jié)點(diǎn)； （2）深度為m

4、的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)； （3）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)； （4）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2n+1,其中l(wèi)og2n表示取log2n的整數(shù)部分； 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))9滿二叉樹(shù) 滿二叉樹(shù)是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k-1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))103月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))113月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))12完全二叉樹(shù) 完全二叉樹(shù)是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少

5、右邊的若干結(jié)點(diǎn)。 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))13滿二叉樹(shù)與完全二叉樹(shù)（5）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1； （6）設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1，2，.n給結(jié)點(diǎn)進(jìn)行編號(hào)（k=1,2.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)（也無(wú)右子結(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)。 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))141.6.

6、3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 對(duì)于滿二叉樹(shù)與完全二叉樹(shù)可以按層序?qū)有蜻M(jìn)行順序存儲(chǔ)。 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))151.6.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。二叉樹(shù)的遍歷： （1）前序遍歷（DLR），首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)； （2）中序遍歷（LDR），首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)； （3）后序遍歷（LRD）首先遍歷左子樹(shù)，然后訪問(wèn)遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))16 1. 前序遍歷（DLR） 前序遍歷首先訪問(wèn)根結(jié)點(diǎn)然后遍歷左子樹(shù)，

7、最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。即： 若二叉樹(shù)為空則結(jié)束返回，否則： （1）訪問(wèn)根結(jié)點(diǎn) （2）前序遍歷左子樹(shù) （3）前序遍歷右子樹(shù) 注意的是：遍歷左右子樹(shù)時(shí)仍然采用前序遍歷方法。 例：如圖二叉樹(shù)， 則前序遍歷結(jié)果是：A B D E C F 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))17 2. 中序遍歷（LDR） 中序遍歷首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。即： 若二叉樹(shù)為空則結(jié)束返回，否則： （1）中序遍歷左子樹(shù) （2）訪問(wèn)根結(jié)點(diǎn) （3）中序遍歷右子樹(shù)。 注意

8、的是：遍歷左右子樹(shù)時(shí)仍然采用中序遍歷方法。 例：如圖二叉樹(shù)， 則中序遍歷結(jié)果是：D B E A F C 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))183. 后序遍歷（LRD）后序遍歷首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。即： 若二叉樹(shù)為空則結(jié)束返回，否則： （1）后序遍歷左子樹(shù)， （2）后序遍歷右子樹(shù) （3）最后訪問(wèn)根結(jié)點(diǎn)。 注意的是：遍歷左右子樹(shù)時(shí)仍然采用后序遍歷方法。 例：如圖二叉樹(shù)， 3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))19例:A B D E C F G D B E A F G C D E B G

9、F C A前序遍歷：中序遍歷：后序遍歷：3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))20歷年考題【2005年4月填空第1題】（1）某二叉樹(shù)中度為2的結(jié)點(diǎn)有18個(gè)，則該二叉樹(shù)中有_個(gè)葉子結(jié)點(diǎn)?！?005年4月填空第4題】（4）一棵二叉樹(shù)第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為_(kāi)個(gè)?！?007年4月選擇第7題】（7）某二叉樹(shù)中有n個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為A）n+1 B）n-1 C）2n D）n/23月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))21歷年考題【2007年4月填空第1題】（1）在深度為7的滿二叉樹(shù)中，度為2的結(jié)點(diǎn)個(gè)數(shù)為 。 【2007年9月選擇第8題】（8）一棵二叉樹(shù)中共有

10、70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為A)219 B)221 C)229 D)231【2008年4月填空第2題】（2）深度為5的滿二叉樹(shù)有 個(gè)葉子結(jié)點(diǎn)。3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))22【2006年4月選擇第6題】（6）對(duì)下列二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCA3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))23【2007年4月選擇第6題】（6）對(duì)下列二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為A）DYBEAFCZX B）YDEBFZXCAC）ABDYECFXZ D）ABCDEFXYZ3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))24【2007年9月填空第4題】（4）對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果為 【4】 。3月二級(jí)公共基礎(chǔ)知識(shí)講義(1.6樹(shù)與二叉樹(shù))252008.9(1)對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是 【1】 。3月二級(jí)公共基礎(chǔ)知識(shí)講義(1