C语言中计算二叉树的宽度的两种方式分享

—-想了解C语言中计算二叉树的宽度的两种方式分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

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;//返回计算所得的最大的二叉树的宽度。  }  

总结：

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

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