23-5-23--二叉树--二叉树的建立的模板

daniel350-wang / 2023-06-01 / 原文

#include <iostream>
#include <queue>
using namespace std;

typedef struct tr* ptree;
typedef struct tr {
    struct tr *lchild;
    struct tr *rchild;
    int date;
}tree;


//前序中序创建二叉树 
ptree premid(int pre[],int mid[],int size)
{
    if(size<=0)
    {
        return NULL;
    }
    int i;
    for(i=0;i<size;i++)
    {
        if(mid[i]==pre[0])
        {
            //cout<<i<<endl;
            break;    
        }
    }
    
    tree * t=new tree;
    t->date  = pre[0];
    t->lchild  = premid(pre+1,mid,i );
    t->rchild = premid(pre+i+1,mid+i+1,size-i-1);
    return t;
}

//后序中序创建二叉树
ptree  postmid(int post[],int mid[],int size)
{
    if(size<=0)
    {
        return NULL;
    }
    int i;
    for( i=0;i<size;i++)
    {
        if(mid[i]==post[size-1])
        {
            //cout<<i<<' ';
            break;
        }
    }
    //int x=i;
    tree* t=new tree;
    t->date = post[size-1];
    //cout<<x<<' ';
    t->lchild =postmid(post,mid,i);
    t->rchild = postmid(post+i,mid+i+1,size-i-1);
    return t;
}


//后序遍历 
void postround(ptree t)
{
    
    if(t==NULL)
        return;
    postround(t->lchild );
    postround(t->rchild );
    cout<<t->date <<' ';
}

void midround(ptree t)
{
    
    if(t==NULL)
        return;
    postround(t->lchild );
    cout<<t->date <<' ';
    postround(t->rchild );
    
}


//前序遍历
void preround(ptree t) 
{
    if(t==NULL)
        return;
    cout<<t->date<<' ' ;
    preround(t->lchild );
    preround(t->rchild );
}


//层序遍历 
void floorprint(ptree t)
{
    queue <ptree> q;
    if(t!=NULL)
    {
        q.push(t); 
    }
    while(q.empty()==false)
    {
        ptree node=q.front() ;
        cout<< node->date <<' ';
        
        if(node->lchild !=NULL)
        {
            q.push(node->lchild ); 
        }
        
        if(node->rchild !=NULL)
        {
            q.push(node->rchild ); 
        }
        q.pop() ;
    }
    
    
}

int main()
{
    int pre[1000]={0},mid[1000]={0},post[1000]={0},n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>post[i];
    }
    
    for(int i=0;i<n;i++)
    {
        cin>>mid[i];
    }
    ptree head=postmid(post,mid,n);
    floorprint(head);
    
    
}