C語言中計算二叉樹的寬度的兩種方式

C語言中計算二叉樹的寬度的兩種方式。本站提示廣大學習愛好者：（C語言中計算二叉樹的寬度的兩種方式）文章只能為提供參考，不一定能成為您想要的結果。以下是C語言中計算二叉樹的寬度的兩種方式正文

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;//返回計算所得的最大的二叉樹的寬度。
}

總結：

不管采用哪種方式，實際上還是利用了對二叉樹的遍歷的特點來進行的。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！