千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站

千鋒學(xué)習(xí)站 | 隨時(shí)隨地免費(fèi)學(xué)

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻

關(guān)注千鋒學(xué)習(xí)站小程序
隨時(shí)隨地免費(fèi)學(xué)習(xí)課程

一、二叉樹各結(jié)點(diǎn)的度

二叉樹各結(jié)點(diǎn)的度是指樹中所以結(jié)點(diǎn)的度數(shù)的最大值。二叉樹的度小于等于2，因?yàn)槎鏄涞亩x要求二叉樹中任意結(jié)點(diǎn)的度數(shù)（結(jié)點(diǎn)的分支數(shù)）小于等于2。

節(jié)點(diǎn)度就是這個(gè)節(jié)點(diǎn)的孩子數(shù)量，例如有左右孩子的節(jié)點(diǎn)，它的度為2，如果只有左孩子或者只有右孩子的節(jié)點(diǎn)，它的度就是1，葉節(jié)點(diǎn)就是度為0的節(jié)點(diǎn)（沒有孩子）。

先序遍歷的話，只要孩子不是NULL，就可以將這個(gè)節(jié)點(diǎn)的度+1。比如這張圖，以節(jié)點(diǎn)3為例，它的左孩子是6，度+1，現(xiàn)在度為1。右孩子沒有，即NULL，不做任何操作。所以節(jié)點(diǎn)3的度為1。

二叉樹是樹形結(jié)構(gòu)中一種特殊的樹形結(jié)構(gòu)：二叉樹中的每個(gè)結(jié)點(diǎn)至多有2棵子樹（即每個(gè)結(jié)點(diǎn)的度小于等于2），并且兩個(gè)子樹有左右之分，順序不可顛倒。在二叉樹中還有種特殊的二叉樹就是完全二叉樹：所有結(jié)點(diǎn)中除了葉子結(jié)點(diǎn)以外的結(jié)點(diǎn)都有兩棵子樹。如果完全二叉樹中只有最底層為葉子結(jié)點(diǎn)那么又稱為滿二叉樹。

延伸閱讀：

二、二叉樹重要性質(zhì)

二叉樹中，第m-層非常多有2^(m-1)個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)為名列前茅層）高度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)二叉樹T葉子結(jié)點(diǎn)總數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1如果完全二叉樹有n個(gè)結(jié)點(diǎn)，那么樹較高為log2(n)+1對(duì)于完全二叉樹，從上至下，從左至右對(duì)每個(gè)結(jié)點(diǎn)從1-n編號(hào)，那么對(duì)于結(jié)點(diǎn)n有：如果i=1，那么此結(jié)點(diǎn)為根結(jié)點(diǎn)，如果i>1那么該結(jié)點(diǎn)的父結(jié)點(diǎn)為不大于i/2的最大整數(shù)如果2*i>n，那么i結(jié)點(diǎn)沒有左子樹，如果2*i<=n那么該結(jié)點(diǎn)的左子樹編號(hào)為2*i如果2*i+1>n，那么結(jié)點(diǎn)i沒有右子樹，如果2*i+1<=n那么該結(jié)點(diǎn)的右子樹編號(hào)為2*i+1