Java代碼二叉樹的深度 二叉樹高度java

java如何創(chuàng)建一顆二叉樹

計算機(jī)科學(xué)中，二叉樹是每個結(jié)點(diǎn)最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left

專注于為中小企業(yè)提供成都做網(wǎng)站、成都網(wǎng)站制作服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)金林免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上1000+企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

subtree）和“右子樹”（right

subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。

二叉樹的每個結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的

i

-1次方個結(jié)點(diǎn)；深度為k的二叉樹至多有2^(k)

-1個結(jié)點(diǎn)；對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)(即葉子結(jié)點(diǎn)數(shù))為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0

=

n2

+

1。

樹是由一個或多個結(jié)點(diǎn)組成的有限集合，其中：

⒈必有一個特定的稱為根(ROOT)的結(jié)點(diǎn)；

二叉樹

⒉剩下的結(jié)點(diǎn)被分成n=0個互不相交的集合T1、T2、......Tn，而且，

這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。

樹的遞歸定義如下：（1）至少有一個結(jié)點(diǎn)（稱為根）（2）其它是互不相交的子樹

1.樹的度——也即是寬度，簡單地說，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹各結(jié)點(diǎn)中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹中度不為零的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。

2.樹的深度——組成該樹各結(jié)點(diǎn)的最大層次。

3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結(jié)點(diǎn)A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；

4.有序樹——指樹中同層結(jié)點(diǎn)從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。

樹的表示

樹的表示方法有許多，常用的方法是用括號：先將根結(jié)點(diǎn)放入一對圓括號中，然后把它的子樹由左至右的順序放入括號中，而對子樹也采用同樣的方法處理；同層子樹與它的根結(jié)點(diǎn)用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。如右圖可寫成如下形式：

二叉樹

(a(

b(d,e),

c(

f(

,g(h,i)

),

)))

Java數(shù)據(jù)結(jié)構(gòu)二叉樹深度遞歸調(diào)用算法求內(nèi)部算法過程詳解

二叉樹

1

2??? 3

4 ?5 6 ?7

這個二叉樹的深度是3，樹的深度是最大結(jié)點(diǎn)所在的層，這里是3.

應(yīng)該計算所有結(jié)點(diǎn)層數(shù)，選擇最大的那個。

根據(jù)上面的二叉樹代碼，遞歸過程是：

f(1)=f(2)+1 f(3) +1 ? f(2) + 1 : f(3) +1

f(2) 跟f(3)計算類似上面，要計算左右結(jié)點(diǎn)，然后取大者

所以計算順序是f(4.left) = 0, f(4.right) = 0

f(4) = f(4.right) + 1 = 1

然后計算f(5.left) = 0,f(5.right) = 0

f(5) = f(5.right) + 1 =1

f(2) = f(5) + 1 =2

f(1.left) 計算完畢，計算f(1.right) f(3) 跟計算f(2)的過程一樣。

得到f(3) = f(7) +1 = 2

f(1) = f(3) + 1 =3

if(depleftdepright){

return?depleft+1;

}else{

return?depright+1;

}

只有l(wèi)eft大于right的時候采取left +1，相等是取right

java中二叉樹的深度怎么計算?

若為空,則其深度為0,否則,其深度等于左子樹和右子樹的深度的最大值加1

java二叉樹遍歷問題

二叉樹具有以下重要性質(zhì)：

性質(zhì)1 二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2i-1(i≥1)。

證明：用數(shù)學(xué)歸納法證明：

歸納基礎(chǔ)：i=1時，有2i-1=20=1。因?yàn)榈?層上只有一個根結(jié)點(diǎn)，所以命題成立。

歸納假設(shè)：假設(shè)對所有的j(1≤ji)命題成立，即第j層上至多有2j-1個結(jié)點(diǎn)，證明j=i時命題亦成立。

歸納步驟：根據(jù)歸納假設(shè)，第i-1層上至多有2i-2個結(jié)點(diǎn)。由于二叉樹的每個結(jié)點(diǎn)至多有兩個孩子，故第i層上的結(jié)點(diǎn)數(shù)至多是第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍。即j=i時，該層上至多有2×2i-2=2i-1個結(jié)點(diǎn)，故命題成立。

性質(zhì)2 深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)(k≥1)。

證明：在具有相同深度的二叉樹中，僅當(dāng)每一層都含有最大結(jié)點(diǎn)數(shù)時，其樹中結(jié)點(diǎn)數(shù)最多。因此利用性質(zhì)1可得，深度為k的二叉樹的結(jié)點(diǎn)數(shù)至多為：

20+21+…+2k-1=2k-1

故命題正確。

性質(zhì)3 在任意-棵二叉樹中，若終端結(jié)點(diǎn)的個數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則no=n2+1。

證明：因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度數(shù)均不大于2，所以結(jié)點(diǎn)總數(shù)(記為n)應(yīng)等于0度結(jié)點(diǎn)數(shù)、1度結(jié)點(diǎn)(記為n1)和2度結(jié)點(diǎn)數(shù)之和：

n=no+n1+n2 (式子1)

另一方面，1度結(jié)點(diǎn)有一個孩子，2度結(jié)點(diǎn)有兩個孩子，故二叉樹中孩子結(jié)點(diǎn)總數(shù)是：

nl+2n2

樹中只有根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子，故二叉樹中的結(jié)點(diǎn)總數(shù)又可表示為：

n=n1+2n2+1 (式子2)

由式子1和式子2得到：

no=n2+1

滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。

1、滿二叉樹(FullBinaryTree)

一棵深度為k且有2k-1個結(jié)點(diǎn)的二又樹稱為滿二叉樹。

滿二叉樹的特點(diǎn)：

（1） 每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。即對給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹。

（2） 滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn)，每個分支結(jié)點(diǎn)均有兩棵高度相同的子樹，且樹葉都在最下一層上。

圖(a)是一個深度為4的滿二叉樹。

2、完全二叉樹(Complete BinaryTree)

若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。

特點(diǎn)：

（1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。

（2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。

（3） 在完全二叉樹中，若某個結(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。

如圖(c)中，結(jié)點(diǎn)F沒有左孩子而有右孩子L，故它不是一棵完全二叉樹。

圖(b)是一棵完全二叉樹。

性質(zhì)4 具有n個結(jié)點(diǎn)的完全二叉樹的深度為

證明：設(shè)所求完全二叉樹的深度為k。由完全二叉樹定義可得：

深度為k得完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結(jié)點(diǎn)。

由于完全二叉樹深度為k，故第k層上還有若干個結(jié)點(diǎn)，因此該完全二叉樹的結(jié)點(diǎn)個數(shù)：

n2k-1-1。

另一方面，由性質(zhì)2可得：

n≤2k-1，

即：2k-1-ln≤2k-1

由此可推出：2k-1≤n2k，取對數(shù)后有：

k-1≤lgnk

又因k-1和k是相鄰的兩個整數(shù)，故有

,

由此即得：

注意：

的證明

網(wǎng)頁標(biāo)題：Java代碼二叉樹的深度 二叉樹高度java
鏈接分享：http://www.jiaotiyi.com/article/docsoci.html