一、二叉樹(shù)終端結(jié)點(diǎn)和葉子結(jié)點(diǎn)有區(qū)別嗎
二叉樹(shù)終端結(jié)點(diǎn)和葉子結(jié)點(diǎn)沒(méi)區(qū)別。葉子結(jié)點(diǎn)(leaf, 也稱(chēng)樹(shù)葉或終端結(jié)點(diǎn)), 沒(méi)有子結(jié)點(diǎn),度為0。除了葉子結(jié)點(diǎn)以外的那些非終端的結(jié)點(diǎn)稱(chēng)為內(nèi)部結(jié)點(diǎn) (internal node, 也稱(chēng)分支結(jié)點(diǎn))。
葉子結(jié)點(diǎn)是離散數(shù)學(xué)中的概念。一棵樹(shù)當(dāng)中沒(méi)有子結(jié)點(diǎn)(即度為0)的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn),簡(jiǎn)稱(chēng)“葉子”。 葉子是指度為0的結(jié)點(diǎn),又稱(chēng)為終端結(jié)點(diǎn)。
例題:
一棵樹(shù)度為4,其中度為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1,則這棵樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)為多少?
解:因?yàn)槿我豢脴?shù)中,結(jié)點(diǎn)總數(shù)=度數(shù)+1,所以:
n0+4+2+1+1 = (n0*0 + 1*4 + 2*2 + 3*1 + 4*1)+1
則:n0=8
其中:n0表示葉子結(jié)點(diǎn)。
延伸閱讀:
二、樹(shù)和二叉樹(shù)知識(shí)整理
1、樹(shù)型結(jié)構(gòu)是一類(lèi)非常重要的非線性結(jié)構(gòu),
樹(shù)型結(jié)構(gòu)為:分支結(jié)構(gòu)、一對(duì)多、層次結(jié)構(gòu)
2、樹(shù)(tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集合T,若n=0時(shí)稱(chēng)為空樹(shù),否則:
(1)有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根(root)結(jié)點(diǎn);根是入口
(2)若n>1時(shí),其余的結(jié)點(diǎn)被分為m(m>0)個(gè)互不相交的子集T1,T2,T3..,其中每個(gè)子集本身又是一棵樹(shù),稱(chēng)其為根的子樹(shù)
3、樹(shù)的定義:樹(shù)的遞歸定義,即用樹(shù)來(lái)定義樹(shù),而只有一個(gè)結(jié)點(diǎn)的樹(shù)必定僅由根組成(樹(shù)只有一個(gè)根,根是樹(shù)的入口)
4、樹(shù)的組成元素:結(jié)點(diǎn)
結(jié)點(diǎn)(node):一個(gè)數(shù)據(jù)元素及其若干指向其子樹(shù)的分支
結(jié)點(diǎn)的度(degree):結(jié)點(diǎn)所擁有的子樹(shù)的棵數(shù)
樹(shù)的度:樹(shù)中結(jié)點(diǎn)度的最大值
葉子(終端)結(jié)點(diǎn):樹(shù)中度為0的結(jié)點(diǎn)
非葉子(非終端、分支)結(jié)點(diǎn):度不為0的結(jié)點(diǎn)
分支結(jié)點(diǎn)又稱(chēng)內(nèi)部結(jié)點(diǎn)
孩子結(jié)點(diǎn):一個(gè)結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)或子節(jié)點(diǎn)
雙親結(jié)點(diǎn):該結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)或父節(jié)點(diǎn)
兄弟結(jié)點(diǎn):同一雙親結(jié)點(diǎn)的所有子節(jié)點(diǎn)
堂兄弟結(jié)點(diǎn):雙親結(jié)點(diǎn)在同一層上,且不是兄弟結(jié)點(diǎn)的所有結(jié)點(diǎn)
?層次:規(guī)定樹(shù)中根結(jié)點(diǎn)的層次為1,其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1
若某結(jié)點(diǎn)在第i層,則其子節(jié)點(diǎn)在第i+1層