【数据结构】（二叉树）求非空二叉树的宽度递归&&非递归

女爷i 2021-11-09 10:10 430阅读 0赞

## 求非空二叉树的宽度 ##

**方法一递归：**

> \*\*算法思想：\*\*当我们看图的时候我们可以知道求二叉树的宽度本质就是求其一层有多少个结点 那么如何用递归的方式去计算每一层结点的个数呢？  
> 答案就是：我们只要知道当前结点是那一层就可以利用数组来统计数量了

int Max=0;
    int conut_[MaxSize];
    void getBiWid(BiTree *T,int k){
         //k变量为当前层数 默认从第一层开始
    	if(!T)
    		return;
    	conut_[k]++;
    	if(conut_[k]>Max)
    		Max=conut_[k];	//Max为数组的最大值
    	getBiWid(T->rchild,k+1);
    	getBiWid(T->lchild,k+1);
    }

**非递归求解：**

> \*\*算法思想：\*\*对于非递归的求法本质就是先序遍历详见[计算二叉树的高度递归与非递归 三种方法 C语言][_ C]这里我使用了两种方案

int getBiWid2(BiTree *t){
        
    	if(!t){
        
    		return 0;
    	}
    	
    	int max=0, front=-1,rear=-1,_count=0,size=0;;
    	BiTree *que[MaxSize];
    	que[++rear]=t;
    	_count++; 
    	while(front<rear){
        
    		if(_count>max)
    			max=_count;
    		size=_count;
    		_count=0;
    		while(size--){
        
    			t=que[++front];
    			if(t->lchild!=NULL){
        
    				que[++rear]=t->lchild;
    				_count++;
    			}
    			if(t->rchild!=NULL){
        
    				que[++rear]=t->rchild;
    				_count++;
    			}
    		}
    	
    	}
    	return max;
    }

[_ C]: https://blog.csdn.net/qq_41934478/article/details/97959086

发表评论取消回复

表情：

评论列表（有 0 条评论，430人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构——二叉树的非递归算法

二叉树的非递归算法先序遍历非递归算法1 先序遍历非递归算法2 非递归交换左右孩子算法使用栈来实现二叉树的非递归算法栈的基本算法 in

灰太狼/ 2022年12月26日 13:26/ 0 赞/ 175 阅读

相关【数据结构】二叉树非递归遍历

以下是我自己的一些写法，由于本人修行尚浅，因此代码难免有不当之处，如有发现，敬请指出，如有雷同纯属巧合。 / 先序遍历思路：先输出根并一直寻找左子

灰太狼/ 2022年08月26日 00:41/ 0 赞/ 178 阅读

相关数据结构-非递归遍历二叉树

转载自：[http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html][http_www.cnblog

￡神魔★判官ぃ/ 2022年08月24日 11:45/ 0 赞/ 210 阅读

相关求二叉树深度 -- 递归和非递归实现

/求二叉树深度 -- 采用递归和非递归方法经调试可运行源码及分析如下： / include <stdio.h> include <st

曾经终败给现在/ 2022年07月28日 09:46/ 0 赞/ 172 阅读

相关数据结构之搜索二叉树递归&非递归

一.搜索二叉树的性质> 1). 每个节点都有一个作为搜索依据的关键码(key),所有节点的关键码互不相同。 2). 左子树上所有节点的关键码(key)都小于根节点的关键

曾经终败给现在/ 2022年07月16日 12:28/ 0 赞/ 213 阅读

相关二叉树递归非递归

include <iostream> include <string.h> include <stack> include <windows.

ゞ浴缸里的玫瑰/ 2022年07月14日 07:43/ 0 赞/ 222 阅读

相关镜像二叉树（递归/非递归）

镜像二叉树：根节点的左右孩子交换所有节点的左右孩子都交换例如： ![在这里插入图片描述][70] 递归递推公式：根节点的左子树

约定不等于承诺〃/ 2022年05月09日 13:42/ 0 赞/ 233 阅读

相关非递归、递归遍历二叉树！

树的先、中、后、层序的遍历，需要用到栈结构和队结构。首先来看树本身的定义： typedef char TElemType; typedef struct BiTNod

小鱼儿/ 2022年04月13日 10:29/ 0 赞/ 374 阅读

相关【数据结构】（二叉树）求二叉树带权路径长度（WPL）递归&&非递归

求二叉树带权路径长度（WPL） > 简介：\树的带权路径长度(Weighted Path Length of Tree，简记为WPL)\二叉树的带权路径长度是每个叶子节点

迷南。/ 2021年11月10日 23:36/ 0 赞/ 448 阅读

相关【数据结构】（二叉树）求非空二叉树的宽度递归&&非递归

求非空二叉树的宽度方法一递归： > \\算法思想：\\当我们看图的时候我们可以知道求二叉树的宽度本质就是求其一层有多少个结点那么如何用递归的方式去计算每一层结点的个

女爷i/ 2021年11月09日 10:10/ 0 赞/ 431 阅读