- 题目描述
http://dsalgo.openjudge.cn/binarytree/10/
- 代码
#include <iostream>
using namespace std;
#define MAX_MN 105
struct Node
{
int parent,lchild,rchild;
};
struct Node nodes[MAX_MN];
void setRelation(int parent,int from,int to)
{
if (nodes[parent].lchild == from)
{
nodes[parent].lchild = to;
}else if (nodes[parent].rchild == from)
{
nodes[parent].rchild = to;
}else{
cout<<"error";
}
nodes[to].parent = parent;
}
void swapNode(int l,int r)
{
int lp = nodes[l].parent;
int rp = nodes[r].parent;
if(l == r)
{
return ;
}else if (lp == rp)
{
//交换父亲的左右孩子指针
//原来代码:
/************************************************************************/
/*
nodes[lp].lchild = l;
nodes[lp].rchild = r;
l 不一定就是父亲对应的左孩子
*/
/************************************************************************/
int temp;
temp = nodes[lp].lchild;
nodes[lp].lchild = nodes[lp].rchild;
nodes[lp].rchild = temp;
return;
}
setRelation(lp,l,r);
setRelation(rp,r,l);
}
void askNode(int i)
{
int c = i;
while(nodes[c].lchild != -1)
{
c = nodes[c].lchild;
}
cout<<c<<endl;
}
int main()
{
int t,m,n;
int p,l,r,op;
cin>>t;
for (int tc = 0;tc <t;tc++)
{
cin>>n>>m;
for (int i=0;i<MAX_MN;i++)
{
nodes[i].parent = -1;
nodes[i].lchild = -1;
nodes[i].rchild = -1;
}
for (int i=0;i<n;i++)
{
cin>>p>>l>>r;
nodes[p].lchild = l;
nodes[p].rchild = r;
if (l != -1)
{
nodes[l].parent = p;
}
if (r != -1)
{
nodes[r].parent = p;
}
}
for (int i=0;i<m;i++)
{
cin>>op;
if (op == 1)
{
cin>>l>>r;
swapNode(l,r);
}else if (op == 2)
{
cin>>l;
askNode(l);
}
}
}
return 0;
}