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;
//返回计算所得的最大的二叉树的宽度。}
总结：
不管采用哪种方式，实际上还是利用了对二叉树的遍历的特点来进行的。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
