【HBU】数据结构月考7-1 列出所有祖先结点 (30 分)
- 2019 年 12 月 3 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shiliang97/article/details/103317199
7-1 列出所有祖先结点 (30 分)
对于给定的二叉树，本题要求你按从上到下顺序输出指定结点的所有祖先结点。
输入格式:
首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。
随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 "-"。编号间以 1 个空格分隔。
最后一行给出一个结点的编号i（0≤i≤N-1）。
输出格式:
在一行中按规定顺序输出i的所有祖先结点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。
输入样例:
7 2 - - 6 - - 0 5 - - 4 1 - - 4
输出样例:
3 5
1.生成图。
2.遍历图内所有节点，打印父亲节点。因为就十个节点，顶多查100次。。。。
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 5; const int MOD = 1e9 + 7; int v[10]; struct Node { int l, r; }q[10]; void init() { CLR(q); CLR(v); } int target; queue <int> Q; vector <int> ans; void bfs() { int len = Q.size(); for (int i = 0; i < len; i++) { int num = Q.front(); Q.pop(); cout <<num<<"*****"<<endl; if (q[num].l == target || q[num].r == target) ans.pb(num); if (q[num].l != -1) Q.push(q[num].l); if (q[num].r != -1) Q.push(q[num].r); } if (Q.size()) bfs(); } int main() { init(); int n; scanf("%d", &n); char a, b; for (int i = 0; i < n; i++) { scanf(" %c %c", &a, &b); if (a == '-') q[i].l = -1; else { q[i].l = a - '0'; v[a - '0'] = 1; } if (b == '-') q[i].r = -1; else { q[i].r = b - '0'; v[b - '0'] = 1; } } int root; for (int i = 0; i < n; i++) { if (v[i] == 0) { root = i; break; } } Q.push(root); //bfs(); vector <int>::iterator it; int temp; scanf("%d", &target); for(int i=0;i<10;i++){ for(int l=0;l<10;l++){ if(q[l].l==target||q[l].r==target){ ans.push_back(l); target=l; } } } for (int i=ans.size()-1;i>=0;i--) { if (i != ans.size()-1) printf(" "); printf("%d", ans[i]); } cout << endl; }
