C語言中計算二叉樹的寬度的兩種方式
二叉樹作為一種很特殊的數據結構，功能上有很大的作用！今天就來看看怎么計算一個二叉樹的最大的寬度吧。
采用遞歸方式
下面是代碼內容：
int GetMaxWidth(BinaryTree pointer){ int width[10];//加入這棵樹的最大高度不超過10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果訪問的是根節點的話，第一層節點++; 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--;//記得退回一層，否則會出錯。因為已經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();//計算當前層的節點的個數 if(size==0){ break; } while(size>0){//如果當前層還有節點就進行下去 BinaryTreeNode node=queue.poll(); size--; if(node->leftChild) queue.add(node->leftChild);//當前節點的左子樹入隊 if(node->rightChild) queue.add(node->rightChild);//當前節點的右子樹入隊 maxWidth=Math.max(size,queue.size()); } } return maxWidth;//返回計算所得的最大的二叉樹的寬度。}總結：
不管采用哪種方式，實際上還是利用了對二叉樹的遍歷的特點來進行的。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
