一棵二叉树的结点若无子树，则可将其子树看作 “.”，输入时，按照前序序列的顺序输入该结点的内容。对 下图，其输入序列为 ABD..EH...CF.I..G..。 [输出] 若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。

输入序列为 ABD..EH...CF.I..G..

我们可以用一个栈来实现二叉树的后序遍历，具体方法如下：

1. 从前往后遍历输入序列，将每个结点压入栈中。同时，记录栈中当前结点的父节点（初始值为NULL）。

2. 如果遇到一个空结点，说明该结点没有左子树或右子树，此时需要将父节点指向栈顶结点（即当前结点的父节点），并弹出栈顶结点。

3. 如果遇到一个非空结点，将其作为栈顶结点的左子树（如果栈顶结点没有左子树）或右子树（如果栈顶结点已经有左子树），并更新父节点为当前结点。

4. 当所有结点都入栈后，从栈顶开始依次弹出结点，即可得到二叉树的后序遍历。

根据上述方法，对于输入序列 ABD..EH...CF.I..G..，可以得到如下二叉树：

        A
      /   \
     B     C
      \   / \
       D E   F
          \   \
           H   I
                \
                 G

然后，按照上述方法，我们可以得到二叉树的后序遍历为 DHEBIFGCA。

因此，输出结果为 DHEBIFGCA。

相关问题

证明:已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树

要证明已知一棵二叉树的前序序列 (Preorder) 和中序序列 (Inorder) 可以唯一确定该二叉树，我们可以采用分步分析法。

**步骤1：前序序列中的根节点**
前序序列的第一个元素通常是根节点，因为它先访问根再遍历左子树和右子树。因此，通过前序序列，我们可以直接找到根节点。

**步骤2：寻找根节点在中序序列中的位置**
在中序序列中，由于左子树会先于根节点被访问，所以我们可以从中序序列的一开始查找第一个大于根节点的元素，这个元素的位置就是根节点的左子树在中序序列中的结束位置。

**步骤3：划分左右子树**
接着，我们用找到的位置将中序序列分为两部分：左边的部分包含左子树的所有节点，右边的部分则包含根节点和右子树。因为中序序列是递增的，所以这部分很容易确定。

**步骤4：递归构建子树**
现在我们可以对左右子树分别进行同样的操作，即找出它们的前序和中序序列。根据这两个序列，可以继续划分出每个子树的结构，直到所有子树都被构建出来。

**结论：唯一性**
由于前序和中序序列包含了关于节点访问顺序的完整信息，而且按照特定规则一步步地重建了整个树的过程是唯一的，所以给定一棵二叉树的前序和中序序列，能够唯一确定这棵树的结构。

c语言交换一个二叉树结点的左右子树

在C语言中，交换一个二叉树节点的左右子树通常涉及到对指针的巧妙操作。对于非空的二叉树节点`node`，你可以通过临时变量存储原左子节点，然后将左子节点指向原右子节点，最后将右子节点指向临时存储的左子节点。这里是一个简单的示例：

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

void swapLeftAndRight(struct TreeNode *node) {
    if (node == NULL || node->left == NULL || node->right == NULL) {
        return; // 如果节点为空或者其中一个子节点为空，无需交换
    }
    
    // 创建临时存储节点
    struct TreeNode* temp = node->left;
    
    // 修改节点的左右子节点
    node->left = node->right;
    node->right = temp;
}

这个函数接受一个二叉树节点作为输入，如果节点及其子节点都存在，则会完成左右子节点的交换。注意，这个操作假设二叉树的结构是有效的，并且不会改变其他部分的结构。