您好,登錄后才能下訂單哦!
解釋:
二叉樹的深度:從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點(含根、葉結(jié)點)形成樹的一條路徑,最長路徑的長度為樹的深度。
二叉樹的寬度:二叉樹的每一層中都有一定數(shù)量的節(jié)點,節(jié)點數(shù)最多的那一層的節(jié)點數(shù)叫做二叉樹的寬度。
思路:遞歸實現(xiàn)。
1.每個節(jié)點都可以看作根節(jié)點
2.根節(jié)點(任意一個節(jié)點)的深度等于它的左子樹或右子樹深度最大值+1
3.從根結(jié)點開始遍歷,若遍歷到葉子節(jié)點,深度為0
//二叉樹的深度 public static int Depth(node root){ if(root == null){ return 0; } int dl = Depth(root.leftchild); int dr = Depth(root.rightchild); return dl>dr? dl+1:dr+1; }
二、二叉樹的寬度
思路:層序遍歷時添加一個計數(shù)器,記錄每層的節(jié)點數(shù)
1.每層出隊列時記錄下一層的節(jié)點數(shù),其實就是隊列的Size()
2.每層遍歷結(jié)束時,比較最大寬度與當(dāng)前層節(jié)點數(shù),記錄最大值
public static int Width(node root) { if(root == null) return 0; Queue<node> q = new LinkedList<node>(); q.add(root); int width = 1; //最大寬度 int len = 1; //當(dāng)前層節(jié)點數(shù) while(q.size()>0){ while(len-->0){ node node = q.poll(); if(node.leftchild != null){ q.add(node.leftchild); } if(node.rightchild != null){ q.add(node.rightchild); } } len = q.size(); //每層循環(huán)結(jié)束后記錄下一層的節(jié)點數(shù) width = width>q.size() ? width : q.size(); } return width; }
總結(jié)
以上就是本文關(guān)于Java語言描述二叉樹的深度和寬度的全部內(nèi)容,希望對大家有所幫助。如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。