【数据结构】第4周 二叉树基础

给定一棵二叉树，在二叉树上执行两个操作：
1. 节点交换
把二叉树的两个节点交换。

2. 前驱询问
询问二叉树的一个节点对应的子树最左边的节点。

2
5 5
0 1 2
1 -1 -1
2 3 4
3 -1 -1
4 -1 -1
2 0
1 1 2
2 0
1 3 4
2 2
3 2
0 1 2
1 -1 -1
2 -1 -1
1 1 2
2 0

1
3
4
2

# include<iostream>

using namespace std;

struct node{
  int p;//parent
  int l;//left
  int r;//right
  node(int pp=-1,int ll=-1,int rr=-1):p(pp),l(ll),r(rr){}
};

int main(void)
{
    node a[105];
    int t,i,n,m,x,y,z,type;
    int p1,p2;
    int *q1,*q2;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(i=0; i<n; i++)
        {
            cin>>x>>y>>z;
            a[x].l=y;
            a[x].r=z;
            a[y].p=a[z].p=x;
        }
        for(i=0; i<m; i++)
        {
            cin>>type;
            if(type==1)
            {
                cin>>x>>y;
                p1=a[x].p;
                p2=a[y].p;
                a[x].p=p2;
                a[y].p=p1;
                if(a[p1].l==x)
                q1=&a[p1].l;
                else
                q1=&a[p1].r;
                if(a[p2].l==y)
                q2=&a[p2].l;
                else
                q2=&a[p2].r;
                *q1=y;
                *q2=x;
            }
            else
            {
                cin>>x;
                while(a[x].l!=-1)
                {
                    x=a[x].l;
                }
                cout<<x<<endl;
            }
        }
    }
    return 0;
}