GPTL—练习集—006树的遍历

2018-06-17 22:59:03来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

#include<bits/stdc++.h>
using namespace std;

typedef int daTp;//datatype
typedef struct BTNode *position;
typedef position BTree;
const int MAXN=30;
struct BTNode
{
    daTp data;
    position lChild,rChild;
};
BTree build(daTp in[],daTp post[],int n)//利用中序和后序遍历生成二叉树
{
    BTree T=NULL;
    if(n)
    {
        T=new BTNode;
        T->data=post[n-1];
        int ln=0,rn=0;
        bool flag=true;
        daTp lin[MAXN],lpost[MAXN],rin[MAXN],rpost[MAXN];
        for(int i=0;i<n;i++)
        {
            if(in[i]==T->data)
            {
                flag=false;
                continue;
            }
            if(flag) lin[ln++]=in[i];
            else rin[rn++]=in[i];
        }
        for(int i=0,k=0;i<n;i++)
        {
            if(i<ln) lpost[i]=post[i];
            else rpost[k++]=post[i];
        }
        T->lChild=build(lin,lpost,ln);
        T->rChild=build(rin,rpost,rn);
    }
    return T;
}
void levelOrder(BTree T)//层序遍历
{
    if(!T) return;
    queue<BTree>qu;
    qu.push(T);
    BTree tr=T;
    while(!qu.empty())
    {
        tr=qu.front();
        qu.pop();
        cout<<(tr==T?"":" ")<<tr->data;
        if(tr->lChild) qu.push(tr->lChild);
        if(tr->rChild) qu.push(tr->rChild);
    }
}
int main()
{
    int n;
    daTp inOd[MAXN],postOd[MAXN];
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
            cin>>postOd[i];
        for(int i=0;i<n;i++)
            cin>>inOd[i];
        BTree T=build(inOd,postOd,n);
        levelOrder(T);
        cout<<endl;
    }
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:读书笔记 effective c++ Item 38 通过组合(composition)为 “has

下一篇:STL容器之优先队列(转)