二叉树的操作

时间:2022-03-22 17:27:38
  • 题目描述

  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;
    }