首页 > ACM题库 > 九度OJ > 九度-1541-二叉树[数据结构]
2014
02-20

九度-1541-二叉树[数据结构]

题目来自:2013年9月九度Online Judge程序猿求职及面试月赛第一场

题目描述:
旋转是二叉树的基本操作,我们可以对任意一个存在父亲节点的子节点进行旋转,包括如下几种形式(设被旋转节点为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 <cstdio>

int lchild[1010];
int rchild[1010];
int par[1010];
bool rootNode[1010];
int root;
int size[1010];
int n;

int parent(int x)
{
	return par[x];
}

int computesize(int x)
{
	if(x == -1)
		return 0;
	else
		return size[x];
}

int initsize(int x){
	if(x == -1)
		return 0;
	if(lchild[x] != -1)
		size[lchild[x]] = initsize(lchild[x]);
	if(rchild[x] != -1)
		size[rchild[x]] = initsize(rchild[x]);
	return size[x] = computesize(lchild[x]) + computesize(rchild[x]) + 1;
}

void rotate(int x)
{
	if(x == root) return;
	int p = parent(x);
	if(p == root){
		root = x;
		par[x] = -1;
	}
	else{
		int pp = parent(p);
		par[x] = pp;
		if(lchild[pp] == p)
			lchild[pp] = x;
		else
			rchild[pp] = x;
	}

	if(x == lchild[p]){
		lchild[p] = rchild[x];
		if(rchild[x] != -1)
			par[rchild[x]] = p;
		rchild[x] = p;
		par[p] = x;
	}
	else{
		rchild[p] = lchild[x];
		if(lchild[x] != -1)
			par[lchild[x]] = p;
		lchild[x] = p;
		par[p] = x;
	}
	size[x] = size[p];
	size[p] = computesize(lchild[p]) + computesize(rchild[p]) + 1;
}

int main()
{
	while((scanf("%d", &n) ) != EOF){
		for(int i = 1; i <= n; ++i)
		{
			scanf("%d%d", &lchild[i], &rchild[i]);
			if(lchild[i] != -1){
				rootNode[lchild[i]] = true;
				par[lchild[i]] = i;
			}
			if(rchild[i] != -1){
				par[rchild[i]] = i;
				rootNode[rchild[i]] = true;
			}
		}
		for(int i = 1; i <= n; ++i){
			if(!rootNode[i]){
				root = i;
				par[root] = -1;
				break;
			}
		}
		initsize(root);
		int t;
		scanf("%d", &t);
		for(int i = 1; i <= t; ++i){
			char op[10];
			int x;
			scanf("%s%d", op, &x);
			if(op[0] == 'r')
				rotate(x);
			else if(op[0] == 'p'){
				int p = parent(x);
				printf("%d\n", p);
			}
			else{
				int siz = computesize(x);
				printf("%d\n", siz);
			}
		}
	}
}

 


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯