首頁猿問對(duì)于任何一顆二叉樹，度為0

對(duì)于任何一顆二叉樹，度為0

C C# C++

kathria 2017-02-14 15:30:33

對(duì)于任何一顆二叉樹，度為0總是比度為2的節(jié)點(diǎn)多1.不能理解。度為0.節(jié)點(diǎn)不是有一個(gè)嗎？度為2，節(jié)點(diǎn)不是有三個(gè)嗎？啊不應(yīng)該多2嗎？

查看完整描述

3 回答

已采納

望遠(yuǎn)

TA貢獻(xiàn)1017條經(jīng)驗(yàn) 獲得超1032個(gè)贊

度為0的點(diǎn)指的是葉子節(jié)點(diǎn)，如果總節(jié)點(diǎn)有n個(gè)，對(duì)應(yīng)度為0.1.2的節(jié)點(diǎn)有n0,n1,n2個(gè)，那么n=n0+n1+n2;并且總度和為n1+2n2=n-1;這兩個(gè)公式減一下就可以得到結(jié)果。

反對(duì) 回復(fù) 2017-02-14

kathria
我看網(wǎng)上就這么寫的。。沒懂。。。為什么不能假設(shè)然后直接想減？

回復(fù) 2017-02-14
望遠(yuǎn)
可以啊，只是你理解錯(cuò)度為0的節(jié)點(diǎn)了，對(duì)于一棵最簡(jiǎn)單的二叉樹來說總的節(jié)點(diǎn)數(shù)是3，度為0的節(jié)點(diǎn)數(shù)為2，度為2的節(jié)點(diǎn)數(shù)是1

回復(fù) 2017-02-14
kathria
你看下我發(fā)的圖片。。我是哪里理解有誤，謝謝你了。

回復(fù) 2017-02-15

kathria

TA貢獻(xiàn)3條經(jīng)驗(yàn) 獲得超0個(gè)贊

直接3-1不行嗎？求大神指教

反對(duì) 回復(fù) 2017-02-14

qq_慕九州7396491
按照你的說法，度為0的結(jié)點(diǎn)（包含其子結(jié)點(diǎn)）確實(shí)有一個(gè)，度為2的結(jié)點(diǎn)（包含其子結(jié)點(diǎn)）有三個(gè)結(jié)點(diǎn)，但是其中有兩個(gè)結(jié)點(diǎn)的度為0，合起來這三個(gè)結(jié)點(diǎn)：一個(gè)度為2，兩個(gè)度為0。好，現(xiàn)在再擴(kuò)散到多個(gè)結(jié)點(diǎn)，先列出公式：n0=n2+1,每增加一個(gè)度為0的結(jié)點(diǎn)，其父節(jié)點(diǎn)若度為0，則度為0的結(jié)點(diǎn)不加也不減，即n0+1-1=n2,公式成立；若父節(jié)點(diǎn)度為1，則度為2的結(jié)點(diǎn)也加1,即n0+1=n2+1+1，公式也成立，注意這個(gè)公式只在二叉樹中成立。

回復(fù) 2020-10-28
qq_慕九州7396491
哦，2017年的，那沒事了

回復(fù) 2020-10-28