时间:2021-05-20
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;//返回计算所得的最大的二叉树的宽度。}总结:
不管采用哪种方式,实际上还是利用了对二叉树的遍历的特点来进行的。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了PHP获取二叉树镜像的方法。分享给大家供大家参考,具体如下:问题操作给定的二叉树,将其变换为源二叉树的镜像。解决思路翻转二叉树,有递归和非递归两种
本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法。分享给大家供大家参考,具体如下:问题给定一棵二叉树,判定该二叉树是否是二叉搜索树(BinarySear
二叉堆是一种特殊的堆,二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆和最小堆。最大堆:父结点的键值总是大于或等于任何一个子节点
C语言数据结构二叉树简单应用在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rights
C++数据结构二叉树(前序/中序/后序递归、非递归遍历)二叉树的性质:二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子。例:实例代