【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; }
