数据结构二叉树

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MaxSize 1000

int isIn(char ch, char* str, int n) {

    for (int i = 0; i < n; i++) {

        if (str[i] == ch) return 1;

    }

    return 0;

}

void extractLevel(char* level, int levelLen, char* set, int setLen, char* result) {

    int idx = 0;

    for (int i = 0; i < levelLen; i++) {

        if (isIn(level[i], set, setLen)) {

            result[idx++] = level[i];

        }

    }

    result[idx] = '\0';

}

void PreOrderFromInAndLevel(char* in, char* level, int n) {

    if (n <= 0) return;

    char root = level[0];

    printf("%c", root);

    int k;

    for (k = 0; k < n; k++) {

        if (in[k] == root) break;

    }

    if (k > 0) {

        char leftLevel[MaxSize];

        extractLevel(level + 1, n - 1, in, k, leftLevel);

        PreOrderFromInAndLevel(in, leftLevel, k);

    }

    if (n - k - 1 > 0) {

        char rightLevel[MaxSize];

        extractLevel(level + 1, n - 1, in + k + 1, n - k - 1, rightLevel);

        PreOrderFromInAndLevel(in + k + 1, rightLevel, n - k - 1);

    }

}

int main() {

    char in[MaxSize], level[MaxSize];

    scanf("%s", in);

    scanf("%s", level);

    int n = strlen(in);

    PreOrderFromInAndLevel(in, level, n);

    printf("\n");

    return 0;

}