Two ways to calculate the width of a binary tree in the C language

Two ways to calculate the width of a two-fork tree in the C language

2 fork tree as a very special data structure, function has a great role! Today let's see how to calculate the maximum width of a two-fork tree.

We're going to do it recursively

Here's the code:

int GetMaxWidth(BinaryTree pointer){
  int width[10];// The maximum height to add to this tree is no higher than 10
  int maxWidth=0;
  int floor=1;
  if(pointer){
    if(floor==1){// If you are accessing the root node, no 1 Layer nodes ++;
      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--;// Remember to return 1 Layer, otherwise there will be errors. Because already Get Yes, so return in time. 
    GetMaxWidth(pointer->rightChild);
  }
  return maxWidth;
}

Take a non-recursive approach

Calculating the width of a two-fork tree in a non-recursive way requires the aid of a queue. The code is as follows:

int GetMaxWidth(BinaryTree pointer){
  if(pointer==null){
    return 0;
  }
  Queue<BinaryTreeNode> queue=new ArrayDeque<BinaryTreeNode>();
  int maxWidth=1;// Maximum width 
  queue.add(pointer);
  while(true){
    int size=queue.size();// Calculates the number of nodes in the current layer 
    if(size==0){
      break;
    }
    while(size>0){// Proceed if there are still nodes in the current layer 
      BinaryTreeNode node=queue.poll();
      size--;
      if(node->leftChild)
        queue.add(node->leftChild);// The left subtree of the current node is queued 
      if(node->rightChild)
        queue.add(node->rightChild);// The right subtree of the current node is queued 
      maxWidth=Math.max(size,queue.size());
    }
  }
  return maxWidth;// Returns the calculated maximum 2 The width of the fork tree. 
}

Conclusion:

Either way, it actually takes advantage of the ability to traverse a two-fork tree.

Thank you for reading, I hope to help you, thank you for your support of this site!