C語言中計(jì)算二叉樹的寬度的兩種方式
公司主營(yíng)業(yè)務(wù)：網(wǎng)站設(shè)計(jì)制作、網(wǎng)站制作、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出滎陽免費(fèi)做網(wǎng)站回饋大家。
二叉樹作為一種很特殊的數(shù)據(jù)結(jié)構(gòu)，功能上有很大的作用！今天就來看看怎么計(jì)算一個(gè)二叉樹的最大的寬度吧。
采用遞歸方式
下面是代碼內(nèi)容：
重慶分公司
重慶分公司
int GetMaxWidth(BinaryTree pointer){
int width[10];//加入這棵樹的最大高度不超過10
int maxWidth=0;
int floor=1;
if(pointer){
if(floor==1){//如果訪問的是根節(jié)點(diǎn)的話，第一層節(jié)點(diǎn)++;
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(maxWidthleftChild);
floor--;//記得退回一層，否則會(huì)出錯(cuò)。因?yàn)橐呀?jīng)Get過了，所以要及時(shí)的返回。
GetMaxWidth(pointer->rightChild);
}
return maxWidth;
}
采用非遞歸方式
采用非遞歸方式計(jì)算二叉樹的寬度需要借助于隊(duì)列。代碼如下：
int GetMaxWidth(BinaryTree pointer){
if(pointer==null){
return 0;
}
Queue queue=new ArrayDeque();
int maxWidth=1;//最大寬度
queue.add(pointer);
while(true){
int size=queue.size();//計(jì)算當(dāng)前層的節(jié)點(diǎn)的個(gè)數(shù)
if(size==0){
break;
}
while(size>0){//如果當(dāng)前層還有節(jié)點(diǎn)就進(jìn)行下去
BinaryTreeNode node=queue.poll();
size--;
if(node->leftChild)
queue.add(node->leftChild);//當(dāng)前節(jié)點(diǎn)的左子樹入隊(duì)
if(node->rightChild)
queue.add(node->rightChild);//當(dāng)前節(jié)點(diǎn)的右子樹入隊(duì)
maxWidth=Math.max(size,queue.size());
}
}
return maxWidth;//返回計(jì)算所得的最大的二叉樹的寬度。
}
總結(jié)：
不管采用哪種方式，實(shí)際上還是利用了對(duì)二叉樹的遍歷的特點(diǎn)來進(jìn)行的。
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
