北京化工大学数据结构2022/12/1作业 题解

 这两天弄工程东西去了，，，忘更了。。。刚想起来

目录

问题 A: 二叉排序树 - 文本输出

问题 B: 销售排行榜

问题 C: 二叉排序树-平衡因子

问题 D: 案例 1-1.1 二分查找

问题 E: 进阶实验 1-3.1：两个有序序列的中位数

---

问题 A: 二叉排序树 - 文本输出

struct Node
{
    int val;
   Node *lc,*rc; 
}tr;
int n;
void insert(Node *&T,int t){
    if(T==NULL){
        T=new Node();
        T->val=t;
        return ;
    }
    if(T->val>t){
        insert(T->lc,t);
    }
    else {
        insert(T->rc,t);
    }
    return ;
}
void order(Node *T,int t){
    for(int i=1;i<=t;i++){
        cout<<"    ";
    }
    if(T){
        cout<val<<'\n';
    }
    else{
        cout<<"#"<<'\n';
        return ;
    }
    if(T->lc||T->rc){
        order(T->lc,t+1);
        order(T->rc,t+1);
    }
    return ;
}
signed main(){
    Node* T=NULL;
    cin>>n;
    fer(i,1,n){
        int t;
        cin>>t;
        insert(T,t);
    }
    order(T,0);
}

问题 B: 销售排行榜

楞排序

const int N = 1e6+10;
mapint> nums;
mapint> vals;
bool cmp(string &a, string &b) {
    if(nums[a]!=nums[b])
        return nums[a]>nums[b];
    return a
}
string name, date;
signed main() {
    int num, val;
    while(cin>>name>>num>>val>>date){
        val*=num;
        nums[name]+=num;
        vals[name]+=val;
    }
    vector v;
    for(auto t:nums){
        v.pb(t.first);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;isize();++i){
        cout<" "<" "<'\n';
    }
}

问题 C: 二叉排序树-平衡因子

从子树更新上去

using namespace std;
struct Node{
    int data;
    Node *l,*r;
    int avl = 0;
};
Node* Insert(Node*& t,int e){
    if(t==nullptr){
        t=new Node;
        t->data = e;
        t->l = nullptr;
        t->r = nullptr;
    }
    else{
        if(edata){
            t->l = Insert(t->l,e);
        }
        else if(e>=t->data){
            t->r = Insert(t->r,e);
        }
    }
    return t;
}
int Balance(Node*& T){
    if(!T){
        return 0;
    }
    int l_height = Balance(T->l)+1;
    int r_height = Balance(T->r)+1;
    T->avl = l_height-r_height;
    if(l_height>r_height){
        return l_height;
    }
    else{
        return r_height;
    }
}
  
void Previsit(Node* t,string s){
    cout<data<<"("<avl<<")"<<'\n';
    s+="    ";
    if(t->l == nullptr && t->r != nullptr){
        cout<"#"<
        Previsit(t->r,s);
    }
    if(t->l != nullptr && t->r == nullptr){
        Previsit(t->l,s);
        cout<"#"<
    }
    if(t->l != nullptr && t->r != nullptr){
        Previsit(t->l,s);
        Previsit(t->r,s);
    }
    return ;
}
signed main(){
    Node* T;
    int n;
    while(cin>>n){
        T = nullptr;
        string s = "";
        fer(i,0,n-1){
            int v;
            cin>>v;
            Insert(T,v);
        }
        Balance(T);
        Previsit(T,s);
    }
}

问题 D: 案例 1-1.1 二分查找

const int N=1e6+10;
int a[N];
signed main(){
    int n,x;
    cin>>n;
    fer(i,1,n) cin>>a[i];
    cin>>x;
    int l=1;int r=n;
    while(l
        int mid=(l+r)/2;
        if (a[mid]
            l=mid+1;
        }
        else r=mid;
    }
    if(a[l]==x)cout<'\n';
    else cout<<-1<<'\n';
}

问题 E: 进阶实验 1-3.1：两个有序序列的中位数

const int N = 1e6+10;
const int mod=998244353;
int a[N];
signed main(){
    int n;
    cin>>n;
    n=n*2;
    fer(i,1,n){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    cout<2];
}