题解 | #二叉树遍历#C语言

#include <stdlib.h> // 利用malloc()
#include <stdio.h>
typedef struct Node {
    char data;
    struct Node* left, * right;
} Node, * BTree;

// 递归生成树
Node* Partition(char A[], char B[], int LA, int RA, int LB, int RB) {
    // A为前序遍历，B为后续遍历，L为左边界，R为右边界
    if (LA == RA) { // 叶结点
        Node* p = (Node*)malloc(sizeof(Node));
        p->data = A[LA];
        p->left = NULL;
        p->right = NULL;
        return p;
    }
  
	// 非叶结点
    char root = A[LA];
    int i = 0;
    while (B[i] != root)    i++;
    // B中在i左边都为左子树，右边都为右子树；
    Node* LNode = NULL;
    Node* RNode = NULL;
    if (i > LB) LNode = Partition(A, B,  LA + 1, LA + i - LB, LB,i - 1); // 递归处理左子树
    if (i < RB) RNode = Partition(A, B,  LA + i - LB + 1, RA, i + 1,RB); // 递归处理右子树
    Node* ROOT = (Node*)malloc(sizeof(Node));
    ROOT->data = root;
    ROOT->left = LNode;
    ROOT->right = RNode;
    return ROOT;
}

// 后序遍历
void LastPrint(BTree T) {
    if (T->left)    LastPrint(T->left);
    if (T->right)   LastPrint(T->right);
    printf("%c", T->data);
}

int main() {
    char a[30], b[30], c[30];
    while (scanf("%s %s", a, b) != EOF) { // 注意 while 处理多个 case
      // 统计字符串长度
	  int k = 0;
        while (a[k] != '\0') { //注意要k-1
            k++;
        }
	  
	// 生成一棵树T
        BTree T = (Node*)malloc(sizeof(Node));
        T = Partition(a, b, 0, k - 1, 0, k - 1);//递归划分，并生成一棵二叉树
	  
	// 后序遍历
        LastPrint(T);
        printf("\n");
    }
    return 0;

}