专栏首页用户6093955的专栏数据结构期末复习——还原二叉树(根据先序和中序遍历输出先序遍历)

数据结构期末复习——还原二叉树(根据先序和中序遍历输出先序遍历)

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<algorithm>
#include<vector>
#include<cstring>
#include<sstream>
#include<cmath>
using namespace std;
const int maxn = 100000;
char pre[maxn];     /**先序遍历后对应的串*/
char ino[maxn];     /**中序遍历后对应的串*/
//char post[maxn];    /**后序遍历后对应的串*/
typedef struct BiNode
{
    char data;
    BiNode *Left;
    BiNode *Right;
}BiNode, *BiTree;

BiTree build(char *pre, char *ino, int len)
{
    if(len <= 0)
        return NULL;
    BiTree T = new BiNode;
    T->data = *pre;
    char *root = pre;
    char *p = ino;
    while(p)
    {
        //找到根节点在中序中对应的位置
        if(*p == *root)
            break;
        ++p;
    }
    //左子树的长度
    int left_len = p - ino;
    T->Left = build(pre + 1, ino, left_len);
    T->Right = build(pre + 1 + left_len, p + 1, len - left_len - 1);
    return T;
}

//后序遍历
void postOrder(BiTree T)
{
    if(T)
    {
        postOrder(T->Left);
        postOrder(T->Right);
        printf(" %c", T->data);
    }
}


int main()
{
    /**N指二叉树节点的个数*/
    int N;
    scanf("%d %s %s", &N, pre, ino);
    BiTree T = build(pre, ino, N);
    printf("postorder:");
    postOrder(T);
    printf("\n");
}

参考博客:https://blog.csdn.net/qq_37708702/article/details/79644068

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构期末复习——还原二叉树(根据中序和后序遍历输出先序遍历)

    参考博客:https://blog.csdn.net/qq_37708702/article/details/79644936

    _DIY
  • 【 BowWow and the Timetable CodeForces - 1204A 】【思维】

    题目链接 可以发现 十进制4 对应 二进制100 十进制16 对应 二进制10000 十进制64 对应 二进制1000000 可以发现每多两个零,4的...

    _DIY
  • 【改革春风吹满地 HDU - 2036 】【计算几何-----利用叉积计算多边形的面积】

    我们都知道计算三角形的面积时可以用两个邻边对应向量积(叉积)的绝对值的一半表示,那么同样,对于多边形,我们可以以多边形上的一个点为源点,作过该点并且过多边形其他...

    _DIY
  • 谷歌同声翻译Translatotron原理

    作为中国人,学好英语这件事从小学开始就让人苦恼,近些年随着AI的快速发展,语言差异是否会缩小甚至被消灭成了热门话题。在5月15日,谷歌AI在博客平台发出一篇文章...

    平也
  • Android4.4运行过程中闪退java.lang.NoClassDefFoundError

    上周五项目测试时发现一个奇怪的Bug,项目中依赖了一个第三方框架,但是在android4.0-4.4.4之间的系统中运行会直接闪退,抛出错误异常为java.la...

    萬物並作吾以觀復
  • VR开发快速入门小诀窍——选对一款VR开发工具让你事半功倍

    VRPinea
  • 微信小程序云开发 初学者入门教程一

    本教程适合刚刚入门的小白,云开发为开发者提供完整的云端支持,弱化后端和运维概念,无需搭建服务器,使用平台提供的 API 进行核心业务开发,即可实现快速上线和迭代...

    祈澈菇凉
  • 同声传译被攻陷!谷歌发布Translatotron直接语音翻译系统

    说不同语言的人更容易地、直接地相互交流,这是语音到语音的翻译系统(Speech-to-speech translation)的目的,这样的系统在过去几十年里取得...

    新智元
  • LeetCode: 221_Maximal Square | 二维0-1矩阵中计算包含1的最大正方形的面积 | Medium

    题目: Given a 2D binary matrix filled with 0's and 1's, find the largest square co...

    CloudDeveloper
  • Python 爬虫使用Requests获取网页文本内容中文乱码

    爬取的网页编码与我们爬取编码方式不一致造成的。如果爬取的网页编码方式为utf8,而我们爬取后程序使用ISO-8859-1编码方式进行编码并输出,这会引起乱码。如...

    smartsi

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动