本文主要是介绍【HBU】数据结构月考7-1 列出所有祖先结点 (30 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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 51.生成图。
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_backusing 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;
}
这篇关于【HBU】数据结构月考7-1 列出所有祖先结点 (30 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
