1-E 二叉树的操作 描述 给定一棵二叉树，在二叉树上执行两个操作：
节点交换
前驱询问
输入 第一行输出一个整数t(t <= 100)，代表测试数据的组数。
输出 对于每次询问操作，输出相应的结果。
样例输入 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2 5 5 0 1 2 1 -1 -1 2 3 4 3 -1 -1 4 -1 -1 2 0 1 1 2 2 0 1 3 4 2 2 3 2 0 1 2 1 -1 -1 2 -1 -1 1 1 2 2 0
样例输出 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 #include <iostream> using namespace std ;struct node { int parent; int left; int right; }; void swap (int a, int b, struct node tree[]) if (tree[a].parent == tree[b].parent){ if (tree[tree[a].parent].left == a){ tree[tree[a].parent].left = b; tree[tree[a].parent].right = a; } else { tree[tree[a].parent].right = b; tree[tree[a].parent].left = a; } } else { if (tree[tree[a].parent].left == a){ tree[tree[a].parent].left = b; } else { tree[tree[a].parent].right = b; } int temp = tree[a].parent; tree[a].parent = tree[b].parent; if (tree[tree[b].parent].left == b){ tree[tree[b].parent].left = a; } else { tree[tree[b].parent].right = a; } tree[b].parent = temp; } } int check (int p, struct node tree[]) while (tree[p].left != -1 ){ p = tree[p].left; } return p; } void output (struct node tree[], int n) for (int i = 0 ; i < n; i++){ cout << "Tree: " << i << " Left: " << tree[i].left << " Right: " << tree[i].right << " Parent: " << tree[i].parent << endl ; } } int main (void ) struct node tree [100]; int group; cin >> group; for (int g = 0 ; g < group; g++){ int n, m; cin >> n >> m; tree[0 ].parent = -1 ; int tag, left, right; for (int i = 0 ; i < n; i++){ cin >> tag >> left >> right; tree[tag].left = left; tree[tag].right = right; tree[left].parent = tag; tree[right].parent = tag; } int type; for (int i = 0 ; i < m; i++){ cin >> type; if (type == 1 ){ int a, b; cin >> a >> b; swap(a, b, tree); } else if (type == 2 ){ int p; cin >> p; cout << check(p, tree) << endl ; } } } return 0 ; }
