数据结构——计算节点个数和二叉树高度（C语言版）

待我称王封你为后i 2022-12-28 00:51 116阅读 0赞

### 数据结构——计算节点个数、二叉树高度 ###

*  一、计算各种节点
 *   *  （1）计算总节点：
     *  （2）计算单分支节点：
     *  （3）计算双分支节点：
 *  二、计算二叉树高度
 *   *  代码实现：

# 一、计算各种节点 #

> 二叉树结构体如下：

//	二叉树结构体 
    typedef struct TreeLink{
        
    	int Data;
    	struct TreeLink *LChild;
    	struct TreeLink *RChild;
    }T_LINK,*TLINK;

## （1）计算总节点： ##

> 让根节点指针开始，进行二叉树的遍历，遍历树节点中不为NULL下，及存在节点，遍历次数相加之和 + 根节点 及为总节点

//	计算二叉树总节点
    int Calc_AllJieDian(TLINK p)
    {
        
    	if(p == NULL)	//	二叉树为空树 或者 该节点下没有子树
    	{
        
    		return 0;
    	}
    	
    	return 1+Calc_AllJieDian(p->LChild)+Calc_AllJieDian(p->RChild); //	遍历该节点的左右子树，再加上根节点 
    }

## （2）计算单分支节点： ##

> 遍历二叉树途中，只记录遍历树节点中遇到（左边子树存在，右边子树为NULL ）或者 （右边子树存在，左边子树为NULL）这种节点，才让递归 返回值 +1，依次累加

//	计算单分支节点 
    int Signal_Node(TLINK p)
    {
        
    	if(p==NULL){
        
    		
    		return 0;
    						//	当前节点左右子树其中一个为NULL，单支点数+1 
    	}else if((p->LChild==NULL&&p->RChild!=NULL)||(p->LChild!=NULL&&p->RChild==NULL)){
        
    		
    		
    		return Signal_Node(p->LChild)+Signal_Node(p->RChild)+1;
    	
    	}else{
        
    		//	双分支都存在，继续向下遍历 
    		return Signal_Node(p->LChild)+Signal_Node(p->RChild);
    	}
    }

## （3）计算双分支节点： ##

> 计算双分支节点思路 和 计算单支点相反 为： 遍历 二叉树 只记录 节点指针指向的节点中 左右子树都存在 的时候，递归返回值＋1，累加最后返回 就是双分支节点的个数

//	计算双分支节点
    int Calc_DoubleNode(TLINK p)
    {
        	
    	if(p==NULL){
        
    	
    		return 0;
    	
    	}else if(p->LChild!=NULL&&p->RChild!=NULL){
        	//	当节点左右子树都存在时，双分支数+1
    		 
    		return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild)+1;	//	继续遍历左右子树 
    	
    	}else{
        	//	否则只继续向下遍历左右子树 
    	
    		return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild);
    	
    	}	
    		
    }

总代码:

#include<stdio.h>
    #include<stdlib.h>
    
     
    //	二叉树结构体 
    typedef struct TreeLink{
        
    	int Data;
    	struct TreeLink *LChild;
    	struct TreeLink *RChild;
    }T_LINK,*TLINK;	
    
    //	创建二叉树 
    TLINK Create_TreeLink()
    {
        
    	TLINK T;
    	
    	int data;
    	int temp;
    	 
    	scanf("%d",&data);
    	temp = getchar();	//	吸收scanf带来的回车 
    
    	if(data == -1){
        		//	输入-1表示该节点下左树或者右树下不存数据,返回到上一级节点 
    		
    		return NULL;		
    	
    	}else{
        
    		
    		T = (TLINK)malloc(sizeof(T_LINK));	//	每个节点开辟空间 
    	
    		T->Data = data;
    		
    		printf("请输入%d节点下左节点数据:  ",data);
    		T->LChild = Create_TreeLink();
    		
    		printf("请输入%d节点下右节点数据:  ",data);
    		T->RChild = Create_TreeLink();
    		
    		return T;
    	}
    	
    }
    
    //	计算二叉树总节点
    int Calc_AllJieDian(TLINK p)
    {
        
    	if(p == NULL)
    	{
        
    		return 0;
    	}
    	
    	return 1+Calc_AllJieDian(p->LChild)+Calc_AllJieDian(p->RChild); //	遍历该节点的左右子树，再加上根节点 
    } 
    //	计算双分支节点
    int Calc_DoubleNode(TLINK p)
    {
        	
    	if(p==NULL){
        
    	
    		return 0;
    	
    	}else if(p->LChild!=NULL&&p->RChild!=NULL){
        	//	当节点左右子树都存在时，双分支数+1
    		 
    		return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild)+1;	//	继续遍历左右子树 
    	
    	}else{
        	//	否则只继续向下遍历左右子树 
    	
    		return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild);
    	
    	}	
    		
    } 
    
    //	计算单分支节点 
    int Signal_Node(TLINK p)
    {
        
    	
    	if(p==NULL){
        
    		
    		return 0;
    						//	当前节点左右子树其中一个为NULL，单支点数+1 
    	}else if((p->LChild==NULL&&p->RChild!=NULL)||(p->LChild!=NULL&&p->RChild==NULL)){
        
    		
    		
    		return Signal_Node(p->LChild)+Signal_Node(p->RChild)+1;
    	
    	}else{
        
    		//	双分支都存在，继续向下遍历 
    		return Signal_Node(p->LChild)+Signal_Node(p->RChild);
    	}
    } 
    
    int main()
    {
        
    	
    	TLINK T;				//	创建二叉树指针 
    	printf("输入第一个节点:\n");
    	T = Create_TreeLink();
    	
    	int count = Calc_AllJieDian(T);
    	
    	int SignalNode = Signal_Node(T); 
    	
    	int DoubleNode = Calc_DoubleNode(T);
    				
    	printf("总节点个数为: %d\n",count); 
    	printf("叶子节点个数为: %d\n",count-1);
    	printf("单支节点个数为: %d\n",SignalNode);
    	printf("双支节点个数为: %d\n",DoubleNode); 
    	
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70]

# 二、计算二叉树高度 #

**思路 ：**

> 递归遍历二叉树，除去根节点下，比较节点左右子树的遍历次数大小，最后大的结果 加上 根节点 1 ，就是二叉树的高度

## 代码实现： ##

//	计算二叉树的高度
    int Calc_Hight(TLINK p)
    {
        
    	int left ;			//	计算左子树 节点 
    	int right; 			//	计算右子树节点
    	int Max; 
    	
    	if(p != NULL){
        
    	
    		left = Calc_Hight(p->LChild);	//	遍历该节点的左子树
    		
    		right= Calc_Hight(p->RChild);	//	遍历该节点的右子树
    	
    		Max = left>right?left:right; 	//	比较左右子树的高度
    	
    		 
    		return Max+1; 
    	}else{
        
    		
    		return 0;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70]: /images/20221120/3ca1f931da5949b4b7fa89854f7577d1.png