PAT1102 Invert a Binary Tree倒置二叉树

忘是亡心i 2023-05-21 05:59 50阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
**思路：**  
很常规的建树遍历问题，按照题目输入在读数据的直接建树，因为根节点不是任何结点的孩子，所以那个没有出现过的点就是根节点  
本题的遍历过程比较特殊，**右孩子的优先级大于左孩子**，**对于层序遍历，只需要先判断右孩子在判断左孩子即可**  
同样的，对于中序遍历，应采用**右孩子根左孩子**的顺序

#include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    struct node{ 
      int data;
      int left,right;
    }Node[15];
    vector<int> in,lv;
    void inorder(int root)
    { 
      if(root==-1)return;
      inorder(Node[root].right);
      in.push_back(Node[root].data);
      inorder(Node[root].left);
    }
    void bfs(int root)
    { 
      queue<node> q;
      q.push(Node[root]);
      while(!q.empty())
      { 
        node it=q.front();
        q.pop();
        lv.push_back(it.data);
        if(it.right!=-1)q.push(Node[it.right]);
        if(it.left!=-1)q.push(Node[it.left]);
      }
    }
    int main()
    { 
      int n,root;
      vector<int> hash(10,0);//0表示未出现过
      cin>>n;
      for(int i=0;i<n;i++)
      { 
        char a,b;
        Node[i].data=i;
        cin>>a>>b;
        if(a!='-')
        { 
          Node[i].left=a-'0';
          hash[a-'0']=1;
        }
        else Node[i].left=-1;
        if(b!='-')
        { 
          Node[i].right=b-'0';
          hash[b-'0']=1;
        }
        else Node[i].right=-1;
      }
      for(int i=0;i<n;i++)
      { 
        if(hash[i]==0)root=i;
      }
      inorder(root);
      bfs(root);
      for(int i=0;i<n;i++)
      { 
        cout<<lv[i]<<(i!=n-1?" ":"\n");
      }
      for(int i=0;i<n;i++)
      { 
        cout<<in[i]<<(i!=n-1?" ":"\n");
      }
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230521/979cecc871ca499c9924b147d93f773f.png