已知树的前序、中序，求后序的c++实现&已知树的后序、中序，求前序的c++实现

#include"iostream"

using namespace std;

int pre[30];

int in[30];

int post[30];

int indexOfRootIn(int start,int stop,int root){

    for(int j=start;j<=stop;j++){

        if(in[j]==root){

            return j;

        }

    }

    return -1;

}

void postOrder(int pre_start,int pre_end,int in_start,int in_end,int length){

    if(length==0)

        return;

    if(length==1){

        cout<<in[in_start]<<endl;

        return;

    }

    int root = pre[pre_start];

    int index = indexOfRootIn(in_start,in_end,root);

    int len1=(index-in_start);

    int len2=(in_end-index);

    postOrder(pre_start+1,pre_start+index,in_start,index-1,len1);

    postOrder(pre_start+index+1,pre_end,index+1,in_end,len2);

    cout<<root<<" "<<endl;

}

void preOrder(int post_start,int post_end,int in_start,int in_end,int length){

    if(length==0)

        return;

    if(length==1){

        cout<<in[in_start]<<endl;

        return;

    }

    int root = post[post_end];

    int index = indexOfRootIn(in_start,in_end,root);

    int len1= index-in_start;

    int len2= in_end-index;

    cout<<root<<" "<<endl;

    preOrder(post_start,post_start+index-1,in_start,index-1,len1);

    preOrder(post_start+index,post_end-1,index+1,in_end,len2);

}

int main(){

    int N;

    cin>>N;

    for(int i=0;i<N;i++){

        cin>>post[i];

    }

    for(int i=0;i<N;i++){

        cin>>in[i];

    }

    preOrder(0,N-1,0,N-1,N);

    return 0;

}

巴特西

已知树的前序、中序，求后序的c++实现&已知树的后序、中序，求前序的c++实现

最新文章

热门文章