基础实验4-2.2 列出叶结点
分数 25
全屏浏览
切换布局
作者 陈越
单位 浙江大学
对于给定的二叉树,本题要求你按从上到下、从左到右的顺序输出其所有叶结点。
输入格式:
首先第一行给出一个正整数 n(≤10),为树中结点总数。树中的结点从 0 到 n−1 编号。随后 n 行,每行给出一个对应结点左右孩子的编号。如果某个孩子不存在,则在对应位置给出 "-"。编号间以 1 个空格分隔。
输出格式:
在一行中按规定顺序输出叶结点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
输出样例:
4 1 5
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
#include<bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;vector<pair<string, string>> tree(n);vector<bool> isChild(n, false);for (int i = 0; i < n; i ++){cin >> tree[i].first >> tree[i].second;//找出根节点if (tree[i].first != "-") isChild[stoi(tree[i].first)] = true;if (tree[i].second != "-") isChild[stoi(tree[i].second)] = true;}int root = -1;for (int i = 0; i < n; i ++){if (!isChild[i]){root = i;break;}}vector<int> leafNodes;queue<int> q;q.push(root);//层序遍历while(!q.empty()){int index = q.front();q.pop();if (tree[index].first == "-" && tree[index].second == "-"){leafNodes.push_back(index);}//stoi 将字符串转换为整数if (tree[index].first != "-") q.push(stoi(tree[index].first));if (tree[index].second != "-") q.push(stoi(tree[index].second));}for (int i = 0; i < leafNodes.size(); i ++){ // 修改这里 if (i == 0) cout << leafNodes[i]; else cout << " " << leafNodes[i]; } return 0;
}
代码思路:
-
输入处理与树的构建:
cppvector<pair<string, string>> tree(n); vector<bool> isChild(n, false);
- 定义了一个
tree
数组,用来存储每个节点的左右孩子。每个元素是一个pair<string, string>
类型的对,存放左右孩子的编号,使用"-"
表示没有孩子。 - 定义了一个
isChild
数组,用来标记哪些节点是其他节点的孩子。
- 定义了一个
-
标记子节点和找到根节点:
for (int i = 0; i < n; i ++){cin >> tree[i].first >> tree[i].second;if (tree[i].first != "-") isChild[stoi(tree[i].first)] = true;if (tree[i].second != "-") isChild[stoi(tree[i].second)] = true; }
- 遍历所有节点的输入,读取左右孩子,并标记这些孩子节点。
- 如果某个节点的左孩子或右孩子存在(不是
"-"
),我们将isChild
数组对应孩子的索引标记为true
。这意味着这个节点是其他节点的子节点。 - 随后遍历
isChild
数组,找到根节点,它是唯一一个没有被标记为子节点的节点。
-
层序遍历查找叶节点:
vector<int> leafNodes; queue<int> q; q.push(root);while(!q.empty()){int index = q.front();q.pop();if (tree[index].first == "-" && tree[index].second == "-"){leafNodes.push_back(index);}if (tree[index].first != "-") q.push(stoi(tree[index].first));if (tree[index].second != "-") q.push(stoi(tree[index].second)); }
- 采用层序遍历(广度优先遍历),即从根节点开始,按照从上到下、从左到右的顺序遍历整棵树。遍历过程中我们使用一个队列
queue<int>
来保存当前需要处理的节点。 - 如果某个节点的左右孩子都是
"-"
,说明它是叶子节点,将其编号加入到leafNodes
数组中。 - 若左右孩子存在,则将孩子的编号转换为整数并加入队列。
- 采用层序遍历(广度优先遍历),即从根节点开始,按照从上到下、从左到右的顺序遍历整棵树。遍历过程中我们使用一个队列
-
输出结果:
for (int i = 0; i < leafNodes.size(); i ++){if (i == 0) cout << leafNodes[i]; else cout << " " << leafNodes[i]; }
- 最后遍历
leafNodes
数组,按要求输出所有叶子节点的编号。注意第一个输出元素前不加空格,之后的元素前加上空格。
- 最后遍历
关键知识点解释:
-
pair<string, string>
:pair
是 C++ 标准库中的一种数据结构,可以存储两个值。这里的pair<string, string>
用来存储每个节点的左右孩子,使用字符串类型来处理输入的"-"
。
-
stoi()
:stoi()
是 C++ 的标准函数,用来将字符串转换为整数。比如,stoi("1")
将字符串"1"
转换为整数1
。在这道题中,用于将左右孩子的字符串编号转换成整数,方便后续操作。
-
queue<int>
和层序遍历:- 层序遍历(广度优先搜索,BFS)是一种遍历树的方式,按照从上到下、从左到右的顺序访问节点。实现层序遍历通常使用队列(
queue
),每次从队列中取出当前节点,然后将它的孩子加入队列。这样保证访问顺序符合题目的要求。
- 层序遍历(广度优先搜索,BFS)是一种遍历树的方式,按照从上到下、从左到右的顺序访问节点。实现层序遍历通常使用队列(
-
isChild
数组:- 这个数组用来标记哪些节点是其他节点的孩子。如果某个节点的左或右孩子存在,就将对应编号的
isChild
设为true
。最终通过检查哪些节点没有被标记为子节点,找出树的根节点。
- 这个数组用来标记哪些节点是其他节点的孩子。如果某个节点的左或右孩子存在,就将对应编号的
-
叶节点的判断:
- 叶节点是没有任何子节点的节点。通过检查节点的左右孩子是否都为
"-"
,可以判断它是否是叶节点。
- 叶节点是没有任何子节点的节点。通过检查节点的左右孩子是否都为
总结:
- 整个程序的核心是二叉树的层序遍历,配合
queue
来逐层查找叶节点。通过isChild
数组标记子节点,并找到根节点,再依次将叶节点输出,解决了这道题。