基础实验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），每次从队列中取出当前节点，然后将它的孩子加入队列。这样保证访问顺序符合题目的要求。
isChild 数组：
- 这个数组用来标记哪些节点是其他节点的孩子。如果某个节点的左或右孩子存在，就将对应编号的 isChild 设为 true。最终通过检查哪些节点没有被标记为子节点，找出树的根节点。
叶节点的判断：
- 叶节点是没有任何子节点的节点。通过检查节点的左右孩子是否都为 "-"，可以判断它是否是叶节点。