/&&&&&78*********^%$#@#$%^$%#
这题没什么可说的，虽然简单，但是折腾了我一阵。
我一开始用指针写的，交上去runtime error
改了好久都不行。然后喵呜要我用结构体数组实现二叉树。
写好后交上去还是WA了，折腾好一阵才AC。
总结:以后二叉树定义的时候除了左右儿子的指针还有父母的指针的话，交换两个非祖先关系的子树要特别注意啊
很容易出错，而且你根本找不到错误在哪，而且尼玛数据就是没有问题尼玛就是不知道哪错了我到现在都不知道哪错了啊喂！
#￥#@%……￥&%*……&%&……￥%#@￥@￥！@#！@#！@#？、/
1:二叉树的操作
- 总时间限制:
- 1000ms
- 内存限制:
- 65535kB
- 描述
-
给定一棵二叉树，在二叉树上执行两个操作：
1. 节点交换
把二叉树的两个节点交换。
2. 前驱询问
询问二叉树的一个节点对应的子树最左边的节点。
- 输入
-
第一行输出一个整数t，代表测试数据的组数。
对于每组测试数据，第一行输入两个整数n m，n代表二叉树节点的个数，m代表操作的次数。
随后输入n行，每行包含3个整数X Y Z，对应二叉树一个节点的信息。X表示节点的标识，Y表示其左孩子的标识，Z表示其右孩子的标识。
再输入m行，每行对应一次操作。每次操作首先输入一个整数type。
当type=1，节点交换操作，后面跟着输入两个整数x y，表示将标识为x的节点与标识为y的节点交换。输入保证对应的节点不是祖先关系。
当type=2，前驱询问操作，后面跟着输入一个整数x，表示询问标识为x的节点对应子树最左的孩子。
1<=n<=100，节点的标识从0到n-1，根节点始终是0. - 输出
- 对于每次询问操作，输出相应的结果。
- 样例输入
-
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 3 4 2
-
# include<iostream> using namespace std; struct node{ int p;//parent int l;//left int r;//right node(int pp=-1,int ll=-1,int rr=-1):p(pp),l(ll),r(rr){} }; int main(void) { node a[105]; int t,i,n,m,x,y,z,type; int p1,p2; int *q1,*q2; cin>>t; while(t--) { cin>>n>>m; for(i=0; i<n; i++) { cin>>x>>y>>z; a[x].l=y; a[x].r=z; a[y].p=a[z].p=x; } for(i=0; i<m; i++) { cin>>type; if(type==1) { cin>>x>>y; p1=a[x].p; p2=a[y].p; a[x].p=p2; a[y].p=p1; if(a[p1].l==x) q1=&a[p1].l; else q1=&a[p1].r; if(a[p2].l==y) q2=&a[p2].l; else q2=&a[p2].r; *q1=y; *q2=x; } else { cin>>x; while(a[x].l!=-1) { x=a[x].l; } cout<<x<<endl; } } } return 0; }
