Skip to content

11111: 【原1111】二哥学二叉树

题目

题目描述

author: Cheng Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1111

Description

二哥学了二叉树的顺序存储后，被下面一个问题难住了，于是他请你帮他解决。给你一个前序遍历和中序遍历，问顺序存储的数组是什么样子的。

Example

Input Format

第一行为前序遍历，第二行为中序遍历，节点个数不超过26.

Output Format

输出一行，表示顺序存储的数组，以空格隔开，NULL表示空节点，数组空间不超过1000个节点.

Sample Input

ABCD
BADC

Sample Output

A B C NULL NULL D

FineArtz's solution 

/* 二哥学二叉树 */
#include <iostream>
#include <cstring>
using namespace std;

char a[1005];
char dlr[30], ldr[30];

void restoreTree(char *dlr, char *ldr, int len, int root){
    if (len <= 0)
        return;
    char r = dlr[0];
    a[root] = r;
    int i = 0;
    while (ldr[i] != r)
        ++i;
    restoreTree(dlr + 1, ldr, i, root * 2);
    restoreTree(dlr + i + 1, ldr + i + 1, len - i - 1, root * 2 + 1);
}

int main(){
    cin >> dlr >> ldr;
    for (int i = 1; i <= 1004; ++i)
        a[i] = ' ';
    restoreTree(dlr, ldr, strlen(dlr), 1);
    int n = 1000;
    while (a[n] == ' ')
        --n;
    for (int i = 1; i <= n; ++i){
        if (a[i] == ' ')
            cout << "NULL ";
        else
            cout << a[i] << ' ';
    }
    cout << endl;
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cmath"
#include "cstring"
using namespace std;

//二叉树类
template <class T>
class myBinaryTree {
public:
    class node {
    public:
        T data;
        T *lchild=nullptr, *rchild=nullptr;
    };
    node *root=nullptr;

    //清空
    void clear() {
        clear(root);
    }

    void clear(node *p) {
        if (p == nullptr)
            return;
        clear(p->lchild);
        clear(p->rchild);
        delete p;
        p = nullptr;
    }

    //构造
    myBinaryTree(){}

    //析构
    ~myBinaryTree() {
        clear(root);
    }

    //判断是否非空
    bool empty() {
        return root == nullptr;
    }
};

char tdata[1009] = { 0 };
int dataSize = 0;

void createTree(int rootNum, char *tempData1,char *tempData2) {
    if (strlen(tempData1) == 0) return;
    char root = tempData1[0];
    tdata[rootNum] = root;
    dataSize = rootNum < dataSize ? dataSize : rootNum;
    char ldata1[50] = { 0 }, rdata1[50] = { 0 }, ldata2[50] = { 0 }, rdata2[50] = { 0 };
    int length = strlen(tempData1);
    bool flag = false;
    for (int i = 0,k=0; i < length; i++,k++) {
        if (tempData2[i] == root) {
            flag = true;
            k = -1;
        }
        else if (!flag) {
            ldata1[k] = tempData1[i + 1];
            ldata2[k] = tempData2[i];
        }
        else if (flag) {
            rdata1[k] = tempData1[i];
            rdata2[k] = tempData2[i];
        }
    }
    //递归
    createTree(rootNum * 2, ldata1, ldata2);
    createTree(rootNum * 2 + 1, rdata1, rdata2);
}

int main() {
    char preData[50], postData[50];
    cin >> preData >> postData;

    createTree(1, preData, postData);

    //输出
    cout << tdata[1];
    for (int i = 2; i <= dataSize; i++) {
        if (tdata[i] == 0)
            cout << " NULL";
        else
            cout << " " << tdata[i];
    }

    return 0;
}

Neight99's solution 

#include <cstring>
#include <iostream>

using namespace std;

char tree[100000] = {0}, Left[100000], Middle[100000];

char* subString(char* str, int l, int r) {
    if (r < l) {
        return NULL;
    }
    char* tmp = new char[100000];
    for (int i = l; i <= r; i++) {
        tmp[i - l] = str[i];
    }

    tmp[r + 1] = 0;

    return tmp;
}

void createTree(char* strLeft, char* strMiddle, int n) {
    int i = 0, j = 0;
    char *lltmp, *lmtmp, *rltmp, *rmtmp;
    if (strLeft == NULL) {
        return;
    }

    tree[n] = strLeft[0];

    if (strlen(strLeft) == 1 || strlen(strMiddle) == 1) {
        return;
    }

    for (i = 0; i < strlen(strMiddle); i++) {
        if (strMiddle[i] == strLeft[0]) {
            break;
        }
    }
    j = (i + 1 > strlen(strLeft)) ? (strlen(strLeft) - 1) : (i + 1);

    lltmp = subString(strLeft, 1, j - 1);
    lmtmp = subString(strMiddle, 0, i - 1);
    rltmp = subString(strLeft, j, strlen(strLeft) - 1);
    rmtmp = subString(strMiddle, i + 1, strlen(strMiddle) - 1);

    createTree(lltmp, lmtmp, 2 * n);
    createTree(rltmp, rmtmp, 2 * n + 1);

    delete[] lltmp;
    delete[] lmtmp;
    delete[] rltmp;
    delete[] rmtmp;
}

int main() {
    int i, j = 1, k = 0;
    cin >> Left >> Middle;
    i = strlen(Left);
    createTree(Left, Middle, 1);
    for (; k < i;) {
        if (tree[j] < 'A' || tree[j] > 'Z') {
            cout << "NULL ";
            j++;
        } else {
            cout << tree[j] << " ";
            j++;
            k++;
        }
    }

    return 0;
}

WashSwang's solution 

#include <iostream>
#include <cstring>
using namespace std;
char pre[100],in[100],ans[2000];
int maxn;
void dfs(int ps,int pe,int is,int it,int p)
{
    int root,leftlen,rightlen;
    for (root=is;root<it;++root){
        if (in[root]==pre[ps])
            break;
    }
    ans[p]=in[root];
    if (p>maxn) maxn=p;
    leftlen=root-is;
    if (leftlen>0) dfs(ps+1,ps+leftlen,is,root,p*2);
    rightlen=it-root-1;
    if (rightlen>0) dfs(ps+leftlen+1,pe,root+1,it,p*2+1);
}
int main() {
    cin>>pre;
    cin>>in;
    dfs(0,strlen(pre),0,strlen(in),1);
    for (int i=1;i<=maxn;++i)
        if (ans[i]) cout<<ans[i]<<" ";
        else cout<<"NULL ";
    return 0;
}

yyong119's solution 

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

char pre[27], mid[27];
char treeData[1001];

void buildTree(char *pstart, char *mstart, int len, int pos) {
    if (len > 0) {
        treeData[pos] = *pstart;
        int i;
        for (i = 0; i < len; ++i)
            if (mstart[i] == *pstart) break;
        buildTree(pstart + 1, mstart, i, pos * 2);
        buildTree(pstart + 1 + i, mstart + i + 1, len - i - 1, pos * 2 + 1);
    }
}

int main() {
    cin >> pre >> mid;
    int n = strlen(pre);
    buildTree(pre, mid, n, 1);
    int cnt = 0;
    for (int i = 1; i <= 1000 && cnt < n; ++i)
        if (treeData[i] != '\0') {
            cout << treeData[i] << " ";
            ++cnt;
        }
        else cout << "NULL ";
    return 0;
}

Zsi-r's solution 

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

void f(int root , int start ,int end,int count,char tree[],const char pre[],const char mid[]){
    int i;
    if (end < start)
        return; 
    else
        tree[count] = pre[root];

    for (i = start; i <= end;i++)
        if (mid[i]==pre[root])
            break;
    f(root + 1, start, i - 1, 2 * count, tree, pre, mid);
    f(root + 1 + i - start, i + 1, end, 2 * count + 1, tree, pre, mid);
}

int main()
{
    char pre[27], mid[27];
    char tree[1001];

    cin >> pre;
    cin >> mid;
    int len = strlen(pre);
    for (int k = 0; k<1000 ;k++)
    {
        tree[k] = '@';
    }

    f(0, 0, len - 1, 1, tree, pre, mid);

    int num = 0, i = 1;
    while (num!=len)
    {
        if (tree[i]=='@')
            cout << "NULL" << ' ';
        else{
            cout << tree[i] << ' ';
            num++;
        }
        i++;
    }

    return 0;
}