一棵二叉树的结点若无子树，则可将其子树看作 “.”，输入时，按照前序序列的顺序输入该结点的内容。对 下图，其输入序列为 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。

相关问题

将一棵树转成二叉树，根结点没有左子树。

将一棵树转成二叉树，可以按照以下步骤进行：

1. 将树的根结点作为二叉树的根结点，但是不作为二叉树的左子树。

2. 对于树中的每个结点，将其第一个子结点作为其左子结点，将其兄弟结点作为其右子结点。

3. 对于树中的每个结点，如果其没有左子结点，则将其右子结点作为其左子结点。

4. 对于树中的每个结点，如果其没有右子结点，则将其左子结点作为其右子结点。

这样就可以将一棵树转成二叉树，其中根结点没有左子树。

一棵非空二叉树，若先序遍历与后序遍历的序列相反，则该二叉树所有结点均无左孩子。

这个说法是正确的。如果一棵二叉树的先序遍历和后序遍历序列恰好相反，那么可以推断出该二叉树所有结点均无左孩子。因为先序遍历是先遍历根结点，再遍历左子树和右子树，而后序遍历是先遍历左子树和右子树，再遍历根结点。如果一个结点有左孩子，那么在先序遍历序列中，它的左孩子会被先遍历，而在后序遍历序列中，它的左孩子会被后遍历，这两个序列不可能相反。因此，如果先序遍历和后序遍历序列相反，那么所有结点都没有左孩子。