【数据结构】（二叉树）计算二叉树的高度递归与非递归三种方法 C语言

￡神魔★判官ぃ 2021-11-14 12:46 225阅读 0赞

## 递归法求二叉树高度 ##

**递归法可以理解为一个子问题当一棵树只有左孩子和右孩子的时候我们只需要计算其左孩子的高度和其右孩子的高度并且求的他门两个之间的最大值并且+1即可 这个1就是根节点这样我们就得到了递归代码如下**

/**
    计算二叉树的高度 递归法
    */
    int getdepth3(BiTree *t){
        
    	
    	if(t!=NULL){
        
    		int ldpth=getdepth3(t->lchild);
    		int rdpth=getdepth3(t->rchild);
    		return ldpth>rdpth? 1+ldpth:1+rdpth; 
    	}else
    	{
        
    			return 0;
    	}
    
    }

## 非递归求解 ##

**第一种方案是可以采用层次遍历的方法记录设置一个指向最后一个结点的“指针”，每次遍历到最后一个结点层次+1**

/**
    计算二叉树的高度 非递归层次遍历方法一
    次方法为 last指针一直指向每一层最右面的元素
    */
    
    int getdepth1(BiTree *t){
        
    	if(t){
        
    		 int front=-1,rear=-1;
    		 int level=0;int last=0;
    		 BiTree *que[MaxSize];
    		 que[++rear]=t;
    
    		 while(front<rear){
          //某一时刻 front==rear 出队最后一个元素
    			t=que[++front];
    	
    			if(t->lchild!=NULL)
    				que[++rear]=t->lchild;
    		
    			if(t->rchild!=NULL)
    				que[++rear]=t->rchild;
     			if(front==last){
        
    				last=rear;
    				level++;
    			}
    		 }
    		 return level;
    	}
    	return 0;
    }

**第二种方案也是层次遍历 记录每一层节点的个数当每一层结点全部出队列的时候 层次+1**

/**
    计算二叉树的高度 非递归层次遍历方法二
    同为层次遍历该方法为记录每一层的的个数当一层全部出队列 层数+1
    */
    
    int getdepth2(BiTree *t){
        
     
    	 if(t){
        
    		 int front=-1, rear=-1;
    	 	 BiTree *que[MaxSize];
    	 	 int count=0;
    		 int level=0;
    		 que[++rear]=t;
    		 count++;  //队列内元素计数器
    		 int size=0; //每一层元素个数
    
    		 while(front<rear){
        
    			 level++;
    			 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 level;
    	}
    	return 0;
    }

## 测试结果![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70] ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]: /images/20211114/a3d4207314514ac9a7ae489a23eda396.png