构造二叉树给定后命令

Question

如果只给出信息是后序遍历，如何构建二叉树。在谷歌上搜索了主题后，我明白在这种情况下不可能有唯一的构造二叉树。但是如果给定整数，则很容易根据小于或大于属性创建BT。但是，如果我们有字母表，那么我无法弄清楚我们根据什么制作父节点的左节点或右节点。这是我试图解决的问题.

Q） 二叉树的后序遍历是DEBFCA。找出前序遍历吗？

选项：
（A）ABFCDE

正确答案是:C

有人能解释一下我们如何回答吗？

我发现这个答案 https://www.quora.com/If-the-post-order-traversal-of-a-binary-tree-is-DEBFCA-how-can-I-find-out-the-pre-order-traversal/answer/Eugene-Yarovoi?srid=zy7j 非常有用，但第三步开始我不明白事情是如何发生的。感谢您抽出宝贵时间

Answer 1

很多时候，在选择题中都有错别字。这里也没有O。唯一的树不能仅仅通过后序来绘制，我们必须搜索一个可能的前序，如下所示（ABDECF），所以答案是C（假设选项中有错别字），因为a最后是后序，所以它必须是根，所以一个可能树如下

在你知道A是根之后，我们只剩下DEBFC。在这里，一些节点属于二叉树的左侧，一些属于右侧。有多少个节点属于左侧，有多少个节点属于右侧。由于首先考虑二叉树的左侧，并且由于每个节点预计最多有两个子节点，因此 DEB 将是二叉树的左侧，而 FC 将是右侧。现在，我们知道 FC 位于二叉树的右侧。同样，最后一个节点将是子树的根，F 是其左侧。接下来我们来到二叉树的左侧，它是 DEB。同样，B 将是子树的根。D和E分别是它的左侧和右侧。这样就创建了树！！

Answer 2

预序遍历的一般算法如下，

public void preorder(Node n) {
    if(n == null) {
        return;
    }
    System.out.println(n.data);
    preorder(n.left);
    preorder(n.right);
}

因此，当进行前序遍历时，它在验证节点不是null后做的第一件事是打印出节点的值。然后它继续递归调用节点左子级的方法，右子级第二。因此，应该很容易看到前三个字母是ABD，因为前序方法将在树的最左边递归调用。D没有子级，所以前序遍历返回到它在B上的方法调用。现在B的右子级被访问，因此顺序现在是ABDE。E没有子级，所以前序遍历返回到B。但是B的所有子级都被检查过了，所以现在它返回到A。现在在A的右子级上调用了前序方法。现在的顺序是ABDEC。C只有一个左子级，所以前序遍历在访问F后完成，最终的顺序是ABDECF。

Answer 3

如果给定整数，基于小于或大于then属性创建BT就变得容易了。但是如果我们有字母表，那么我不能算出，我们在什么基础上做左节点或右节点

在Java＜code＞（“B”

二叉树的后序遍历是DEBFCA

根据后序的定义，你知道 A 是根，所以问题是 B 或 D 是在 A 的左边还是右边（如果你考虑给你的选择）

同样从后排序中，您知道D必须是最左边的元素，因为它位于后排序字符串的开头。现在，您可以排除选项A（D不是C的子级）和选项B（D不是紧邻AA的左边）。

此时，您可以确定您的树是这样的，因为后排序以CA结束，以D开始

    A 
  B    C
 ...   ...
D     ......

在后序中，您有FCA，因此F将是C的子级，C是a的子级。

    A 
  B    C
 ...   ...
D     ...  F

我们已经完成了除 E 之外的所有工作。从后序来看，你有 DE，我们有 D 作为最左边的叶子，所以 E 一定是它的兄弟姐妹。

这是一棵完整的树(我认为F的位置可以互换)

     A 
  B    C
D  E     F

通过消除，选项C仍然存在。