寫出求二叉樹深度的算法 二叉樹的高度,深度和結(jié)點(diǎn)計(jì)算?
二叉樹的高度,深度和結(jié)點(diǎn)計(jì)算?1.首先,我們聲明一個(gè)【TreeHeight】函數(shù),傳遞一個(gè)【root】的樹過來。2.然后,我們定義左右子樹,名為【LCHeight】【RCHeight】。3.此時(shí),我們
二叉樹的高度,深度和結(jié)點(diǎn)計(jì)算?
1.首先,我們聲明一個(gè)【TreeHeight】函數(shù),傳遞一個(gè)【root】的樹過來。
2.然后,我們定義左右子樹,名為【LCHeight】【RCHeight】。
3.此時(shí),我們便可以在這里進(jìn)行樹是否為空的判斷,如果是空的直接退出函數(shù)。
4.這時(shí),我們就能在這里進(jìn)行進(jìn)行左右遞歸的調(diào)用。
5.接下來,我們就可以在這里進(jìn)行邊遞歸邊累加。
6.注意,第五步驟的代碼和此段代碼的功能的相同。
二叉樹的深度和高度有什么區(qū)別?
一、概念不同 深度是從根節(jié)點(diǎn)數(shù)到它的葉節(jié)點(diǎn),高度是從葉節(jié)點(diǎn)數(shù)到它的根節(jié)點(diǎn)。 二叉樹的深度是指所有結(jié)點(diǎn)中最深的結(jié)點(diǎn)所在的層數(shù)。 對于整棵樹來說,最深的葉結(jié)點(diǎn)的深度就是樹的深度;樹根的高度就是樹的高度。這樣樹的高度和深度是相等的。 對于樹中相同深度的每個(gè)結(jié)點(diǎn)來說,它們的高度不一定相同,這取決于每個(gè)結(jié)點(diǎn)下面的葉結(jié)點(diǎn)的深度。 二、定義不同 高度和深度是相反的表示,深度是從上到下數(shù)的,而高度是從下往上數(shù)。 三、計(jì)算方式不同 1、二叉樹深度算法如下: 深度為m的滿二叉樹有2^m-1個(gè)結(jié)點(diǎn); 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n] 1.(log2n是以2為底n的對數(shù))。 2、分析二叉樹的深度(高度)和它的左、右子樹深度之間的關(guān)系。從二叉樹深度的定義可知,二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此,需先分別求得左、右子樹的深度,算法中“訪問結(jié)點(diǎn)”的操作為:求得左、右子樹深度的最大值,然后加 1 。