二叉树节点数及叶子节点数

本是古典何须时尚 2022-04-10 01:54 185阅读 0赞

继续二叉树系列的代码内容。今天写的是求二叉树节点个数及叶子节点个数的代码。采用了递归的方法求解。  
代码如下：

#include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    
    typedef struct BiTNode
    {
        
    	char data;//树中节点的数据
    	struct BiTNode *lchild,*rchild;//节点的左孩子指针和右孩子指针
    }BiTNode,*BiTree;//二叉树节点
    
    //创建树
    void CreateBiTree(BiTree &T)
    {
        
    	char ch;
    	scanf("%c",&ch);
    	if(ch == '#')
    	{
        
    		T = NULL;
    		return;
    	}		
    	T = (BiTNode*)malloc(sizeof(BiTNode));
    	T->data = ch;
    	CreateBiTree(T->lchild);
    	CreateBiTree(T->rchild);
    }
    
    //计算树中的叶子节点数
    int LeafCount(BiTree T)
    {
        
    	if(NULL == T)
    	{
        
    		return 0;
    	}
    	else
    	{
        
    		if(NULL == T->lchild && NULL == T->rchild)
    		{
        
    			return 1;
    		}
    		else
    		{
        
    			return LeafCount(T->lchild) + LeafCount(T->rchild);
    		}
    	}
    }
    
    //树的节点个数
    int Nodes(BiTree T)
    {
        
    	if(NULL == T)
    		return 0;
    	else
    	{
        
    		if(NULL == T->lchild && NULL == T->rchild)
    			return 1;
    		else
    		{
        
    			return Nodes(T->lchild) + Nodes(T->rchild) + 1;
    		}
    	}
    }
    
    int main(int argc, char* argv[])
    {
        
    	BiTree T = NULL;
    	CreateBiTree(T);
    	int leaf = LeafCount(T);
    	printf("BiTree leaf num is %d\n",leaf);
    	int nodes = Nodes(T);
    	printf("BiTree nodes is %d\n",nodes);
    	return 0;
    }

构建的二叉树如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]

运行结果如下图：  
![在这里插入图片描述][20181219170115281.png]  
  相对于第一天开始写代码，现在自己对于数据结构的定义，二叉树的创建已经很熟练了。现在写代码无需参考书中的伪代码，自己直接就可以写出来，虽然可能需要调试多次才能得到正确的结果，但相对于一周前的自己，现在的自己已经有很大进步了。毕竟一年多没有写过代码，没有看过相关的内容。虽然荒废了很多，但是我觉得捡起来是很快的，加油！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]: /images/20220404/dbb00dc9b9a343c48c53358038b5cd14.png
[20181219170115281.png]: /images/20220404/207d66b397e9491295bda2361a5da971.png