,完全二叉樹(shù)的計(jì)算問(wèn)題,31.,對(duì)一顆,699,個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，求它共有的非葉子結(jié)點(diǎn)數(shù)？,首先應(yīng)該理解什么是“完全二叉樹(shù)”,完全二叉樹(shù)數(shù)學(xué)定義：設(shè)二叉樹(shù)的高度為,h,，若：,除第,h,層外，其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù),第,h,層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊,同時(shí)成立，則稱此這二叉樹(shù)為,完全二叉樹(shù),完全二叉樹(shù)的計(jì)算問(wèn)題,完全二叉樹(shù)數(shù)學(xué)定義：設(shè)二叉樹(shù)的高度為,h,，若：,除第,h,層外，其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù),第,h,層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊,同時(shí)成立，則稱此這二叉樹(shù)為,完全二叉樹(shù),A,F,B,C,G,I,J,E,A,F,K,B,C,G,I,J,L,E,L,完全二叉樹(shù)的計(jì)算問(wèn)題,31.,對(duì)一顆,699,個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，求它共有的非葉子結(jié)點(diǎn)數(shù)？,解：首先計(jì)算此完全二叉樹(shù)的層數(shù)。,我們知道，,9,層的滿二叉樹(shù)一共有,29-1=511,個(gè)結(jié)點(diǎn)，而,10,層滿二叉樹(shù)一共有,210-1=1023,個(gè)結(jié)點(diǎn)。,因?yàn)?511 699 1023,所以可以知道此完全二叉樹(shù)一共有,10,層，且前,9,層成滿結(jié)點(diǎn)狀態(tài)。,前,9,層共有的結(jié)點(diǎn)數(shù),=29-1=511,個(gè)，所以第,10,層的結(jié)點(diǎn)數(shù)為,699-511=148,完全二叉樹(shù)的計(jì)算問(wèn)題,31.,對(duì)一顆,699,個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，求它共有的非葉子結(jié)點(diǎn)數(shù)？,前,9,層共有的結(jié)點(diǎn)數(shù),=29-1=511,個(gè)，所以第,10,層的結(jié)點(diǎn)數(shù)為,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,由遍歷逆推二叉樹(shù)問(wèn)題,32.,官方教材習(xí)題,已知一顆二叉樹(shù)的前序遍歷為,ABDEGCFH,，中序遍歷為,DBGEACHF,，則該二叉樹(shù)的后序遍歷為（,）,根左右,ABDEGCFH,左根右,DBGEACHF,A,B,C,D,E,F,G,H,由遍歷逆推二叉樹(shù)問(wèn)題,37.,設(shè)一顆二叉樹(shù)的中序遍歷結(jié)果為,DBEAFC,，前序遍歷結(jié)果為,ABDECF,，則后序遍歷結(jié)果為？,先前資料網(wǎng)上發(fā)布的答案有誤，請(qǐng)以下圖為準(zhǔn)！,B,A,D,E,C,F,新穎題型,38.,二叉樹(shù)的深度為,k,，且它沒(méi)有度為,1,的結(jié)點(diǎn)，則此二叉樹(shù)中所含結(jié)點(diǎn)數(shù)至多為,。,明顯滿二叉樹(shù)符合題目要求，且滿二叉樹(shù)已經(jīng)是一定深度樹(shù)中最多結(jié)點(diǎn)的情況。所以填,2k-1,本題為官方教材附錄“樣卷”中的一題，難度很小。但是，“樣卷”所給答案為,2*k-1,，與我們計(jì)算的答案有所出入。,但事實(shí)上，若將題目中“至多”兩字改為“至少”，則答案就恰為,2*k-1,，并且題目將具有一定的難度。所以我懷疑，樣卷本來(lái)要考查的就是“至少”，而“至多”系筆誤。那么，你會(huì)計(jì)算“至少”么？,新穎題型,38.,二叉樹(shù)的深度為,k,，且它沒(méi)有度為,1,的結(jié)點(diǎn)，則此二叉樹(shù)中所含結(jié)點(diǎn)數(shù),至少,為,。,新穎題型,補(bǔ)充題,1,：中序遍歷可以記錄多項(xiàng)式的四則運(yùn)算。下面的二叉樹(shù)表達(dá)的多項(xiàng)式運(yùn)算之后的結(jié)果是？,*,+,-,5,2,2,4,新穎題型,補(bǔ)充題,2,：若二叉樹(shù)中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹(shù)的深度絕對(duì)值之差不超過(guò),1,，則稱此二叉樹(shù)為“平衡二叉樹(shù)”，則下列選項(xiàng)中，是平衡二叉樹(shù)的是？,新穎題型,補(bǔ)充題,2,：若二叉樹(shù)中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹(shù)的深度絕對(duì)值之差不超過(guò),1,，則稱此二叉樹(shù)為“平衡二叉樹(shù)”，則下列選項(xiàng)中，是平衡二叉樹(shù)的是？,新穎題型,補(bǔ)充題,2,：若二叉樹(shù)中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹(shù)的深度絕對(duì)值之差不超過(guò),1,，則稱此二叉樹(shù)為“平衡二叉樹(shù)”，則下列選項(xiàng)中，是平衡二叉樹(shù)的是？,新穎題型,補(bǔ)充題,2,：若二叉樹(shù)中每一個(gè)結(jié)點(diǎn)都左右兩顆子樹(shù)的深度絕對(duì)值之差不超過(guò),1,，則稱此二叉樹(shù)為“平衡二叉樹(shù)”，則下列選項(xiàng)中，是平衡二叉樹(shù)的是？,