PAT1115 Counting Nodes in a BST

ゝ一世哀愁。 2023-03-12 12:17 17阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
**题意：**  
按照输入的顺序建一颗BST树，然后求深度最大的结点数n1和深度第二大的结点数n2  
**思路：**  
常规的建树，maxdepth记录最大深度，numofdepth记录每个深度下的结点数，根节点深度为1，bfs遍历树，每入队一个结点，更新最大深度和累加一次当前深度的结点数  
最后n1=numofdepth【maxdepth】，  
n2=numofdepth【maxdepth-1】

#include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    struct node{ 
      int data,depth;
      node *l,*r;
    };
    int maxdepth=1;
    vector<int> numofdepth(1005,0);
    void insert(node* &root,int x)
    { 
      if(root==NULL)
      { 
        root=new node;
        root->data=x;
        root->l=NULL;
        root->r=NULL;
        return;
      }
      if(x>root->data)insert(root->r,x);
      else insert(root->l,x);
    }
    void bfs(node* root)
    { 
      queue<node*> q;
      root->depth=1;
      numofdepth[1]=1;
      q.push(root);
      while(!q.empty())
      { 
        node* it=q.front();
        q.pop();
        if(it->l!=NULL)//左孩子存在
        { 
          it->l->depth=it->depth+1;
          numofdepth[it->depth+1]++;
          maxdepth=it->depth+1;
          q.push(it->l);
        }
        if(it->r!=NULL)
        { 
          it->r->depth=it->depth+1;
          numofdepth[it->depth+1]++;
          maxdepth=it->depth+1;
          q.push(it->r);
        }
      }
    }
    int main()
    { 
      int n,temp,n1,n2;
      cin>>n;
      node* rot=NULL;
      for(int i=0;i<n;i++)
      { 
        cin>>temp;
        insert(rot,temp);
      }
      bfs(rot);
      n1=numofdepth[maxdepth];
      n2=numofdepth[maxdepth-1];
      cout<<n1<<" + "<<n2<<" = "<<n1+n2<<endl;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230312/3992930e3079430e830368d4a6fd63ac.png