PTA列出叶结点 (25分)

古城微笑少年丶 2023-07-23 03:48 142阅读 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 条评论，142人围观）

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

相关阅读

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

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Ax

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

相关 PTA:单身狗 (25分)(C语言版)

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。输入格式：输入第一行给出一个正整数 N（≤50000），是已知夫

旧城等待，/ 2023年05月28日 05:28/ 0 赞/ 20 阅读

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

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

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

相关 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 赞/ 283 阅读

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

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

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

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

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

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

相关 6-3 先序输出叶结点（15 分）

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。函数接口定义： void PreorderPrintLeaves( BinTree BT ); 其中Bin

太过爱你忘了你带给我的痛/ 2022年04月22日 03:46/ 0 赞/ 115 阅读

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

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

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

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

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

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

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

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

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