什么是紅黑樹呢？顧名思義，跟棗樹類似，紅黑樹是一種葉子是黑色果子是紅色的樹。。。
當然，這個是我說的。。。
《算法導論》上可不是這么說的：
如果一個二叉查找樹滿足下面的紅黑性質(zhì)，那么則為一個紅黑樹。
1）每個節(jié)點或是紅的，或者是黑的。
2）每個葉子節(jié)點(NIL)是黑色的
3）如果一個節(jié)點是紅色的，那么他的兩個兒子都是黑的。
4）根節(jié)點是黑色的。
5）對于每個節(jié)點，從該節(jié)點到子孫節(jié)點的所有路徑上包含相同數(shù)目的黑色節(jié)點。
我們在整個過程中會用到這些性質(zhì)，當然，為了公平起見，其實即使你不知道這些性質(zhì)，這個題目也是可以完成的（為什么不早說。。。。）。在紅黑樹的各種操作中，其核心操作被稱為旋轉(zhuǎn)，那么什么是旋轉(zhuǎn)呢，我們來看一個例子：
假設我們這里截取紅黑樹的一部分，放在左邊，通過操作如果可以把他轉(zhuǎn)化為右邊的形式，那么我們就稱將根為x的子樹進行了左旋，反之我們稱將根為Y的樹進行了右旋：
恰好慢板同學把自己紅黑樹弄亂了，然后請你幫忙進行修復，他將向你描述他的紅黑樹（混亂的。。。）。然后告訴他需要用哪種方式旋轉(zhuǎn)某個節(jié)點。在你完成工作之后，直接向大黃提交新的樹的中序遍歷結果就好了。
Hint:
在這里好心的慢板同學給你簡單的解釋下樣例：
最開始的時候樹的樣子是這樣的：
0
/ /
1 2
然后對于標號為0的節(jié)點進行右旋，結果將變?yōu)椋?/p>
1
/
0
/
2
然后呢。。。
中序遍歷？這個是什么東西，哪個人可以告訴我下。。。。
輸入輸入分兩部分：第一部分：一個整數(shù)T(1<=T<=10),表示測試的組數(shù)。第二部分：第一行是一個數(shù)字N，表示紅黑樹的節(jié)點個數(shù)。0<N<10然后下面有N行，每行三個數(shù)字，每個數(shù)字的大小都在-1~N-1之間。第一個數(shù)字表示當前節(jié)點的標號，后面兩個數(shù)字表示這個節(jié)點的左孩子和右孩子。如果是-1的話表示是空節(jié)點。對于所有的輸入來說標號為0節(jié)點為根。然后是一個數(shù)字M表示需要旋轉(zhuǎn)的次數(shù)。M<100接下來M行，每行有兩個數(shù)字，分別表示你要旋轉(zhuǎn)的節(jié)點標號和你需要的操作。標號的范圍為0~n-1,如果標號后面的數(shù)字0，那么表示為左旋。如果是1，則表示右旋。輸出每組測試返回N行數(shù)字，表示對樹的中序遍歷。在每組測試數(shù)據(jù)之后留一行空行。樣例輸入130 1 21 -1 -12 -1 -110 1樣例輸出102//直接對輸入的樹進行中序遍歷
#include <bits/stdc++.h>using namespace std;struct nodeTree{ int data; int left; int right;}tree[15];void orderTraverse(int t){ if(t != -1) { orderTraverse(tree[t].left); cout<<tree[t].data<<endl; orderTraverse(tree[t].right); }}int main(){ int T; cin>>T; while(T--) { int N; cin>>N; int a,b,c; for(int i=0;i<N;i++) { cin>>a>>b>>c; tree[a].data = a; tree[a].left = b; tree[a].right = c; } int M; cin>>M; while(M--) { int m,n; cin>>m>>n; } orderTraverse(0); } return 0;}
新聞熱點
疑難解答
