C語言中計算二叉樹的寬度的兩種方式
更新時間：2017年04月07日 09:54:33 投稿：lqh
這篇文章主要介紹了C語言中計算二叉樹的寬度的兩種方式的相關(guān)資料,需要的朋友可以參考下
C語言中計算二叉樹的寬度的兩種方式
二叉樹作為一種很特殊的數(shù)據(jù)結(jié)構(gòu)，功能上有很大的作用！今天就來看看怎么計算一個二叉樹的最大的寬度吧。
采用遞歸方式
下面是代碼內(nèi)容：
int GetMaxWidth(BinaryTree pointer){
int width[10];//加入這棵樹的最大高度不超過10
int maxWidth=0;
int floor=1;
if(pointer){
if(floor==1){//如果訪問的是根節(jié)點的話，第一層節(jié)點++;
width[floor]++;
floor++;
if(pointer->leftChild)
width[floor]++;
if(pointer->rightChild)
width[floor]++;
}else{
floor++;
if(pointer->leftChild)
width[floor]++;
if(pointer->rightChild)
width[floor]++;
}
if(maxWidth<width[floor])
maxWidth=width[floor];
GetMaxWidth(pointer->leftChild);
floor--;//記得退回一層，否則會出錯。因為已經(jīng)Get過了，所以要及時的返回。
GetMaxWidth(pointer->rightChild);
}
return maxWidth;
}
采用非遞歸方式
采用非遞歸方式計算二叉樹的寬度需要借助于隊列。代碼如下：
int GetMaxWidth(BinaryTree pointer){
if(pointer==null){
return 0;
}
Queue<BinaryTreeNode> queue=new ArrayDeque<BinaryTreeNode>();
int maxWidth=1;//最大寬度
queue.add(pointer);
while(true){
int size=queue.size();//計算當(dāng)前層的節(jié)點的個數(shù)
if(size==0){
break;
}
while(size>0){//如果當(dāng)前層還有節(jié)點就進行下去
BinaryTreeNode node=queue.poll();
size--;
if(node->leftChild)
queue.add(node->leftChild);//當(dāng)前節(jié)點的左子樹入隊
if(node->rightChild)
queue.add(node->rightChild);//當(dāng)前節(jié)點的右子樹入隊
maxWidth=Math.max(size,queue.size());
}
}
return maxWidth;//返回計算所得的最大的二叉樹的寬度。
}
總結(jié)：
不管采用哪種方式，實際上還是利用了對二叉樹的遍歷的特點來進行的。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
編譯程序的基本功能是把源程序（高級語言）翻譯成目標(biāo)程序。但是,作為一個具有實際應(yīng)用價值的編譯系統(tǒng),除了基本功能之外，還應(yīng)具備語法檢查、調(diào)試措施、修改手段、覆蓋處理、目標(biāo)程序優(yōu)化、不同語言合用以及人-機聯(lián)系等重要功能2022-02-02
篩選法又稱篩法，是求不超過自然數(shù)N（N>1）的所有質(zhì)數(shù)的一種方法。據(jù)說是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）發(fā)明的，又稱埃拉托斯特尼篩子2013-10-10
這篇文章主要介紹了C++使用一個棧實現(xiàn)另一個棧的排序算法,結(jié)合實例形式分析了C++借助輔助棧實現(xiàn)棧排序算法的相關(guān)操作技巧,需要的朋友可以參考下2017-05-05
thread_local 是 C++11 中引入的關(guān)鍵字,用于聲明線程局部存儲,下面這篇文章主要給大家介紹了關(guān)于C++之thread_local變量用法的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-07-07
這篇文章主要介紹了VC6實現(xiàn)激活后臺窗口最佳方法,實例分析了VC操作后臺窗口的技巧,需要的朋友可以參考下2015-06-06
最強的C語言筆記，此處對于C語言的基礎(chǔ)部分做一個簡要的介紹，作者實屬初學(xué)，寫博客也是作者學(xué)習(xí)的一個過程，若文中內(nèi)容有理解不到位或者有不當(dāng)之處，還請朋友們不吝指正2021-11-11
CreateCompatibleDC()函數(shù)案例詳解
這篇文章主要介紹了CreateCompatibleDC()函數(shù)案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
簡單談?wù)勱P(guān)于C++中大隨機數(shù)的問題
這篇文章主要介紹了關(guān)于C++中大隨機數(shù)的問題,文中給出了詳細的示例代碼，相信對大家的學(xué)習(xí)或者工作具有一定的參考借鑒價值，有需要的朋友可以一起來學(xué)習(xí)學(xué)習(xí)。2017-01-01
在 C 語言中，字符串實際上是使用空字符 \0 結(jié)尾的一維字符數(shù)組。因此，\0 是用于標(biāo)記字符串的結(jié)束?？兆址∟ull character）又稱結(jié)束符，縮寫 NUL，是一個數(shù)值為 0 的控制字符，\0 是轉(zhuǎn)義字符，意思是告訴編譯器，這不是字符 0，而是空字符2022-04-04
在C++程序開發(fā)維護過程中,時常會遇到資源泄漏問題,比如GDI對象泄漏、進程線程句柄泄漏以及內(nèi)存泄漏問題,今天我們就來深入探討一下這幾類資源泄漏以及排查這些泄露的辦法,需要的朋友可以參考下2023-10-10