四川盐亭网站制作公司

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(maxWidthleftChild);
    floor--;//记得退回一层，否则会出错。因为已经Get过了，所以要及时的返回。
    GetMaxWidth(pointer->rightChild);
  }
  return maxWidth;
}

采用非递归方式

采用非递归方式计算二叉树的宽度需要借助于队列。代码如下：

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();//计算当前层的节点的个数
    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;//返回计算所得的最大的二叉树的宽度。
}

总结：

不管采用哪种方式，实际上还是利用了对二叉树的遍历的特点来进行的。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！


当前标题：C语言中计算二叉树的宽度的两种方式
转载源于：http://scyanting.com/article/jjdphe.html

其他资讯