《全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)VisualBasic精講》由會(huì)員分享，可在線閱讀，更多相關(guān)《全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)VisualBasic精講（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,完全二叉樹的計(jì)算問題,31.,對(duì)一顆,699,個(gè)結(jié)點(diǎn)的完全二叉樹，求它共有的非葉子結(jié)點(diǎn)數(shù)？,首先應(yīng)該理解什么是“完全二叉樹”,完全二叉樹數(shù)學(xué)定義：設(shè)二叉樹的高度為,h,，若：,除第,h,層外，其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù),第,h,層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊,同時(shí)成立，則稱此這二叉樹為,完全二叉樹,完全二叉樹的計(jì)算問題,完全二叉樹數(shù)學(xué)定義：設(shè)二叉樹的高度為,h,，若：,除第,h,層外，其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù),第,h,層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊,同時(shí)成立，則稱此這二叉樹為,完全二叉樹,A,F,B,C,G,I,J,E,A,F,K,B,C,G,I,J,L,E,L,完全二叉樹的計(jì)算問

2、題,31.,對(duì)一顆,699,個(gè)結(jié)點(diǎn)的完全二叉樹，求它共有的非葉子結(jié)點(diǎn)數(shù)？,解：首先計(jì)算此完全二叉樹的層數(shù)。,我們知道，,9,層的滿二叉樹一共有,29-1=511,個(gè)結(jié)點(diǎn)，而,10,層滿二叉樹一共有,210-1=1023,個(gè)結(jié)點(diǎn)。,因?yàn)?511 699 1023,所以可以知道此完全二叉樹一共有,10,層，且前,9,層成滿結(jié)點(diǎn)狀態(tài)。,前,9,層共有的結(jié)點(diǎn)數(shù),=29-1=511,個(gè)，所以第,10,層的結(jié)點(diǎn)數(shù)為,699-511=148,完全二叉樹的計(jì)算問題,31.,對(duì)一顆,699,個(gè)結(jié)點(diǎn)的完全二叉樹，求它共有的非葉子結(jié)點(diǎn)數(shù)？,前,9,層共有的結(jié)點(diǎn)數(shù),=29-1=511,個(gè)，所以第,10,層的結(jié)點(diǎn)數(shù)為,

3、699-511=188,511,個(gè),188,個(gè),9,28=256,188/2=94,256-94=162,非葉子節(jié)點(diǎn)的個(gè)數(shù),=699-188-162=349,由遍歷逆推二叉樹問題,32.,官方教材習(xí)題,已知一顆二叉樹的前序遍歷為,ABDEGCFH,，中序遍歷為,DBGEACHF,，則該二叉樹的后序遍歷為（,）,根左右,ABDEGCFH,左根右,DBGEACHF,A,B,C,D,E,F,G,H,由遍歷逆推二叉樹問題,37.,設(shè)一顆二叉樹的中序遍歷結(jié)果為,DBEAFC,，前序遍歷結(jié)果為,ABDECF,，則后序遍歷結(jié)果為？,先前資料網(wǎng)上發(fā)布的答案有誤，請(qǐng)以下圖為準(zhǔn)！,B,A,D,E,C,F,新穎題型

4、,38.,二叉樹的深度為,k,，且它沒有度為,1,的結(jié)點(diǎn)，則此二叉樹中所含結(jié)點(diǎn)數(shù)至多為,。,明顯滿二叉樹符合題目要求，且滿二叉樹已經(jīng)是一定深度樹中最多結(jié)點(diǎn)的情況。所以填,2k-1,本題為官方教材附錄“樣卷”中的一題，難度很小。但是，“樣卷”所給答案為,2*k-1,，與我們計(jì)算的答案有所出入。,但事實(shí)上，若將題目中“至多”兩字改為“至少”，則答案就恰為,2*k-1,，并且題目將具有一定的難度。所以我懷疑，樣卷本來要考查的就是“至少”，而“至多”系筆誤。那么，你會(huì)計(jì)算“至少”么？,新穎題型,38.,二叉樹的深度為,k,，且它沒有度為,1,的結(jié)點(diǎn)，則此二叉樹中所含結(jié)點(diǎn)數(shù),至少,為,。,新穎題型,補(bǔ)充

5、題,1,：中序遍歷可以記錄多項(xiàng)式的四則運(yùn)算。下面的二叉樹表達(dá)的多項(xiàng)式運(yùn)算之后的結(jié)果是？,*,+,-,5,2,2,4,新穎題型,補(bǔ)充題,2,：若二叉樹中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹的深度絕對(duì)值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項(xiàng)中，是平衡二叉樹的是？,新穎題型,補(bǔ)充題,2,：若二叉樹中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹的深度絕對(duì)值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項(xiàng)中，是平衡二叉樹的是？,新穎題型,補(bǔ)充題,2,：若二叉樹中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹的深度絕對(duì)值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項(xiàng)中，是平衡二叉樹的是？,新穎題型,補(bǔ)充題,2,：若二叉樹中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹的深度絕對(duì)值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項(xiàng)中，是平衡二叉樹的是？,