C语言数据结构之二叉树求二叉树的先序遍历

末蓝、 2022-05-30 22:22 179阅读 0赞

求二叉树的先序遍历  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历  
Input

输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。  
Output

输出二叉树的先序遍历序列  
Example Input

2  
dbgeafc  
dgebfca  
lnixu  
linux  
Example Output

abdegcf  
xnliu

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        char data;
        struct node *l, *r;
    };
    char s1[60], s2[60];
    struct node *creat(int n, char *s1, char *s2)
    {
        int i;
        if(n == 0)
            return NULL;
        struct node *root;
        root = (struct node*)malloc(sizeof(struct node));
        root -> data = s2[n - 1];
        for(i = 0; i < n; i++)
        {
            if(s1[i] == s2[n - 1])
                break;
        }
        root -> l = creat(i, s1, s2);
        root -> r = creat(n - i - 1, s1 + i + 1, s2 + i);
        return root;
    }
    void xianxv(struct node *root)
    {
        if(root)
        {
            printf("%c", root -> data);
            xianxv(root -> l);
            xianxv(root -> r);
        }
    
    }
    int main()
    {
        int t, n;
        scanf("%d", &t);
        while(t--)
        {
            scanf("%s %s", s1, s2);
            n = strlen(s1);
            struct node *root;
            root = creat(n, s1, s2);
            xianxv(root);
            printf("\n");
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关求二叉树的先序遍历

求二叉树的先序遍历 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Prob

亦凉/ 2024年02月18日 22:31/ 0 赞/ 49 阅读

相关【数据结构】二叉树的先序遍历

关于先序遍历的详细介绍参见前面关于中序遍历的博文，这里仅给出先序遍历的递归及非递归的代码实现。 ![这里写图片描述][SouthEast] 如图二叉树，其先序遍历结果为

古城微笑少年丶/ 2022年09月30日 13:52/ 0 赞/ 182 阅读

相关数据结构 -- 二叉树先序遍历

二叉树先序遍历的两种方法： 1.递归遍历 2.利用链栈实现非递归遍历以下代码在vs2010 测试通过： include "stdafx.h" i

﹏ヽ暗。殇╰゛Y/ 2022年08月25日 09:00/ 0 赞/ 182 阅读

相关求二叉树的先序遍历

求二叉树的先序遍历 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述已知一棵二叉树的

柔光的暖阳◎/ 2022年08月18日 02:25/ 0 赞/ 146 阅读

相关求二叉树的先序遍历

Problem Description 已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历 Input 输入数据有多组，第一行是一个整数t (t<1000)，代表有

╰半夏微凉°/ 2022年07月12日 07:08/ 0 赞/ 171 阅读

相关求二叉树的先序遍历

Problem Description 已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历 Input 输入数据有多组，第一行是一个整数t (t<1000)

素颜马尾好姑娘i/ 2022年07月12日 02:10/ 0 赞/ 159 阅读

相关二叉树先序遍历

前两天面试，看见了个笔试题，关于二叉树的，今天算是把自己的一点理解写下来吧。今天看网文，才想起来，二叉树的先序遍历、中序遍历、后序遍历，遍历顺序都是

向右看齐/ 2022年07月10日 10:57/ 0 赞/ 208 阅读

相关 C语言数据结构之二叉树求二叉树的先序遍历

求二叉树的先序遍历 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Descri

末蓝、/ 2022年05月30日 22:22/ 0 赞/ 180 阅读

相关求二叉树的先序遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 已

╰+攻爆jí腚メ/ 2022年05月14日 03:40/ 0 赞/ 144 阅读

相关二叉树之先序遍历

　　二叉树不同于列表、链表、栈、队列这些线性结构，也不同于图这种非线性结构，它属于半线性结构。我们在搞二叉树的时候不要从轮子造起，而要善于引用此前的工作成果，转化成以前已经玩烂

墨蓝/ 2021年11月09日 00:32/ 0 赞/ 311 阅读