建站
咨詢
售后
建站咨詢
新聞中心
二叉樹是一種常見的數(shù)據(jù)結(jié)構(gòu)，具有以下五個(gè)性質(zhì)：
創(chuàng)新互聯(lián)不只是一家網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司；我們對(duì)營(yíng)銷、技術(shù)、服務(wù)都有自己獨(dú)特見解，公司采取“創(chuàng)意+綜合+營(yíng)銷”一體化的方式為您提供更專業(yè)的服務(wù)！我們經(jīng)歷的每一步也許不一定是最完美的，但每一步都有值得深思的意義。我們珍視每一份信任，關(guān)注我們的成都網(wǎng)站建設(shè)、成都做網(wǎng)站質(zhì)量和服務(wù)品質(zhì)，在得到用戶滿意的同時(shí)，也能得到同行業(yè)的專業(yè)認(rèn)可，能夠?yàn)樾袠I(yè)創(chuàng)新發(fā)展助力。未來將繼續(xù)專注于技術(shù)創(chuàng)新，服務(wù)升級(jí)，滿足企業(yè)一站式成都營(yíng)銷網(wǎng)站建設(shè)需求，讓再小的成都品牌網(wǎng)站建設(shè)也能產(chǎn)生價(jià)值！
1、每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)
2、左子樹和右子樹都是二叉樹
3、二叉樹的第i層最多有2^(i1)個(gè)節(jié)點(diǎn)（i>=1）
4、深度為k的二叉樹最多有2^k 1個(gè)節(jié)點(diǎn)（k>=1）
5、對(duì)于任何一棵二叉樹，如果其葉節(jié)點(diǎn)數(shù)為N0，度為2的節(jié)點(diǎn)數(shù)為N2，則N0=N2+1
下面是這些性質(zhì)的詳細(xì)解釋：
每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)
二叉樹中的每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)，這意味著每個(gè)節(jié)點(diǎn)可以有0、1或2個(gè)子節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)，有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn)。
左子樹和右子樹都是二叉樹
除了根節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，這兩個(gè)子節(jié)點(diǎn)也分別是一個(gè)二叉樹，整個(gè)二叉樹可以遞歸地分解為許多小的二叉樹。
二叉樹的第i層最多有2^(i1)個(gè)節(jié)點(diǎn)（i>=1）
在二叉樹中，第i層的節(jié)點(diǎn)數(shù)最多為2^(i1)，第1層的節(jié)點(diǎn)數(shù)最多為1（只有一個(gè)根節(jié)點(diǎn)），第2層的節(jié)點(diǎn)數(shù)最多為2（兩個(gè)子節(jié)點(diǎn)），第3層的節(jié)點(diǎn)數(shù)最多為4（四個(gè)子節(jié)點(diǎn)），依此類推。
深度為k的二叉樹最多有2^k 1個(gè)節(jié)點(diǎn)（k>=1）
對(duì)于深度為k的二叉樹，它的節(jié)點(diǎn)數(shù)最多為2^k 1，這是因?yàn)槊恳粚由系墓?jié)點(diǎn)數(shù)都不超過2^(k1)，而總層數(shù)就是k，總節(jié)點(diǎn)數(shù)就是每一層的節(jié)點(diǎn)數(shù)乘以總層數(shù)。
對(duì)于任何一棵二叉樹，如果其葉節(jié)點(diǎn)數(shù)為N0，度為2的節(jié)點(diǎn)數(shù)為N2，則N0=N2+1
這個(gè)性質(zhì)可以通過數(shù)學(xué)歸納法來證明，當(dāng)樹只有根節(jié)點(diǎn)時(shí)，N0=0，N2=0，滿足N0=N2+1，假設(shè)當(dāng)樹中有n個(gè)葉子節(jié)點(diǎn)時(shí)滿足N0=N2+1，那么當(dāng)添加一個(gè)新的葉子節(jié)點(diǎn)時(shí)，新的葉子節(jié)點(diǎn)將連接到某個(gè)度為1的節(jié)點(diǎn)上，使得該度為1的節(jié)點(diǎn)變?yōu)槎葹?的節(jié)點(diǎn)，此時(shí)，新的葉子節(jié)點(diǎn)是第n+1個(gè)葉子節(jié)點(diǎn)，度為2的節(jié)點(diǎn)是第n+1個(gè)度為2的節(jié)點(diǎn)，仍然滿足N0=N2+1，通過數(shù)學(xué)歸納法可知，對(duì)于任何一棵二叉樹，都滿足N0=N2+1。
網(wǎng)站題目：二叉樹的5個(gè)性質(zhì)
文章路徑：http://www.5511xx.com/article/dpjieed.html
