【两种解法】基础实验4-2.2 列出叶结点 (25 分)

立志用最少的代码做最高效的表达

---

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。

输入格式：
首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-”。编号间以 1 个空格分隔。

输出格式：
在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出样例：
4 1 5

---

步骤：
1、按行建树。 因为节点少，因此可以采用数组模拟建树的方式，即伪建树。
2、将所有节点的出现记录在数组中，遍历，若某值没出现，则一定为根。
3、dfs或队列遍历树，存储并输出节点。

总结：
1、对于简单的建树工程，可以采用数组伪建树的方法
2、对于按顺序输出叶节点，可以采用两种方法
  1、采用dfs深度优先搜索，同时将层数加入递归遍历
  2、采用队列层序遍历输出。

---

DFS解法

#include<iostream> #include<vector> #include<cstring> using namespace std;struct node{char left, right; }nd[15];vector<int>leaf[15]; void dfs(int s, int cur) { //cur是层数 if(nd[s].left == '-' && nd[s].right == '-') {leaf[cur].push_back(s); //记录叶节点 return;}if(nd[s].left != '-') dfs(nd[s].left - '0', cur + 1); //左遍历 if(nd[s].right != '-') dfs(nd[s].right - '0', cur + 1); }int main() {int n, root[10], rt = 0;memset(root, 0, sizeof(root));cin >> n;for(int i = 0; i < n; i++) {cin >> nd[i].left >> nd[i].right;root[nd[i].left-'0'] = root[nd[i].right-'0'] = 1; //判断根 }for(int i = 0; i < n; i++) //求根节点 if(!root[i]) {rt = i;break;}dfs(rt, 1);bool f = false;for(int i = 1; i <= 10; i++) {for(int j = 0; j < leaf[i].size(); j++) {if(f) cout << ' ';else f = true;cout << leaf[i][j];}}return 0; }

---

队列解法

#include<iostream> #include<vector> #include<cstring> #include<queue> using namespace std;struct node{char left, right; }nd[15];queue<int>fin; void Stack(int s) {queue<int>q;q.push(s);while(!q.empty()) {int x = q.front();q.pop();bool flag = false;if(nd[x].left != '-') { q.push(nd[x].left - '0'); flag = true; }if(nd[x].right != '-') { q.push(nd[x].right - '0'); flag = true; }if(flag == false) fin.push(x); //如果无左无右，则一定为叶，保存。 } }int main() {int n, root[10], rt = 0;memset(root, 0, sizeof(root));cin >> n;for(int i = 0; i < n; i++) {cin >> nd[i].left >> nd[i].right;root[nd[i].left-'0'] = root[nd[i].right-'0'] = 1; //判断根 }for(int i = 0; i < n; i++) //求根节点 if(!root[i]) {rt = i;break;}Stack(rt);bool flag1 = false;while(!fin.empty()) {if(!flag1) flag1 = true;else cout << ' ';cout << fin.front();fin.pop();}return 0; }

---

      ——只有一种英雄主义，就是在认清生活真相后依然热爱生活

总结

以上是生活随笔为你收集整理的【两种解法】基础实验4-2.2 列出叶结点 (25 分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。