平武建站

还原二叉树（求高度并输出二叉树）-创新互联

目录

为卫辉等地区用户提供了全套网页设计制作服务，及卫辉网站建设行业解决方案。主营业务为成都网站建设、网站建设、卫辉网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

举一个例子：

求大高度

先序遍历

树的层序遍历

解析：

在还原二叉树的过程中，我们必须明确中序遍历的结果才能进行

举一个例子：

已知后序遍历结果和中序遍历结果：

（依据后序从后往前的结果为根节点开始划分）

例题： 

题目详情 - 7-1 还原二叉树 (pintia.cn)

（前序和中序）

求大高度
#includeusing namespace std;

const int N=55;
char pre[N],inoder[N];
int n,h;

typedef struct Binode{
    int elem;
    Binode*lchild,*rchild;
}Binode;

Binode*creatheap(char pre[],char in[],int N){
    if(N<=0)
    return NULL;
    Binode*T1=new Binode;
    int i=0;
    T1->elem=pre[0];
    while(ilchild=creatheap(pre+1,in,i);
    T1->rchild=creatheap(pre+i+1,in+i+1,N-i-1);
    return T1;
}

int  heap(Binode*T){
     if(T==NULL) return 0; 
    else  
    { 
        int m = heap(T->lchild); 
        int n = heap(T->rchild); 
        return (m >n) ? (m+1) : (n+1);  
    } 
}

int main(){
    cin>>n;
    cin>>pre>>inoder;
    Binode*T;
    T=creatheap(pre,inoder,n);
    h=heap(T);
    cout<

例题： 

题目详情 - 7-2 根据后序和中序遍历输出先序遍历 (pintia.cn)

先序遍历
#includeusing namespace std;

const int N=35;
int post[N],inoder[N];
int n;

typedef struct Binode{
    int elem;
    Binode*lchild,*rchild;
}Binode;

Binode*creatheap(int po[],int in[],int N){
    if(N==0)
        return NULL;
    int i=0;
    //Binode*T1=new Binode;
    Binode*T1=(Binode*)malloc(sizeof(Binode));
    T1->elem=po[N-1];
    while(ielem){
            break;
        }
        i++;
    }
    T1->lchild=creatheap(po,in,i);
    T1->rchild=creatheap(po+i,in+i+1,N-i-1);
    return T1;
}

void printheap(Binode*T){
    if(T){
        cout<<' '<elem;
        printheap(T->lchild);
        printheap(T->rchild);
    }
}

int main(){
    cin>>n;
    Binode*T;
    for(int i=0;i>post[i];
    for(int i=0;i>inoder[i];
    cout<<"Preorder:";
    T=creatheap(post,inoder,n);
    printheap(T);
}

例题：

题目详情 - 7-3 树的遍历 (pintia.cn)

树的层序遍历 解析：

通过一个队列对二叉树进行遍历，与广度优先搜索极为相似

#includeusing namespace std;

const int N=35;
int post[N],inoder[N];
int n;

typedef struct BiNode{
    int elem;
    BiNode*lchild,*rchild;
}BiNode;

BiNode*creatheap(int p[],int in[],int N){
    if(N<=0)
        return NULL;
    BiNode*T1=new BiNode;
    T1->elem=p[N-1];
    int i=0;
    while(ielem==in[i])
        break;
        i++;
    }
    T1->lchild=creatheap(p,in,i);
    T1->rchild=creatheap(p+i,in+i+1,N-i-1);
    return T1;
}

void printfheap(BiNode*T2){
    queueque;
    que.push(T2);
    int i=0;
    while(!que.empty()){
        auto p=que.front();
        if(i==0)
        cout<elem;
        else
        cout<<' '<elem;
        que.pop();
        if(p->lchild!=NULL)que.push(p->lchild);
        if(p->rchild!=NULL)que.push(p->rchild);
        i++;
    }
}

int main(){
    BiNode*T;
    cin>>n;
    for(int i=0;i>post[i];
    for(int i=0;i>inoder[i];
    T=creatheap(post,inoder,n);
    printfheap(T);
}

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


当前文章：还原二叉树（求高度并输出二叉树）-创新互联
转载来源：http://pwwzsj.com/article/cogjcj.html

其他资讯