1、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為多少？怎么算？11. 證明了二叉樹(shù)中所有節(jié)點(diǎn)的度不大于2，n=N0，N1，N2。另一方面，0度節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，1度節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，2度節(jié)點(diǎn)有兩

1、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為多少？怎么算？

11. 證明了二叉樹(shù)中所有節(jié)點(diǎn)的度不大于2，n=N0，N1，N2。另一方面，0度節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，1度節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，2度節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，因此二叉樹(shù)中的子節(jié)點(diǎn)總數(shù)為N1，2n2。此外，只有根節(jié)點(diǎn)不是任何節(jié)點(diǎn)的子節(jié)點(diǎn)。N=n1 2 n2 1，根據(jù)上述公式，N 0=n2 1。原來(lái)的命題已經(jīng)被證明了！深度為K且節(jié)點(diǎn)數(shù)為2^K-1的二叉樹(shù)稱為完全二叉樹(shù)。該樹(shù)的特點(diǎn)是每層的節(jié)點(diǎn)數(shù)為最大節(jié)點(diǎn)數(shù)。在二叉樹(shù)中，除了最后一層，如果所有其他層都滿了，并且最后一層要么滿了，要么右邊缺少幾個(gè)連續(xù)的節(jié)點(diǎn)，那么二叉樹(shù)就是一個(gè)完整的二叉樹(shù)。具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度是floor（log2n）1。

對(duì)于一顆具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為多少？

N-1每個(gè)節(jié)點(diǎn)都有且只有一個(gè)度數(shù)。除了根節(jié)點(diǎn)沒(méi)有度數(shù)，所以總數(shù)是n-1。

樹(shù)的度和結(jié)點(diǎn)數(shù)的關(guān)系是什么？

深度為K的二叉樹(shù)最多有2^ K-1個(gè)節(jié)點(diǎn)，二叉樹(shù)的i層最多有2^{i-1}個(gè)節(jié)點(diǎn)，深度為K和N的二叉樹(shù)最多有2^{i-1}個(gè)節(jié)點(diǎn)。

二叉樹(shù)是一種有序樹(shù)，其次數(shù)不超過(guò)2次。它是最簡(jiǎn)單也是最重要的樹(shù)。二叉樹(shù)的遞歸定義是：二叉樹(shù)是由一個(gè)根節(jié)點(diǎn)和兩個(gè)不相交的左右子樹(shù)（稱為根）組成的空樹(shù)或非空樹(shù)；左右子樹(shù)也是二叉樹(shù)；二叉樹(shù)是一組N個(gè)有限元。集合是空的，或者由稱為根的元素和兩個(gè)不相交的二叉樹(shù)（分別稱為左子樹(shù)和右子樹(shù)）組成。序列樹(shù)。當(dāng)集合為空時(shí)，二叉樹(shù)稱為空二叉樹(shù)。在二叉樹(shù)中，元素也稱為節(jié)點(diǎn)

1。概念

與圖論中的“度”不同，樹(shù)的度定義如下：在有根樹(shù)T中，節(jié)點(diǎn)x的子節(jié)點(diǎn)數(shù)稱為x的度，即：在樹(shù)中，節(jié)點(diǎn)有幾個(gè)分支，度為幾個(gè)。

一個(gè)有用的小公式：樹(shù)中的節(jié)點(diǎn)數(shù)=分叉總數(shù)1。設(shè)t的階數(shù)為4，其中階數(shù)為1、2、3和4的節(jié)點(diǎn)數(shù)分別為4、2、1和1，則t中的葉數(shù)為？

解決方案：

葉的度數(shù)為0；然后讓葉的數(shù)目為x，則樹(shù)的總分支數(shù)為1*42*23*14*1=15；樹(shù)的節(jié)點(diǎn)數(shù)為16（這里涉及一個(gè)公式，節(jié)點(diǎn)數(shù)=分支數(shù)1，可以從圖中觀察到）。根據(jù)主題，我們可以知道頂點(diǎn)的數(shù)量。我們也可以列出一個(gè)方程：4211x，然后我們可以得到方程：4211x=16；x=8是葉子的數(shù)目。

由于此問(wèn)題是數(shù)據(jù)結(jié)構(gòu)中的問(wèn)題：一般來(lái)說(shuō)，它是一個(gè)有向樹(shù)，因此葉節(jié)點(diǎn)的階數(shù)為0。為了區(qū)別于離散數(shù)學(xué)中的無(wú)向樹(shù)，葉節(jié)點(diǎn)的階數(shù)為1。在數(shù)據(jù)結(jié)構(gòu)中，常用的公式是：二叉樹(shù)：階數(shù)為0的節(jié)點(diǎn)數(shù)=階數(shù)為21的節(jié)點(diǎn)數(shù)（N0=N21）。這個(gè)公式可以從上面的計(jì)算思想中推導(dǎo)出來(lái)（一般來(lái)說(shuō)，二叉樹(shù)中的公式比較多。只要你在樹(shù)中清楚地定義和繪制一個(gè)圖形，你就可以根據(jù)圖形找到規(guī)則）