NYOJ 202红黑树

旋转操作不影响中序遍历。只要把树存起来再中序遍历即可。

 1  
 2 #include<iostream>
 3 using namespace std;
 4 struct node{
 5     int L;
 6     int R;
 7 }Tree[11];
 8 void InorderTraverse(int root)
 9 {
10     if(Tree[root].L != -1)InorderTraverse(Tree[root].L);
11     cout<<root<<endl;
12     if(Tree[root].R != -1)InorderTraverse(Tree[root].R);
13 }
14 int main()
15 {
16     //freopen("in.txt","r",stdin);
17     int i,T,root,lchild,rchild,N,M;
18     cin>>T;
19     while(T--)
20     {
21         cin>>N;
22         for(i=0; i<N; i++){
23             cin>>root>>lchild>>rchild;
24             Tree[root].L = lchild;
25             Tree[root].R = rchild;
26         }
27         for(cin>>M;M--;cin>>root>>rchild);
28         InorderTraverse(0);
29         cout<<endl;
30     }
31     return 0;
32 }
33