什么是紅黑樹

《算法導(dǎo)論》上可不是這么說的：

如果一個(gè)二叉查找樹滿足下面的紅黑性質(zhì)，那么則為一個(gè)紅黑樹。

1）每個(gè)節(jié)點(diǎn)或是紅的，或者是黑的。

2）每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色的

3）如果一個(gè)節(jié)點(diǎn)是紅色的，那么他的兩個(gè)兒子都是黑的。

4）根節(jié)點(diǎn)是黑色的。

5）對于每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑色節(jié)點(diǎn)。

我們在整個(gè)過程中會(huì)用到這些性質(zhì)，當(dāng)然，為了公平起見，其實(shí)即使你不知道這些性質(zhì)，這個(gè)題目也是可以完成的（為什么不早說。。。。）。在紅黑樹的各種操作中，其核心操作被稱為旋轉(zhuǎn)，那么什么是旋轉(zhuǎn)呢，我們來看一個(gè)例子：

假設(shè)我們這里截取紅黑樹的一部分，放在左邊，通過操作如果可以把他轉(zhuǎn)化為右邊的形式，那么我們就稱將根為x的子樹進(jìn)行了左旋，反之我們稱將根為Y的樹進(jìn)行了右旋：

恰好慢板同學(xué)把自己紅黑樹弄亂了，然后請你幫忙進(jìn)行修復(fù)，他將向你描述他的紅黑樹（混亂的。。。）。然后告訴他需要用哪種方式旋轉(zhuǎn)某個(gè)節(jié)點(diǎn)。在你完成工作之后，直接向大黃提交新的樹的中序遍歷結(jié)果就好了。

?

Hint:

在這里好心的慢板同學(xué)給你簡單的解釋下樣例：

最開始的時(shí)候樹的樣子是這樣的：

?? ?0

??/ ? ?

1 ? ? ? 2

然后對于標(biāo)號(hào)為0的節(jié)點(diǎn)進(jìn)行右旋，結(jié)果將變?yōu)椋?/p>

?1

??

?? 0

?? ?

?? ? ?2

然后呢。。。

中序遍歷？這個(gè)是什么東西，哪個(gè)人可以告訴我下。。。。

輸入輸入分兩部分：
第一部分：一個(gè)整數(shù)T(1<=T<=10),表示測試的組數(shù)。
第二部分：第一行是一個(gè)數(shù)字N，表示紅黑樹的節(jié)點(diǎn)個(gè)數(shù)。0<N<10
然后下面有N行，每行三個(gè)數(shù)字，每個(gè)數(shù)字的大小都在-1~N-1之間。第一個(gè)數(shù)字表示當(dāng)前節(jié)點(diǎn)的標(biāo)號(hào)，后面兩個(gè)數(shù)字表示這個(gè)節(jié)點(diǎn)的左孩子和右孩子。如果是-1的話表示是空節(jié)點(diǎn)。對于所有的輸入來說標(biāo)號(hào)為0節(jié)點(diǎn)為根。
然后是一個(gè)數(shù)字M表示需要旋轉(zhuǎn)的次數(shù)。M<100
接下來M行，每行有兩個(gè)數(shù)字，分別表示你要旋轉(zhuǎn)的節(jié)點(diǎn)標(biāo)號(hào)和你需要的操作。標(biāo)號(hào)的范圍為0~n-1,如果標(biāo)號(hào)后面的數(shù)字0，那么表示為左旋。如果是1，則表示右旋。 輸出每組測試返回N行數(shù)字，表示對樹的中序遍歷。在每組測試數(shù)據(jù)之后留一行空行。 樣例輸入

1
3
0?1?2
1?-1?-1
2?-1?-1
1
0?1

樣例輸出

1
0
2

#include#include#includetypedef?struct?node//創(chuàng)建靜態(tài)紅黑樹
{
	int?left;
	int?right;
}sanyuanzu;
sanyuanzu?map[20];
void?zhongxu(int?n)//遞歸中序遍歷
{
	if(n==-1)
		return;//跳出函數(shù)體?
	zhongxu(map[n].left);//遞歸?輸出map[0].left?直到map[n].left為-1??
	printf("%dn",n);
	zhongxu(map[n].right);//遞歸?輸出map[0].right?直到map[n].right為-1
}

int?main()
{	
	int?n,?node,i,a,b,c,m,d,e;
	scanf("%d",&n);
	while(n--)
	{	
		memset(map,-1,sizeof(map));
		scanf("%d",&node);
		for(i=0;i<node;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			map[a].left=b;
			map[a].right=c;
		}
		
		scanf("%d",&m);
		while(m--)
			scanf("%d%d",&d,&e);?
		zhongxu(0);
	}
}