题目地址：http://ac.jobdu.com/problem.php?pid=1541
- 题目描述：
-
旋转是二叉树的基本操作，我们可以对任意一个存在父亲节点的子节点进行旋转，包括如下几种形式（设被旋转节点为x，其父亲节点为p）：
1.左旋
旋转前，x是p的右儿子。
x的左儿子（若存在）变为p的右儿子，p变为x的左儿子。如下图
2.右旋
旋转前，x是p的左儿子。
x的右儿子（若存在）变为p的左儿子，p变为x的右儿子。如下图
综上，我们可以通过检查选择前x是p的左儿子还是右儿子来判断该次旋转是左旋还是右旋。给定一颗n个节点的二叉树，其节点由1至n编号，并给定一系列操作，如下：
1.rotate x，对编号x的节点进行旋转，若x为根节点，则不进行任何操作。
2.parent x，输出编号x的父亲节点编号，若x为根节点输出-1。
3.size x，输出以x为根节点的子树的节点个数。
- 输入：
-
输入包含多组测试用例。
每组测试用例开头为一个整数n（1<=n<=1000），代表二叉树的节点个数。
接下去n行描述，二叉树原始的状态，第i行为两个整数x，y，代表i号节点的左儿子节点为x号节点，右儿子节点为y号节点，若x或y为-1，则表示相应儿子节点不存在。编号的范围为1到n。
接下去一行为一个整数t(1<=t<=50000)，代表操作的个数。
最后t行，每行代表一个对二叉树的操作，描述如上所示。
- 输出：
-
对于每组测试用例，输出操作parent x和size x查询的数据。
- 样例输入：
-
5
2 3
-1 -1
4 5
-1 -1
-1 -1
5
size 1
rotate 5
size 5
parent 3
parent 4
- 样例输出：
-
5
3
5
3
#include <stdio.h>
#include <string.h> typedef struct node{
int parent;
int left;
int right;
}Node; Node tree[1001];
int has_parent[1001];
int size[1001];
int n;
int root; int Compute(int node){
return (node == -1) ? 0 : size[node];
} int Size(int node){
if (node == -1)
return 0;
if (tree[node].left != -1)
size[tree[node].left] = Size(tree[node].left);
if (tree[node].right != -1)
size[tree[node].right] = Size(tree[node].right);
return size[node] = Compute(tree[node].left) + Compute(tree[node].right) + 1;
} void Rotate(int node){
int parent, grandpar;
int left, right;
if (node != root){
parent = tree[node].parent;
grandpar = tree[parent].parent;
tree[node].parent = grandpar;
if (grandpar != -1){
if (tree[grandpar].right == parent)
tree[grandpar].right = node;
else
tree[grandpar].left = node;
}
if (parent == root)
root = node;
tree[parent].parent = node;
if (tree[parent].right == node){//node是其父节点的右孩子，左旋
left = tree[node].left;
tree[parent].right = left;
tree[node].left = parent;
if (left != -1){
tree[left].parent = parent;
}
}
else{//node是其父节点的左孩子，右旋
right = tree[node].right;
tree[parent].left = right;
tree[node].right = parent;
if (right != -1){
tree[right].parent = parent;
}
}
size[node] = size[parent];
size[parent] = Compute(tree[parent].left) + Compute(tree[parent].right) + 1;
}
} int main(void) {
int i;
int t;
char ope[10];
int id; while (scanf("%d", &n) != EOF){
for (i = 1; i <= n; ++i){
memset(has_parent, 0, sizeof(has_parent));
memset(size, 0, sizeof(size));
scanf("%d%d", &tree[i].left, &tree[i].right);
if (tree[i].left != -1){
tree[tree[i].left].parent = i;
has_parent[tree[i].left] = 1;
}
if (tree[i].right != -1){
tree[tree[i].right].parent = i;
has_parent[tree[i].right] = 1;
}
}
for (i = 1; i <= n; ++i)
if (has_parent[i] != 1){
tree[i].parent = -1;
root = i;
break;
}
for (i = 1; i <= n; ++i)
Size(i);
scanf("%d", &t);
while (t-- != 0){
scanf("%s%d", ope, &id);
if (ope[0] == 'r')
Rotate(id);
else if (ope[0] == 'p')
printf("%d\n", tree[id].parent);
else
printf("%d\n", size[id]);
}
} return 0;
}