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