首页 / 算法 / 二叉树算法：中序、后序推导先序（数组递归实现）

二叉树算法：中序、后序推导先序（数组递归实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树算法：中序、后序推导先序（数组递归实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含968字，纯文字阅读大概需要2分钟。

内容图文

中根序列和后根序列重建二叉树

描述

我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序 列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。

用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树

技术分享

中根序列是9 5 32 67

后根序列9 32 67 5

前根序列5 9 67 32

先读入一个数n代表中序和后序均有n个元素。

接着输入中序序列，在输入后序序列。

输出先序序列。

输入：

4

9 5 32 67

9 32 67 5

输出：

5 9 67 32

#include <stdio.h>
#include <string.h>

void build(int len, int *s1, int *s2, int *s)
{
    int p;
    int i;
    if(len<=0)
        return;
    else{
        for(i=0; i<len; i++){
            if(s1[i]==s2[len-1]){
                p = i;
            }
        }
        build(p, s1, s2, s+1);
        build(len-p-1, s1+p+1, s2+p, s+p+1);
        s[0] = s2[len-1];
    }
}

int main()
{
    int i;

    int s1[1000], s2[1000], s3[1000];
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        for(i=0; i<n; i++){
            scanf("%d", &s1[i] );
        }
        for(i=0; i<n; i++){
            scanf("%d", &s2[i] );
        }
        build(n, s1, s2, s3 );

        for(i=0; i<n; i++){
            printf("%d%c", s3[i], i==n-1?‘\n‘:‘ ‘ );
        }
    }
    return 0;
}

 

原文：http://www.cnblogs.com/yspworld/p/4460986.html

内容总结

以上是互联网集市为您收集整理的二叉树算法：中序、后序推导先序（数组递归实现）全部内容，希望文章能够帮你解决二叉树算法：中序、后序推导先序（数组递归实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1098132.html

来源：【匿名】