7-1 树！ (30分)

Myth丶恋晨 2023-02-09 13:26 14阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70 1]  
分析：  
首先题目要求“**层序遍历输出**”一棵树所有叶子节点编号，再看题目的输入要求，是输入其自身序号以及对应的左右子树序号，而序号是从1到N按顺序下来的，而不是按某种遍历输入，因此建树再层序输出的方法比较麻烦。  
**思路**：可以定义一个结构，里面有树的深度，自身序号，左结点和右结点的序号。然后定义一个此结构类型的的队列。开始时，把1号序列树入队，再设置循环至队列为空时停止，循环中依次弹出，如果弹出的结点，它的左右节点都为0，那么就输出它的序号以及深度；如果左结点不为空就把左结点的深度+1，再把左结点入队；如果右结点不为空就把右结点的深度+1，再把右结点入队。

#include<stdio.h>
    struct Node{
        
    	int e,r,l,d; //e为自身结点序号，r为右结点序号，l为左结点序号，d为自身结点深度
    };
    void Operate(struct Node* T)
    {
        
    	int front=0,rear=0;//front为出队标志，rear为入队标志
    	struct Node a[600],t;//队列类型为结构类型
    	a[++rear]=T[1];
    	while(front!=rear){
        //front和rear相等时，表示队列为空
    		t=a[++front];
    		if(!t.l&&!t.r) printf("%d %d\n",t.e,t.d);
    		else{
        
    			T[t.l].d=T[t.r].d=t.d+1;//深度+1
    			if(t.l) a[++rear]=T[t.l];//左不空，入队列
    			if(t.r) a[++rear]=T[t.r];//右不空，入队列
    		}
    	}
    }
    int main ()
    {
        
    	int n,i;
    	scanf("%d",&n);
    	struct Node T[n+1];
    	for(i=1;i<=n;i++){
        
    		scanf("%d %d %d",&T[i].e,&T[i].l,&T[i].r);
    		T[i].d=0;
    	}
    	Operate(T);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200519091231492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200519091310774.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA==,size_16,color_FFFFFF,t_70