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; } Queuequeue=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