7-3 求二叉树的叶子结点个数 (20分)

冷不防 2023-07-25 11:25 8阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]  
分析：  
题目关键在于怎样创建一棵树，具体的思路就是和先序遍历一样，先根结点，再左孩子，最后右孩子，无非就是遍历的时候是Pretravelse（BinTree T），而创建树的时候是Create（BinTree T）  
（这是递归的抽象思维，你就把它抽象的总结出来，具体的遍历步骤，等代码写出来再去具体一条条走）  
创建树：由于是先序序列输入，那么第一个输入的肯定为根结点，然后一直向左延伸，当输入碰到 \# 时，左边（即左分支）搞定了，然后向右向右延伸，直到碰到 \# 时，右边（即右分支）搞定。  
至于叶子结点可通过先序遍历，当碰到左右孩子都为NULL时，count++来统计。或者用层序遍历来统计，层序遍历的话要用队列，第一个结点（根结点）先入队，然后设一个循环（当队列为空时结束），循环内语句为如果结点左孩子不为NULL则入队，否则为NULL的话设置标记flag为1（flag原先为0），如果右孩子不为NULL则入队，否则为NULL的话，如果flag为1的话则count++，flag等于0。（在这里只给出先序递归的代码，层序只提供思路，抱歉！）  
具体代码：

# include <stdio.h>
    # include <stdlib.h>
    struct Node{
        
    	char data;
    	struct Node* left;
    	struct Node* right;
    };
    typedef struct Node* BinTree;
    BinTree Create()
    {
        
    	BinTree T;
    	char x;
    	scanf("%c",&x);
    	if(x=='#') return NULL;
    	else {
        
    		T=(BinTree)malloc(sizeof(struct Node));
    		T->data=x;
    		T->left=Create();
    		T->right=Create();
    		return T;
    	}
    }
    void InOrderTraverse(BinTree T)
    {
        
    	if(!T) return;
    	else{
        
    		InOrderTraverse(T->left);
    		printf("%c",T->data);
    		InOrderTraverse(T->right);
    	}
    }
    int Count(BinTree T,int count)
    {
        
    	if(T){
        
    		if(T->left==NULL&&T->right==NULL) count++;
    		count=Count(T->left,count);
    		count=Count(T->right,count);
    	}
    	return count;
    }
    int main()
    {
        
    	BinTree T=Create();
    	int count=0;
    	InOrderTraverse(T);
    	printf("\n");
    	count=Count(T,count);
    	printf("%d",count);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]: /images/20230528/6c4ad5b73068420eb8409a516301892c.png