构造给定的二叉树Post order

如果只有给出的信息是后序遍历，如何构造二叉树。通过搜索主题，我明白在这种情况下，不可能有独特的构造二叉树。但是，如果给定整数，则基于更少或更大的属性来创建BT变得容易。但是，如果我们有字母表，那么我无法弄清楚我们是以什么为基础制作父节点的左节点或右节点。这是我试图解决的问题。构造给定的二叉树Post order

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

选项：
（A）ABFCDE
（B）ADBFEC
（C）ABDECF
（0）ABDCEF

正确答案是：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非常有帮助，但第3步起，我不明白事情是怎么发生的。感谢您的时间

来源

2017-02-01 sandeep pandey

@ daniel-fischer你能帮我解决这个问题吗 –

这不是你如何通知某人。你可以@用他们的用户名 –

我不认为你发布了正确的字符串。问号字符串中没有字母O，所以C不能正确。 – 4castle

很多次在选择题中有错别字。它在这里没有相同的O. 唯一的树不能通过邮政订单来绘制回答我们必须搜索一个可能的预订它可以是如下（ABDECF），所以ANS为C（假设选项，在错字），因为A是最后的职务序列所以它必须是根这样一个可能的树是

你知道后A是我们只剩下DEBFC的根源。这里的一些节点属于二叉树的左侧，一些属于右侧。左侧有多少个节点，右侧有多少个节点。由于二叉树的左侧被认为是第一个，并且由于每个节点最多有两个孩子，所以DEB将是二叉树的左侧，FC将是右侧。现在，我们知道FC在二叉树的右侧。再次，最后一个节点是子树的根，F是它的左边。接下来我们来到二叉树的左边，它是DEB。再次B将是子树的根。 D和E分别是它的左侧和右侧，这样树就创建了！

来源

2017-02-01 04:49:47 Akshay

很显然，A将是根。你在什么基础上在左边和右边儿童中放置了B，C，可以有其他的方式，对其他人也是如此。DEBFC –

在你知道A是根后，请看编辑的解释。干杯 – Akshay

你以什么为基础声称“DEB将是二叉树和FC的左侧“因为所有的DEBFC都可以是左子树或右子树。说每个节点最多可以有2个孩子并不妨碍“DEBFC”完全成为左子树或右子树的一部分。 Plz参考http://ugcnetsolved-computerscience.blogspot.in/2012/09/june-2012-paper-ii.html并进入评论部分。 thx –

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

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

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

来源

2017-02-01 05:06:09

如果给定整数很容易创建BT基于更少或更大的属性。但是，如果我们字母表那么我凭什么我们做左节点或右节点

那么，在Java ("B" > "A") == true因为字符串是字典顺序比较...

的职位上无法搞清楚二叉树的遍历阶是DEBFCA

通过后序的定义，你知道是根，所以这个问题是B或d是否向左或A的权利（如果你考虑给你的选择）

也从后期订购中，您知道D必须是最左边的元素，因为它位于后序订单字符串的开头。现在您可以排除选项A（D不是C的子项），并且选项B（D不会立即留在A左侧）。

在这一点上，你可以决定你的树看起来像这样因为职位的排序中CA结束与D

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

在后序开始，你有FCA，因此歼将是一个孩子的C，这是A的孩子，要按照这种顺序发生。

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

我们已经完成了所有，但E.从后序，你有DE，我们有d为最左侧叶，所以E必须是它的兄弟。

这里是整个树（F的位置是可以互换的，我认为）

 A 
    B C 
D E  F

通过淘汰，选项C保持。

来源

2017-02-01 05:10:10

“你知道A是根，所以问题是B或D是否在A的左边或右边。”你为什么只考虑B或D.为什么不使用BF或DE（假设您正在比较给定的预购选项） –

“如果这是一个真正有序的二叉树，则B在左边，这排除了选项B.” - 我不确定他们是否在谈论真正有序的二叉树。如果他们不谈论真正有序的二叉树，会怎么样？我知道他们有很多可能性，但我们需要看到预购和后期订单，并找出哪些预购单与后续订单一致 –

解决第一条评论。你当然会以A为根。我想我们在那里同意。我只考虑B和D，因为这是你的问题中唯一的选择。您可以选择AB或AD。 –

构造给定的二叉树Post order

回答

相关问题