数据结构课程期末总结二

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int  num=0;
struct donser
{
    int data;
    donser*lson;
    donser*rson;
};
donser *root;
donser *creat(int *a,int *b,int n)//da下标从i开始依次找  db下标从j开始向后扫  n向后扫几个
{
    donser *ss;
    for(int k=0;k<n;k++)
    {
        if(b[k]==a[0])
        {
            ss=new donser;
            ss->data=b[k];
            ss->lson=creat(a+1,b,k);
            ss->rson=creat(a+k+1,b+1+k,n-k-1);
            return ss;
        }
    }
    return NULL;
}

void solve(donser *r)
{
    if(r!=NULL)
    {
        solve(r->lson);
        solve(r->rson);
        if(r!=root) cout<<r->data<<" ";
        else cout<<r->data<<endl;
    }
}

int main()
{
    int  da[1010],db[1010];//前中
    while(~scanf("%d",&num))
    {
        for(int i=0;i<num;i++) {scanf("%d",&da[i]);}
        for(int i=0;i<num;i++) {scanf("%d",&db[i]);}
        root=creat(da,db,num);
        solve(root);
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ld[100010],rd[100010],a,num,root,i;
void build(int root,int al)
{
    if(al>root)
    {
        if(rd[root]==-1)
        {
            rd[root]=al;
            //cout<<"al:"<<al<<" r root:"<<root<<endl;
        }
        else build(rd[root],al);
    }
    else
    {
        if(ld[root]==-1)
        {
            ld[root]=al;
            //cout<<"al:"<<al<<" l root:"<<root<<endl;
        }
        else build(ld[root],al);
    }
}

void solve(int root)
{
    if(ld[root]!=-1)
    {
        cout<<" "<<ld[root];
        solve(ld[root]);
    }
    if(rd[root]!=-1)
    {
        cout<<" "<<rd[root];
        solve(rd[root]);
    }
    else return;
}

int main()
{
    while(~scanf("%d",&num))
    {
        memset(ld,-1,sizeof(ld));
        memset(rd,-1,sizeof(rd));
        for(i=1;i<=num;i++)
        {
            scanf("%d",&a);
            if(i==1){root=a;}
            else build(root,a);
        }
        cout<<root;
        solve(root);
        cout<<endl;
    }
    return 0;
}