PTA列出叶结点 (25分)

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

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

相关阅读

相关 PTA 树的同构 (25分)

PTA 树的同构 (25分) ![1][] 输入格式: 输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假

缺乏、安全感/ 2023年07月25日 11:23/ 0 赞/ 20 阅读

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

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Ax

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

相关 PTA: 单链表结点的阶乘和 (15分)

本题要求实现一个函数，求单链表L结点的阶乘和。这里默认所有结点的值非负，且题目保证结果在int范围内。函数接口定义： int FactorialSum( List L

爱被打了一巴掌/ 2023年07月21日 13:25/ 0 赞/ 42 阅读

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

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

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

相关 PTA练习题：先序输出叶结点

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

忘是亡心i/ 2023年02月11日 04:45/ 0 赞/ 10 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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