北京化工大学数据结构第十二次作业（计算机类）（2022.12.1）-创新互联

A 二叉排序树 - 文本输出

构造二叉排序树之后先序遍历输出，要注意如何处理特殊的输出格式。

#includeusing namespace std;
typedef struct {
    int key;
    int otherinfo;
}ElemType;
typedef struct BSTNode {
    ElemType data;
    struct BSTNode* lchild, * rchild;
}BSTNode,*BSTree;

void InsertBST(BSTree& T, ElemType e) {
    if (!T) {
        BSTNode* S = new BSTNode;
        S->data = e;
        S->lchild = S->rchild = NULL;
        T = S;
    }
    else if (e.key< T->data.key)
    InsertBST(T->lchild, e);
    else if (e.key >T->data.key)
    InsertBST(T->rchild, e);
}
void CreatBST(BSTree& T) 
{
    T = NULL;
    ElemType e;
    int n;
    cin >>n;
    while(n--){
        cin >>e.key;
        InsertBST(T, e);
    }
}
string s="";
void InorderTree(BSTree T) {
    cout<data.key<< " ";
        cout<< endl;
        if(T->lchild || T->rchild)
        {
            s+="    ";
            InorderTree(T->lchild);
            InorderTree(T->rchild);
            for(int i=0;i<4;i++) s.pop_back();
        }
    }
    else
    {
        cout<<"#"<

B 销售排行榜

结构体把数据都储存进去，然后直接排序即可。第一遍按name排序把相同name的合并，第二遍按题意排序得到结果。

#includeusing namespace std;
struct shopg
{
    string name;
    long long num;
    long long price;
}goods[100010];
bool pd1(shopg shopg1,shopg shopg2)
{
    if(shopg1.nameshopg2.num) return true;
    else if(shopg1.num==shopg2.num && shopg1.name>s)
    {
        goods[i].name=s;
        cin>>goods[i].num;
        cin>>goods[i].price;
        goods[i].price*=goods[i].num;
        cin>>s;
        i++;
    }
    sort(goods,goods+i,pd1);
    for(int j=0;j

C 二叉排序树-平衡因子

在A题的基础上多维护每个节点的左大深度和右大深度。

平衡因子为左大深度-右大深度。

#includeusing namespace std;
typedef struct {
    int key;
    int leftbal;
    int rightbal;
}ElemType;
int cc;
typedef struct BSTNode {
    ElemType data;
    struct BSTNode* lchild, * rchild;
}BSTNode,*BSTree;
void InsertBST(BSTree& T, ElemType e) {
    if (!T)
    {    
        BSTNode* S = new BSTNode;
        e.leftbal=cc;
        e.rightbal=cc;
        S->data = e;
        S->lchild = S->rchild = NULL;
        T = S;
    }
    else if (e.key< T->data.key)
    {
        cc++;
        InsertBST(T->lchild, e);
        T->data.leftbal=max(T->data.leftbal,cc);
    }
    else if (e.key >T->data.key)
    {
        cc++;
        InsertBST(T->rchild, e);
        T->data.rightbal=max(T->data.rightbal,cc);
    }
}
void CreatBST(BSTree& T) {
   
    T = NULL;
    ElemType e;
    int n;
    cin >>n;
    while(n--){
        cin >>e.key;
        e.leftbal=0;
        e.rightbal=0;
        cc=0;
        InsertBST(T, e);
    }
}
string s="";
void InorderTree(BSTree T) {
    cout<data.key<< "("<data.leftbal-T->data.rightbal<<")";
        cout<< endl;
        if(T->lchild || T->rchild)
        {
            s+="    ";
            InorderTree(T->lchild);
            InorderTree(T->rchild);
            for(int i=0;i<4;i++) s.pop_back();
        }
    }
    else
    {
        cout<<"#"<

D 案例 1-1.1 二分查找

建议使用C++的二分查找函数lower_bound（）

#includeusing namespace std;
int main()
{
    int n,t;
    cin>>n;
    int a[n];
    for(int i=0;i>a[i];
    cin>>t;
    auto g=lower_bound(a,a+n,t);
    if(*g!=t) cout<<-1<

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

不知道这题出在这一次作业的意义（（（（

#includeusing namespace std;
int main()
{
    int n;
    cin>>n;
    int a[2*n];
    for(int i=0;i<2*n;i++) cin>>a[i];
    sort(a,a+2*n);
    cout<

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧