PTA列出叶结点 (25分)

古城微笑少年丶 2023-07-23 03:48 121阅读 0赞

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3AxOTY3OTE0OTAx_size_16_color_FFFFFF_t_70_pic_center]  
**【程序思路】**  
按从上到下、从左到右的顺序输出，则是层序遍历的顺序，这里需要用到队列。首先需要根据输入找出根节点，将输入利用静态链表的方式保存，没有被指向的编号就是根节点。然后再根据层序遍历遍历树，若该节点为叶子节点则将其编号保存，最后输出。  
**【程序实现】**

#include<bits/stdc++.h>
    using namespace std;
    struct tree{
        
    	int left,right;
    }a[15];
    int main(){
        
    	int n,check[15] = {
        0},head,p[10],j = 0;
    	queue<int> q;
    	cin>>n;
    	for (int i = 0; i < n; i++) {
        
    		char l,r;
    		cin>>l>>r;
    		a[i].left = l != '-' ? l-'0' : 12;//12表示空
    		a[i].right = r != '-' ? r-'0' : 12;
    		check[a[i].left] = 1;
    		check[a[i].right] = 1;
    	}
    	for (head = 0; head < n;head++)
    		if (!check[head]) break;
    	q.push(head);
    	while(!q.empty()) {
        
    		int i = q.front();
    		q.pop();
    		if(i == 12) continue;
    		if(a[i].left == 12 && a[i].right == 12)
    			p[j++] = i;
    		q.push(a[i].left);
    		q.push(a[i].right);
    	}
    	cout<<p[0];
    	for (int i = 1; i < j; i++)
    		cout<<' '<<p[i];
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3AxOTY3OTE0OTAx_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/9fcf86e948f54153acf0463429cf7e48.png

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关 PTA列出叶结点 (25分)

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Ax

古城微笑少年丶/ 2023年07月23日 03:48/ 0 赞/ 122 阅读

相关 7-4 列出叶结点 (25分) AC代码

7-4 列出叶结点 (25分) 对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。输入格式：首先第一行给出一个正整数 N（≤10），为树

我不是女神ヾ/ 2023年05月21日 11:48/ 0 赞/ 4 阅读

相关 PTA练习题：统计二叉树结点个数

本题要求实现一个函数，可统计二叉树的结点个数。函数接口定义： int NodeCount ( BiTree T); T是二叉树树根指针，函数NodeCount返回二叉

梦里梦外;/ 2023年02月11日 04:44/ 0 赞/ 2 阅读

相关 PTA 1003 Emergency (25 分)（详细翻译+注释）

背景： As an emergency rescue team leader of a city, you are given a special map of your

我会带着你远行/ 2022年09月03日 01:27/ 0 赞/ 269 阅读

相关天梯赛训练列出连通集（25 分）

7-1 列出连通集（25 分）给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶

旧城等待，/ 2022年05月30日 11:19/ 0 赞/ 153 阅读

相关 7-6 列出连通集（25 分）

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点

╰+攻爆jí腚メ/ 2022年05月03日 11:58/ 0 赞/ 122 阅读

相关 PTA-L2-023 图着色问题（25 分)

L2-023 图着色问题（25 分) \[[L2-023 图着色问题（25 分)][L2-023 _ _25]\] // 图论得分 25分(25分)

你的名字/ 2022年02月27日 05:34/ 0 赞/ 385 阅读

相关 PTA-L2-025 分而治之（25 分)

L2-025 分而治之（25 分) \[[L2-025 分而治之（25 分)][L2-025 _ _25]\] 分而治之，各个击破是兵家常用的策略之一。在战争中，我

快来打我*/ 2022年02月27日 05:34/ 0 赞/ 319 阅读

相关 PTA-L2-026 小字辈（25 分)

L2-026 小字辈（25 分) \[[L2-026 小字辈（25 分)][L2-026 _ _25]\] 本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

快来打我*/ 2022年02月27日 05:26/ 0 赞/ 239 阅读

相关单链表结点删除--PTA

本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下： struct ListNode {

末蓝、/ 2022年02月09日 08:39/ 0 赞/ 219 阅读