完全二叉樹的計算問題,31.,對一顆,699,個結(jié)點的完全二叉樹，求它共有的非葉子結(jié)點數(shù)？,首先應該理解什么是“完全二叉樹”,完全二叉樹數(shù)學定義：設二叉樹的高度為,h,，若：,除第,h,層外，其它各層的結(jié)點數(shù)都達到最大個數(shù),第,h,層所有的節(jié)點都連續(xù)集中在最左邊,同時成立，則稱此這二叉樹為,完全二叉樹,完全二叉樹的計算問題,完全二叉樹數(shù)學定義：設二叉樹的高度為,h,，若：,除第,h,層外，其它各層的結(jié)點數(shù)都達到最大個數(shù),第,h,層所有的節(jié)點都連續(xù)集中在最左邊,同時成立，則稱此這二叉樹為,完全二叉樹,A,F,B,C,G,I,J,E,A,F,K,B,C,G,I,J,L,E,L,完全二叉樹的計算問題,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ù)為,699-511=188,511,個,188,個,9,28=256,188/2=94,256-94=162,非葉子節(jié)點的個數(shù),=699-188-162=349,由遍歷逆推二叉樹問題,32.,官方教材習題,已知一顆二叉樹的前序遍歷為,ABDEGCFH,，中序遍歷為,DBGEACHF,，則該二叉樹的后序遍歷為（,）,根左右,ABDEGCFH,左根右,DBGEACHF,A,B,C,D,E,F,G,H,由遍歷逆推二叉樹問題,37.,設一顆二叉樹的中序遍歷結(jié)果為,DBEAFC,，前序遍歷結(jié)果為,ABDECF,，則后序遍歷結(jié)果為？,先前資料網(wǎng)上發(fā)布的答案有誤，請以下圖為準！,B,A,D,E,C,F,新穎題型,38.,二叉樹的深度為,k,，且它沒有度為,1,的結(jié)點，則此二叉樹中所含結(jié)點數(shù)至多為,。

明顯滿二叉樹符合題目要求，且滿二叉樹已經(jīng)是一定深度樹中最多結(jié)點的情況所以填,2k-1,本題為官方教材附錄“樣卷”中的一題，難度很小但是，“樣卷”所給答案為,2*k-1,，與我們計算的答案有所出入但事實上，若將題目中“至多”兩字改為“至少”，則答案就恰為,2*k-1,，并且題目將具有一定的難度所以我懷疑，樣卷本來要考查的就是“至少”，而“至多”系筆誤那么，你會計算“至少”么？,新穎題型,38.,二叉樹的深度為,k,，且它沒有度為,1,的結(jié)點，則此二叉樹中所含結(jié)點數(shù),至少,為,新穎題型,補充題,1,：中序遍歷可以記錄多項式的四則運算下面的二叉樹表達的多項式運算之后的結(jié)果是？,*,+,-,5,2,2,4,新穎題型,補充題,2,：若二叉樹中每一個結(jié)點都左右兩顆子樹的深度絕對值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項中，是平衡二叉樹的是？,新穎題型,補充題,2,：若二叉樹中每一個結(jié)點都左右兩顆子樹的深度絕對值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項中，是平衡二叉樹的是？,新穎題型,補充題,2,：若二叉樹中每一個結(jié)點都左右兩顆子樹的深度絕對值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項中，是平衡二叉樹的是？,新穎題型,補充題,2,：若二叉樹中每一個結(jié)點都左右兩顆子樹的深度絕對值之差不超過,1,，則稱此二叉樹為“平衡二叉樹”，則下列選項中，是平衡二叉樹的是？,。