一棵二叉树的先序遍历序列为ABDGEHKICFJ，中序遍历序列为GDBHKEIAFJC写出该树的后序遍历序列

根据先序遍历序列，我们可以得知根节点是A；根据中序遍历序列，我们可以将树分成左右子树，左子树的中序遍历序列为GDBHKE，对应的先序遍历序列为BDGEHK；右子树的中序遍历序列为IAFJC，对应的先序遍历序列为ICFJ。接下来，我们可以使用递归的方式，分别求出左右子树的后序遍历序列。

左子树的后序遍历序列为: GDBHKHEFJCA

右子树的后序遍历序列为: IJFCIA

因此，该树的后序遍历序列为: GDBHKHEFJCAIJFCIA

相关问题

二叉树的遍历推理 已知二叉树的先序遍历序列为 EIFCGABHDJ 中序遍历序列为 FIGCAEHDBJ 则后序遍历序列为

可以使用二叉树的构建和遍历算法来推理后序遍历序列。根据先序遍历序列的首个元素E，我们可以确定它是二叉树的根节点，然后在中序遍历序列中找到E的位置，可以将中序遍历序列分成左子树和右子树两部分。接下来，我们可以递归地重复上述步骤，找出左子树和右子树的根节点和子树的中序遍历序列，直到所有节点都被遍历过。最后，我们得到的后序遍历序列为：FGIACBHJDE。

1）由树的先序遍历序列和中序遍历序列创建一棵二叉树。（2）输出二叉树的后序遍历序列。测试数据：先序遍历序列：ABDGCEF中序遍历序列：DGBAECF

1. 由树的先序遍历序列和中序遍历序列创建一棵二叉树的步骤：
1.1. 如果先序遍历序列或中序遍历序列为空，则返回空树。
1.2. 取先序遍历序列的第一个元素作为根节点。
1.3. 在中序遍历序列中找到根节点的位置，将中序遍历序列分成左子树和右子树两部分。
1.4. 根据左子树和右子树的长度，在先序遍历序列中分出左子树和右子树的序列。
1.5. 递归地对左子树和右子树进行步骤1-4，分别得到左子树和右子树，将其作为根节点的左右子树。
1.6. 返回根节点。
2. 输出二叉树的后序遍历序列的步骤：
2.1. 如果根节点为空，则返回。
2.2. 递归地输出左子树的后序遍历序列。
2.3. 递归地输出右子树的后序遍历序列。
2.4. 输出根节点的值。
代码如下：

void CreateTree_HZ(BiTree &T, char hou[], int hl, int hr, char zhong[], int zl, int zr) {
    if (hl > hr || zl > zr) { // 先序遍历序列或中序遍历序列为空
        T = NULL;
        return;
    }
    T = new BiTNode; // 创建根节点
    T->data = hou[hr]; // 取先序遍历序列的最后一个元素作为根节点
    int i;
    for (i = zl; i <= zr; i++) { // 在中序遍历序列中找到根节点的位置
        if (zhong[i] == hou[hr]) {
            break;
        }
    }
    int left_len = i - zl; // 左子树的长度
    int right_len = zr - i; // 右子树的长度
    CreateTree_HZ(T->lchild, hou, hl, hl + left_len - 1, zhong, zl, i - 1); // 递归地对左子树进行步骤1-4
    CreateTree_HZ(T->rchild, hou, hl + left_len, hr - 1, zhong, i + 1, zr); // 递归地对右子树进行步骤1-4
}

void postorder(BiTree T) {
    if (T == NULL) { // 根节点为空
        return;
    }
    postorder(T->lchild); // 递归地输出左子树的后序遍历序列
    postorder(T->rchild); // 递归地输出右子树的后序遍历序列
    cout << T->data; // 输出根节点的值
}