C语言给出一个按照“扩展遍历序列”的扩展后序遍历序列字符串

，请问如何构建该二叉树？

回答：

构建扩展遍历序列的二叉树需要用到后序遍历的性质：

在后序遍历中，最后一个元素为根节点。

在扩展遍历序列中，如果一个节点有左/右子树，则其后面必定跟着左/右孩子的值和一个'+'。

可以根据这些性质来构建二叉树：

1. 从扩展遍历序列的末尾找到根节点。

2. 根据性质 1，可以将扩展遍历序列的末尾元素弹出，作为根节点。

3. 在扩展遍历序列中，找到第一个出现 “元素 值 +” 的节点，该节点的子串即为左子树的扩展遍历序列。

4. 根据性质 3，可以将左子树的扩展遍历序列从原序列中分离出来，递归构建出左子树，将左子树挂在根节点的左侧。

5. 剩下的扩展遍历序列即为右子树的扩展遍历序列，递归构建出右子树，将右子树挂在根节点的右侧。

6. 递归结束条件为扩展遍历序列为空。

下面是一个示例代码，构建扩展遍历序列为 "8+4+2+6+5+7+12+10+9+" 的二叉树：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 100

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 根据扩展遍历序列构建二叉树
TreeNode* buildExtendedPostorderTree(char* extended_postorder) {
    // 如果扩展遍历序列为空，则返回 NULL
    if (extended_postorder[0] == '\0') {
        return NULL;
    }

    // 创建根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = atoi(extended_postorder + strlen(extended_postorder) - 2);
    root->left = NULL;
    root->right = NULL;

    // 查找左子树的扩展遍历序列和右子树的扩展遍历序列
    int index = 0;
    while (extended_postorder[index] != ' ') {
        index++;
    }
    char* left_str = (char*)malloc(index + 1);
    strncpy(left_str, extended_postorder, index);
    left_str[index] = '\0';
    char* right_str = extended_postorder + index + 1;
    // 如果左子树的扩展遍历序列不为空，则递归构建左子树
    if (left_str[0] != '\0') {
        root->left = buildExtendedPostorderTree(left_str);
    }
    // 如果右子树的扩展遍历序列不为空，则递归构建右子树
    if (right_str[0] != '\0') {
        root->right = buildExtendedPostorderTree(right_str);
    }

    // 释放内存
    free(left_str);

    return root;
}

// 后序遍历打印二叉树
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}

int main() {
    char extended_postorder[MAX_NODES];
    scanf("%s", extended_postorder);
    // 构建扩展遍历序列的二叉树
    TreeNode* root = buildExtendedPostorderTree(extended_postorder);
    // 后序遍历打印二叉树
    postorderTraversal(root);
    printf("\n");
    return 0;
}

输出结果为: 2 5 7 6 4 9 10 12 8