《全國計算機等級考試二級VisualBasic精講》由會員分享，可在線閱讀，更多相關(guān)《全國計算機等級考試二級VisualBasic精講（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

3、699-511=188,511,個,188,個,9,28=256,188/2=94,256-94=162,非葉子節(jié)點的個數(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ā)布的答案有誤，請以下圖為準(zhǔn)！,B,A,D,E,C,F,新穎題型

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

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