欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥-ALGO-20-求先序排列

程序员文章站 2022-06-16 12:05:17
...

ACM模版

描述

蓝桥-ALGO-20-求先序排列

题解

不管是要输出先序还是后序,只要给定中序和另外一种遍历,就可以求出来。

根据各个序列之间的关系,很容易就能建树,然后再遍历一遍即可。

代码

#include <iostream>
#include <string>

using namespace std;

typedef struct BTNode
{
    char data;
    struct BTNode *lc, *rc;
} *BTree;

BTree root;
string m, l;

void BuildBTree(BTree &t, int ms, int me, int ls, int le)
{
    t = new BTNode;
    t->data = l[le];
    t->lc = t->rc = NULL;

    int pos = ms;

    while (m[pos] != l[le])
    {
        pos++;
    }
    int len = pos - ms;
    if (pos > ms)
    {
        BuildBTree(t->lc, ms, pos - 1, ls, ls + len - 1);
    }
    if (pos < me)
    {
        BuildBTree(t->rc, pos + 1, me, ls + len, le - 1);
    }
}

void PrintBTree(BTree p)
{
    if (p != NULL)
    {
        cout << p->data;
        PrintBTree(p->lc);
        PrintBTree(p->rc);
    }
}

int main(int argc, char* argv[])
{
    cin >> m;
    cin >> l;

    BuildBTree(root, 0, int(m.size() - 1), 0, int(l.size() - 1));

    PrintBTree(root);
    putchar(10);

    return 0;
}
相关标签: 树的遍历